Let A be a matrix $n\times n$, given a n-vector $v$, what conditions over $v$ and $A$ are necessaries for $[v, Av,..., A^{n-1}v]$ will be linearly independent?

For example if $v$ is a eigenvector or $A^k=Id$ $(k<n)$, they are not linearly independent.

In other words, when the orbit of a matrix over a vector space $V$ (finite dimensional) can generates a basis of $V$?


Some context: the orbit you are describing is called a Krylov Subspace.

For the case where $ V = \mathbb{R}^n$:

Consider a diagonalizable $A$: since the eigenvectors of $A$ span $\mathbb{R}^n$, we can write

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

Then, for every power of $A$, we have

$$ 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 $$

Based on the above observation, we may write $\left\{ v, Av, \dots, A^{n-1} v \right\}$ in compact form as

$$ \{ 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} $$

In order for the above to be a basis of $V$, we want its determinant to be nonzero, which means that we want $$ \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 $$ where the first equality follows from the fact that $\Lambda$ is a Vandermonde Matrix. If $v$ is representable as a linear combination of $d < n$ eigenvectors, one of the $c_i$'s above will be $0$, making $\det(U_c) = 0$. On the other hand, if all the eigenvectors are necessary to represent $v$, the resulting subspace spans $V = \mathbb{R}^n$.

  • $\begingroup$ What makes this special to $\mathbb{R}^n$? $\endgroup$ – Chappers May 23 '18 at 20:07
  • $\begingroup$ I put a bunch of equivalent conditions math.stackexchange.com/questions/92480/… $\endgroup$ – Will Jagy May 23 '18 at 20:07
  • 1
    $\begingroup$ A being nonsingular means invertible right? It doesn't follow that $A$ is diagonizable $A=\begin{bmatrix}1 & 1 \\ 0 & 1\end{bmatrix}$ has determinant one so is invertible but is not diagonizable since the 1 eigenspace is 1-dimensional. $\endgroup$ – N8tron May 23 '18 at 20:09
  • $\begingroup$ @N8tron: good catch, I'm editing my answer. $\endgroup$ – VHarisop May 23 '18 at 20:10
  • $\begingroup$ VHarisop, recently I finish a work, and this idea was very usefull in a proof of a proposition, so I would like to thank you. Unfortunately, I do not how to contact you. Anyway, thank you very much. Thank a lot, for all answers. $\endgroup$ – D. L Garcia Oct 1 '20 at 15:01

A matrix (associated to an endomorphism) for which it exists $v$ such that $(v,Av, \dots, A^{n-1})$ is linearly independent is called a cyclic endomorphism. This is a direct French translation and I'm not sure that this is a proper English mathematical wording.

At least Wikipedia mentions that a vector $v$ for which $(v,Av, \dots, A^{n-1})$ spans $V$ is a cyclic vector.

You can have a look to French Wikipedia Decomposition de Frobenius, in particular the paragraph Endomorphisme cyclique. Unfortunately, the English version seems to lack a similar paragraph.

This paragraph mentions equivalent conditions for an endomorphism $u$ to be cyclic:

  • the degree of the minimum polynomial of $u$ is equal to the dimension of $V$,

  • the minimal polynomial and the characteristic polynomial of $u$ are equal (with the sign near);

  • an endomorphism commutes with $u$ (if and) only if it is a polynomial in $u$;

  • there is a base of $V$ in which the matrix of $u$ is a companion matrix. It is then the companion matrix of the minimal polynomial of $u$.

  • $\begingroup$ Google Translate does a perfect job for the conditions you cite. $\endgroup$ – lhf May 23 '18 at 21:26
  • $\begingroup$ If you love the french language, why did you choose a pseudo in English; there is still time to change it ! $\endgroup$ – user91684 May 24 '18 at 0:34
  • $\begingroup$ @loupblanc Good question! This has something to do with the fact that my pseudo is also th name of my website... $\endgroup$ – mathcounterexamples.net May 24 '18 at 4:40
  • $\begingroup$ Of course, my comment is a joke. It's a very good thing to write that one is attached to one's language. $\endgroup$ – user91684 May 24 '18 at 8:24
  • $\begingroup$ Your pseudo is very nice... White wolf! $\endgroup$ – mathcounterexamples.net May 24 '18 at 11:32

This is basically a restatement of the problem, but it still might be useful.

For every vector $v \in V$ there exists a unique monic polynomial $p$ of minimal degree such that $p(A)v = 0$.

Namely, the minimal polynomial $m_A$ of $A$ annihilates $A$ so the set of all monic polynomials $q$ such that $q(A)v = 0$ is nonempty. Consider the polynomials of minimal degree.

Let $p,q$ be two such polynomials. Then $(q-r)(A)v = q(A)v - r(A)v = 0$ and $q-r$ is of lesser degree than the minimal, which implies $q = r$.

As a consequence, if $q(A)v= 0$ then $p \,|\,q$. Namely, $\deg q \ge \deg p$ so there exist unique $g, h$ such that $p = qg + h$ with $\deg h < \deg p$. In particular

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

Note that $\deg p \le n$ because $\deg m_A \le n$ and $p \,|\, m_A$.

Therefore, linear independence of $\{v, Av, \ldots, A^{n-1}v\}$ is equivalent to the fact that $\deg p = n$, which in turn is equivalent to $m_A = p$.

  • $\begingroup$ Linear independence of the set IMPLIES $\deg p = n$, but they are not equivalent. $\endgroup$ – amsmath Jun 1 '19 at 12:37

The answer to your question "when $(*)$ the orbit $\{v,Av,\cdots,A^{n-1}v\}$ over a vector space $V$ can generate a basis of $V$ ?" is, in a probabilistic point of view: ALWAYS.

Indeed, let $\chi_A$ be the characteristic polynomial of $A$ and $discr_A$ be its discriminant. The set $Z$ of $A\in M_n(\mathbb{C})$ s.t. $discr_A\not= 0$ is Zariski open dense. Thus, if the entries of $A$ are randomly chosen (using a normal law for example) then $A\in Z$ (that is $A$ has $n$ distinct eigenvalues) with probability $1$. We may assume that $A$ is diagonal; then the vector $v=[1,\cdots,1]^T$ realizes $(*)$ and more generally, a randomly chosen vector realizes $(*)$ with probability $1$; therefore, when $A\in Z$ (not in a diagonal form) then a random vector realizes $(*)$ with probability $1$.

Of course, there exist matrices, with multiple eigenvalues, that have the considered property. cf. the other answers.


Answer for the field $\mathbb C$:

If $A\in\mathbb C^{n\times n}$ and $v\in\mathbb C^n$, the set $\{v,Av,\ldots,A^{n-1}v\}$ is a basis of $\mathbb C^n$ if and only if for each eigenvalue $\lambda$ of $A$ we have $\dim\ker(A-\lambda I) = 1$ and $v\notin\operatorname{im}(A-\lambda I)$.

Of course, the first condition means that minimal and characteristic polynomial coincide. If you pick a random matrix $A$ and a random vector $v$, then both conditions are satisfied with probability $1$, confirming loup blanc's answer.

Proof. Assume that the set is a basis of $\mathbb C^n$. mechanodroid has already proved in their answer that $\dim\ker(A-\lambda I) = 1$ for every eigenvalue $\lambda$ of $A$. Assume that $v = (A-\lambda I)u$ for some eigenvalue $\lambda$ and some $u\in\mathbb C^n$. Then each of the vectors $A^kv = (A-\lambda I)A^ku$ is contained in $\operatorname{im}(A-\lambda I) \neq \mathbb C^n$ and therefore the set cannot span $\mathbb C^n$. A contradiction.

Assume now that the conditions are true for every eigenvalue $\lambda$ and suppose that the set is linearly dependent. Then there exists a monic polynomial $p$ of degree at most $n-1$ such that $p(A)v = 0$. As mechanodroid pointed out in their answer, we have $p|m_A$ and so $p(z) = \prod_{k=1}^m(z-\lambda_k)^{n_k}$, where the $\lambda_k$ are the distinct eigenvalues of $A$ and $\sum_{k=1}^mn_k < n$ (we also allow $n_k = 0$ here). For each $k$ let $\ell_k$ be the smallest number such that $\ker((A-\lambda_k I)^{\ell_k}) = \ker((A-\lambda_k I)^{\ell_k+1})$. It is well known that $$ \mathbb C^n = \mathcal L_1\oplus\dots\oplus\mathcal L_m, $$ where $\mathcal L_k := \ker((A-\lambda_k I)^{\ell_k})$. So, we may decompose $v$ as $v = \sum_{k=1}^mv_k$ with $v_k\in\mathcal L_k$. Now $p(A)v = 0$ implies that $(A-\lambda_k I)^{n_k}v_k = 0$. By assumption, we have $\dim\mathcal L_k = \ell_k$, so $\sum_{k=1}^m\ell_k = n$. Hence, there exists at least one $k$ such that $n_k < \ell_k$. WLOG, let $n_1 < \ell_1$. Again by assumption, this implies the existence of some $u_1\in\ker((A-\lambda_1)^{n_1+1})$ such that $(A-\lambda_1 I)u_1 = v_1$. Now, let $A_k$ denote the restriction of $A$ to $\mathcal L_k$. Then $A_k$ leaves $\mathcal L_k$ invariant and $A_k - \lambda_1 I$ is a bijective mapping on $\mathcal L_k$ for $k\neq 1$. Therefore, $u_k := (A_k - \lambda_1 I)^{-1}v_k\in\mathcal L_k$ exists for $k\neq 1$. Set $u := \sum_{k=1}^mu_k$. Then $(A-\lambda_1 I)u = \sum_{k=1}^m(A_k-\lambda_1 I)u_k = \sum_{k=1}^mv_k = v$, that is, $v\in\operatorname{im}(A-\lambda_1 I)$, which contradicts our assumption.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.