# Orbit of a matrix can generates a basis?

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

• What makes this special to $\mathbb{R}^n$? – Chappers May 23 '18 at 20:07
• I put a bunch of equivalent conditions math.stackexchange.com/questions/92480/… – Will Jagy May 23 '18 at 20:07
• 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. – N8tron May 23 '18 at 20:09
• @N8tron: good catch, I'm editing my answer. – VHarisop May 23 '18 at 20:10
• 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. – 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$.

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

• Linear independence of the set IMPLIES $\deg p = n$, but they are not equivalent. – 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.