# Linear algebra: proof of sufficient conditions for $x,Ax,A^{2}x,\dots,$ being linearly independent

This questsion is an extension of a previously asked question that I think needs a more rigorous proof (please see the link and the answer by user Aaron).

The question is, given a little bit of different notation (in accordance with control theory), for $$b\in\mathbb{R}^{n}$$ and $$A\in\mathbb{R}^{n\times n}$$, what is a sufficient condition for

\begin{align} b,Ab,A^{2}b,\dots,A^{n-1}b \end{align}

all being linearly independent? Furthermore, if we assume that $$A$$ has $$n$$ distinct eigenvalues $$\lambda_{i}$$, $$i=1,\dots,n$$, is this condition sufficient for the above to hold and if so how do we prove it?

If the characteristic polynomial of $$A$$ has no repeated roots, then we have a basis $$\{v_{i}\;\vert\;1\leq i\leq n\}$$ of eigenvectors for $$\mathbb{C}^{n}$$, and we can express $$x=\sum \alpha_{i}v_{i}$$ in terms of the basis. If all of the $$\alpha_{i}$$ are non-zero, then all of your vectors will be linearly independent. In fact, with this condition on $$A$$, this is a necessary and sufficient condition on $$x$$.

If $$A$$ has an eigenvalue with geometric multiplicity greater than 1, then no $$x$$ will work.

If $$A$$ has repeated eigenvalues but all eigenvalues have geometric multiplicity of 1, then it is still possible to find such an $$x$$, but things are a bit more complicated.

I would be very happy if someone could fill in the blanks for his statements, it is not immediately evident that a $$b$$ with nonzero entries leads to all vectors $$b,Ab,\dots,A^{n-1}b$$ being linearly independent.

• Aaron doesn't say $b$ has nonzero entries. Aaron says if the expression for $b$ as a linear combination of the eigenvectors has all nonzero coefficients, etc., etc. Commented Nov 17, 2020 at 23:50
• Yes, you are correct, my fault. However if you make change of basis then those $\alpha_{i}$ will become coordinates for $b$, thus entries in the transformed case. In this case, it would be correct what I said first. Also, $A$ would take on a diagonal form. Commented Nov 17, 2020 at 23:56

No assumption is made on the field $$k$$ and $$A\in M_n(k)$$.

For $$b\in k^n$$, the $$A^0 b,\ldots, A^{n-1}b$$ are linearly dependent iff there is some non-zero polynomial $$h\in k[x]$$ of degree $$ such that $$h(A)b=0$$.

With $$p\in k[x]$$ the minimal polynomial of $$A$$ and $$g=\gcd(p,h)$$ then $$h(A)b=0,p(A)b=0$$ implies $$g(A)b=0$$.

Thus the necessary and sufficient condition for the $$A^0 b,\ldots, A^{n-1}b$$ to be linearly independent is that $$\deg(p)=n$$ and $$f(A)b\ne 0$$ for each $$f\in k[x]$$ strictly dividing $$p$$.

When the $$\deg(p)=n$$ condition is satisfied, factorize in irreducibles $$p=\prod_j q_j^{e_j}\in k[x]$$. Taking $$b_j \in \ker(q_j(A)^{e_j}) ,\not \in \ker(q_j(A)^{e_j-1})$$ then $$b = \sum_j b_j$$ works.

(take $$f$$ such that $$p = q_j f$$, then $$0=f(A)b = f(A)b_j=\gcd(f,q_j^{e_j})(A)b_j=q_j(A)^{e_j-1}b_j$$ is a contradiction)

• Thank you. This is more complex than I thought it to be. Commented Nov 18, 2020 at 8:31
• @SimpleProgrammer It can't be trivial because if some $b$ works then on the $A^0b,\ldots,A^{n-1}b$ basis $A$ acts as the companion matrix, so this is the main way to find if two matrices $A,A'$ are similar and if so to obtain a $P$ such that $A=PA' P^{-1}$. That said which step is complex ? Commented Nov 18, 2020 at 14:11
• Yes, I see. Well, linear algrbra is not my strong suit and these arguments all look very abstract to me (since I do not know the subject to well). For example, why I need this result is for purposes of control theory, but I did not expect control theory to dwell this deep into linear algebra (control theory can be very hands on / practical is what I mean, so this came as a surprise). Commented Nov 19, 2020 at 11:20