Sufficient conditions for $x, Ax, A^2x, ...$ being linearly indepedent Suppose $x\in\mathbb{R}^n$ and $A\in\mathbb{R}^{n\times n}$. What is a sufficient condition for $$x, Ax, A^2x, ..., A^{n-1}x$$ being linearly independent?
 A: A possible sufficient condition is that the characteristic polynomial of $A$ is irreducible and $x\ne0$. Unfortunately, with base field $\Bbb R$, we cannot have irreducibility if $n>2$.
A: By the Popov-Belovich-Hautus (PBH) test in control theory, $x,\,Ax,\,\cdots,\,A^{n-1}x$ are linearly independent if and only if the augmented matrix $[A-\lambda I|x]$ has rank $n$ for every complex eigenvalue $\lambda$ of $A$.
A: If the characteristic polynomial of $A$ has no repeated roots, then we have a basis $\{v_i\mid 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$.
Here is a quick proof.  Let $\lambda_i$ be the eigenvalues, $v_i$ the eigenvectors, and $f(x)$ the characteristic polynomial of $A$.  Let $g_i(x)=f(x)/(x-\lambda_i)=\prod_{j\neq i} (x-\lambda_j)$, and let $h_i(x)=g_i(x)/g_i(\lambda_i)$.  Then one can check that $h_i(A)v_j=\delta_{ij}v_j$.  If $x=\sum a_i v_i$, then $h_j(A)(x)=a_j v_j$, so each eigenvector is a linear combination of $x, Ax, A^2x, \ldots$.  Since the eigenvectors are linearly independent, this shows  that $\dim \operatorname{Span}(x,Ax,\ldots A^{n-1}x)=n$.  On the other hand, if we could write $x$ as a linear combination of some subset of the eigenvectors, then $A^kx$ would also be a linear combination of that same subset, so  $\dim \operatorname{Span}(x,Ax,\ldots A^{n-1}x)<n$.
If $A$ has an eigenvalue with geometric multiplicity greater than $1$, then no $x$ will work. Indeed, $\dim \operatorname{Span}(x,Ax,A^2x,\ldots)\leq \dim \operatorname{Span}(I,A,A^2,\ldots)$ which is the degree of the minimal polynomial of $A$.  So a necessary condition is that the minimal polynomial equals the characteristic polynomial, which prevents $A$ from having geometric multiplicity greater than $1$ for any eigenvalue.
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.  If $A$ is in JNF, then each block has a generator, and if we express $x$ with respect to the basis for the JNF, we need the coefficients of all the block generators to be non-zero.  Explaining this is a bit involved, though.
A: Suppose that $K$ is the base field with the algebraic closure $\bar{K}$.  Let $f(t)\in K[t]$ denote the minimal polynomial of $A\in\text{Mat}_{n\times n}(K)$.  First, the situation is trivial if $f(t)$ is of degree less than $n$.  We now assume that $f(t)$ is of degree $n$.
Suppose that $\lambda_1,\lambda_2,\ldots,\lambda_l\in\bar{K}$ be the distinct eigenvalues of $A$ with algebraic multiplicities $m_1,m_2,\ldots,m_l$, respectively.  Denote by $I$ the $n$-by-$n$ identity matrix.  For $i=1,2,\ldots,l$, fix $$a_i\in\ker\big((A-\lambda_i\,I)^{m_i}\big)\setminus \ker\big((A-\lambda_i\,I)^{m_i-1}\big).$$  Extend $\{a_1,a_2,\ldots,a_l\}$ to a basis $\mathcal{B}$ of $\bar{K}^n$ consisting of generalized eigenvectors of $A$ .   Write $V_i$ for the $\bar{K}$-span of $\mathcal{B}\setminus\{a_i\}$ for every $i=1,2,\ldots,l$.
Suppose that $x\in K^n$ is such that $x$, $Ax$, $A^2x$, $\ldots$, $A^{n-1}x$ are linearly independent over $K$. 
There exists a monic polynomial $p(t)\in K[t]$ of degree at most $n-1$ such that $p(A)\,x=0$.  This shows that $q(t):=\gcd\big(p(t),f(t)\big)$ also satisfies $q(A)\,x=0$. This implies that $x$ lies in the kernel of $q(A)$.  Because $q(t)$ is of degree at most $n-1$, it follows that there exists $i\in\{1,2,\ldots,l\}$ such that $(t-\lambda_i)\,q(t)$ divides $f(t)$. Consequently, $x\in V_i$ for some $i\in\{1,2,\ldots,l\}$.
Conversely, assume that $x\in K^n$ is such that $x\in V_i$ for some $i\in\{1,2,\ldots,l\}$.  Then, $p(A)\,x=0$, where $p(t) \in K[t]$ is the monic polynomial such that $p(t)\,q(t)=f(t)$, where $q(t)$ is the minimal polynomial of $\lambda_i$ in $K[t]$.  Thus, $p(t)$ has degree at most $n-1$, and so $x$, $Ax$, $A^2x$, $\ldots$, $A^{n-1}x$ are linearly dependent.  
In conclusion, we have proven the following.  For a fixed $x\in K^n$ and $A\in \text{Mat}_{n\times n}(K)$, $x$, $Ax$, $Ax^2$, $\ldots$, $Ax^{n-1}$ are linearly independent if and only if 


*

*the minimal polynomial of $A$ equals its characteristic polynomial, 

*$x\notin V_i\cap K^n$ for any $i=1,2,\ldots,l$, where the subspaces $V_i\subseteq \bar{K}^n$ are defined as above.


However, I am not sure how useful this formulation will be.
