¿La órbita de una matriz puede generar una base?

Question

Sea A una matriz $n\times n$ dado un n-vector $v$ ¿Qué condiciones se dan en $v$ y $A$ son necesarios para $[v, Av,..., A^{n-1}v]$ serán linealmente independientes?

Por ejemplo, si $v$ es un vector propio o $A^k=Id$ $(k<n)$ no son linealmente independientes.

En otras palabras, cuando la órbita de una matriz sobre un espacio vectorial $V$ (de dimensión finita) puede generar una base de $V$ ?

Answer 1

Una matriz (asociada a un endomorfismo) para la que existe $v$ tal que $(v,Av, \dots, A^{n-1})$ es linealmente independiente se llama endomorfismo cíclico . Esta es una traducción directa al francés y no estoy seguro de que sea una redacción matemática correcta en inglés.

Al menos la Wikipedia menciona que un vector $v$ para lo cual $(v,Av, \dots, A^{n-1})$ abarca $V$ es un vector cíclico .

Puede consultar la Wikipedia en francés Descomposición de Frobenius En particular, el párrafo Endomorfismo cíclico . Por desgracia, la versión inglesa parece carecer de un párrafo similar.

Este párrafo menciona condiciones equivalentes para un endomorfismo $u$ para ser cíclico:

• el grado del polinomio mínimo de $u$ es igual a la dimensión de $V$ ,

• el polinomio mínimo y el polinomio característico de $u$ son iguales (con el signo cerca);

• un endomorfismo conmuta con $u$ (si y) sólo si es un polinomio en $u$ ;

• hay una base de $V$ en la que la matriz de $u$ es una matriz compañera. Es entonces la matriz compañera del polinomio mínimo de $u$ .

Answer 2

Esto es básicamente un replanteamiento del problema, pero aún así puede ser útil.

Para cada vector $v \in V$ existe un único polinomio mónico $p$ de grado mínimo tal que $p(A)v = 0$ .

En concreto, el polinomio mínimo $m_A$ de $A$ aniquila $A$ por lo que el conjunto de todos los polinomios mónicos $q$ tal que $q(A)v = 0$ es no vacía. Consideremos los polinomios de grado mínimo.

Dejemos que $p,q$ sean dos de estos polinomios. Entonces $(q-r)(A)v = q(A)v - r(A)v = 0$ y $q-r$ es de menor grado que el mínimo, lo que implica $q = r$ .

En consecuencia, si $q(A)v= 0$ entonces $p \,|\,q$ . A saber, $\deg q \ge \deg p$ por lo que existe un único $g, h$ tal que $p = qg + h$ con $\deg h < \deg p$ . En particular

$$0 = q(A)v = g(A)p(A)v + h(A)v = h(A)v \implies h = 0 \implies p \,|\,q$$

Tenga en cuenta que $\deg p \le n$ porque $\deg m_A \le n$ y $p \,|\, m_A$ .

Por lo tanto, la independencia lineal de $\{v, Av, \ldots, A^{n-1}v\}$ equivale al hecho de que $\deg p = n$ que a su vez equivale a $m_A = p$ .

Answer 3

La respuesta a su pregunta "cuándo $(*)$ la órbita $\{v,Av,\cdots,A^{n-1}v\}$ sobre un espacio vectorial $V$ puede generar una base de $V$ ?" es, desde un punto de vista probabilístico: SIEMPRE.

En efecto, dejemos que $\chi_A$ sea el polinomio característico de $A$ y $discr_A$ sea su discriminante. El conjunto $Z$ de $A\in M_n(\mathbb{C})$ s.t. $discr_A\not= 0$ es denso abierto Zariski. Por lo tanto, si las entradas de $A$ se eligen al azar (utilizando una ley normal, por ejemplo), entonces $A\in Z$ (es decir $A$ tiene $n$ valores propios distintos) con probabilidad $1$ . Podemos suponer que $A$ es diagonal; entonces el vector $v=[1,\cdots,1]^T$ realiza $(*)$ y más generalmente, un vector elegido al azar realiza $(*)$ con probabilidad $1$ Por lo tanto, cuando $A\in Z$ (no en forma diagonal) entonces un vector aleatorio realiza $(*)$ con probabilidad $1$ .

Por supuesto, existen matrices, con múltiples valores propios, que tienen la propiedad considerada. cf. las otras respuestas.

Answer 4

Un poco de contexto: la órbita que describes se llama Subespacio de Krylov .

Para el caso en que $ V = \mathbb{R}^n$ :

Considere un diagonalizable $A$ ya que los vectores propios de $A$ span $\mathbb{R}^n$ podemos escribir

$$ v = \sum_i^n c_i \mathbf{u}_i, \; \mathbf{u}_i \text{ eigenvector of $ A $} $$

Entonces, por cada potencia de $A$ tenemos

$$ A^k v = A^k \left( \sum_i c_i \mathbf{u}_i \right) = \sum_i c_i A^k \mathbf{u}_i = \sum_i c_i (\lambda_i)^k \mathbf{u}_i $$

Basándonos en la observación anterior, podemos escribir $\left\{ v, Av, \dots, A^{n-1} v \right\}$ en forma compacta como

$$ \{ v, Av, \dots, A^{n-1}v\} = \underbrace{\begin{pmatrix} c_1 \mathbf{u}_1 & \dots & c_n \mathbf{u}_n \end{pmatrix}}_{\displaystyle=: U_c, \in \mathbb{R}^{n \times n}} \underbrace{\begin{pmatrix} 1 & \lambda_1 & \dots & \lambda_1^{n-1} \\ 1 & \dots & \dots & \dots \\ 1 & \lambda_n & \dots & \lambda_n^{n-1} \end{pmatrix}}_{\Lambda} $$

Para que lo anterior sea una base de $V$ queremos que su determinante sea distinto de cero, lo que significa que queremos $$ \det(\Lambda) \neq 0 \Rightarrow \prod_{i \neq j} (\lambda_i - \lambda_j) \neq 0 \Leftrightarrow \lambda_i \neq \lambda_j, i \neq j, \; \\ \det(U_c) \neq 0 \Rightarrow c_i \neq 0, \; \forall i $$ donde la primera igualdad se deduce del hecho de que $\Lambda$ es un Matriz Vandermonde . Si $v$ es representable como una combinación lineal de $d < n$ vectores propios, uno de los $c_i$ 's arriba será $0$ , haciendo que $\det(U_c) = 0$ . Por otro lado, si todos los vectores propios son necesarios para representar $v$ el subespacio resultante abarca $V = \mathbb{R}^n$ .

Answer 5

Respuesta para el campo $\mathbb C$ :

Si $A\in\mathbb C^{n\times n}$ y $v\in\mathbb C^n$ el conjunto $\{v,Av,\ldots,A^{n-1}v\}$ es una base de $\mathbb C^n$ si y sólo si para cada valor propio $\lambda$ de $A$ tenemos $\dim\ker(A-\lambda I) = 1$ y $v\notin\operatorname{im}(A-\lambda I)$ .

Por supuesto, la primera condición significa que el polinomio mínimo y el característico coinciden. Si se elige una matriz aleatoria $A$ y un vector aleatorio $v$ entonces ambas condiciones se satisfacen con probabilidad $1$ confirmando la respuesta de loup blanc.

Prueba. Supongamos que el conjunto es una base de $\mathbb C^n$ . mechanodroid ya ha demostrado en su respuesta que $\dim\ker(A-\lambda I) = 1$ para cada valor propio $\lambda$ de $A$ . Supongamos que $v = (A-\lambda I)u$ para algún valor propio $\lambda$ y algunos $u\in\mathbb C^n$ . Entonces cada uno de los vectores $A^kv = (A-\lambda I)A^ku$ está contenida en $\operatorname{im}(A-\lambda I) \neq \mathbb C^n$ y por lo tanto el conjunto no puede abarcar $\mathbb C^n$ . Una contradicción.

Supongamos ahora que las condiciones se cumplen para cada valor propio $\lambda$ y supongamos que el conjunto es linealmente dependiente. Entonces existe un polinomio mónico $p$ de grado como máximo $n-1$ tal que $p(A)v = 0$ . Tal y como señala mechanodroid en su respuesta, tenemos $p|m_A$ y así $p(z) = \prod_{k=1}^m(z-\lambda_k)^{n_k}$ donde el $\lambda_k$ son los valores propios distintos de $A$ y $\sum_{k=1}^mn_k < n$ (también permitimos $n_k = 0$ aquí). Para cada $k$ dejar $\ell_k$ sea el menor número tal que $\ker((A-\lambda_k I)^{\ell_k}) = \ker((A-\lambda_k I)^{\ell_k+1})$ . Es bien sabido que $$ \mathbb C^n = \mathcal L_1\oplus\dots\oplus\mathcal L_m, $$ donde $\mathcal L_k := \ker((A-\lambda_k I)^{\ell_k})$ . Así, podemos descomponer $v$ como $v = \sum_{k=1}^mv_k$ con $v_k\in\mathcal L_k$ . Ahora $p(A)v = 0$ implica que $(A-\lambda_k I)^{n_k}v_k = 0$ . Por supuesto, tenemos $\dim\mathcal L_k = \ell_k$ Así que $\sum_{k=1}^m\ell_k = n$ . Por lo tanto, existe al menos una $k$ tal que $n_k < \ell_k$ . WLOG, que $n_1 < \ell_1$ . Nuevamente por suposición, esto implica la existencia de algún $u_1\in\ker((A-\lambda_1)^{n_1+1})$ tal que $(A-\lambda_1 I)u_1 = v_1$ . Ahora, dejemos que $A_k$ denota la restricción de $A$ a $\mathcal L_k$ . Entonces $A_k$ deja $\mathcal L_k$ invariante y $A_k - \lambda_1 I$ es un mapeo biyectivo sobre $\mathcal L_k$ para $k\neq 1$ . Por lo tanto, $u_k := (A_k - \lambda_1 I)^{-1}v_k\in\mathcal L_k$ existe para $k\neq 1$ . Establecer $u := \sum_{k=1}^mu_k$ . Entonces $(A-\lambda_1 I)u = \sum_{k=1}^m(A_k-\lambda_1 I)u_k = \sum_{k=1}^mv_k = v$ Es decir, $v\in\operatorname{im}(A-\lambda_1 I)$ lo que contradice nuestra suposición.