Rank$[b \ Ab \ A^2b \ \cdots \ A^{n-1}b]=n$ if and only if Rank$[A-\lambda I \ b]$=n Here's a problem I've been stuck on for quite a while.
Let $A$ be a complex $n\times n$ matrix and $b$ a complex $n\times 1$ vector. Then
Rank$[b \ Ab \ A^2b \ \cdots \ A^{n-1}b]=n$ if and only if Rank$[A-\lambda I \ b]=n$ for every eigenvalue $\lambda$ of $A$.
A few approaches I've tried so far:


*

*For $(\implies)$: $A$ generates a cyclic vector for $\mathbb{C}^n$ and so $A$ is similar to a companion matrix $C$. I've tried analyzing the rank of $[C-\lambda I \ b]$ but it seems that this matrix would have full rank regardless of whether $\lambda$ is an eigenvalue or not, so I must be missing something.

*For $(\implies)$: $A$ is similar to a Jordan matrix $J$. First of all, using the same approach as the companion matrix attempt the matrix $[J-\lambda I \ b]$ seems to have rank $n$ regardless of the vector $b$ (as long as that vector has a nonzero entry wherever the eigenvalue $\lambda$ is deleted from the Jordan block). Alternatively, I did notice that restricting to a single Jordan block $B$ and looking at $[B-\lambda I \ b]$ is almost a companion matrix, which may help with the converse direction.

*For $(\implies)$: it suffices to show that for a vector $x\in\mathbb{C}^n$ that $x[A-\lambda I \ b]=0$ implies that $x=0$. But then this would require $x[A-\lambda I]=0$ as a $1\times n$ matrix, and so $x$ is an eigenvector for $\lambda$ and so not zero. 
Any help with other approaches to this problem or clearing up misconceptions in my ideas would be greatly appreciated!
 A: This is a special case of the Popov-Belovich-Hautus (PBH) test in control theory. The more general statement is that if $A\in\mathbb F^{n\times n},\ B\in\mathbb F^{n\times m}$ and $C=[B,\,AB,\,\cdots,\,A^{n-1}B]$ where $\mathbb F$ is an algebraically closed field, then
$$
\ \operatorname{rank}(C)=n
\ \Longleftrightarrow
\ \operatorname{rank}[A-\lambda I,B]=n\ \text{ for every eigenvalue $\lambda$ of $A$}.
$$
Suppose $\operatorname{rank}[A-\lambda I,B]<n$ for some eigenvalue $\lambda$ of $A$. Then $v^\top[A-\lambda I,B]=0$ for some vector $v\ne0$. Hence $v^\top B=0,\ v^\top A=\lambda v^\top,\ v^\top C=[v^TB,\,\lambda v^TB,\,\ldots,\,\lambda^{n-1}v^TB]=0$ and $\operatorname{rank}(C)<n$.
Conversely, suppose $r=\operatorname{rank}(C)<n$. Then $C$ contains an $n\times r$ submatrix $X$ of full column rank. Complete $X$ to a nonsingular matrix $P=[X,Y]$. Let $\operatorname{col}(M)$ denotes the column space of a matrix $M$. By Cayley-Hamilton theorem, $A^n$ is a polynomial in $A$. Therefore
$$
A\operatorname{col}(X)
=\operatorname{col}(AC)
=\operatorname{col}([AB,\,\ldots,\,A^{n-1}B,\,A^nB])
=\operatorname{col}([AB,\,\ldots,\,A^{n-1}B])
\subseteq\operatorname{col}(X).
$$
In other words, $\operatorname{col}(X)$ is an invariant subspace of $A$. It follows that
$$
P^{-1}AP=\begin{bmatrix}A_{11}&A_{12}\\ 0&A_{22}\end{bmatrix}
\ \text{ and }\ P^{-1}B=\begin{bmatrix}B_1\\ 0_{(n-r)\times m}\end{bmatrix}
$$
where $A_{22}$ is $(n-r)\times(n-r)$. Since $P^{-1}AP$ is similar to $A$, each eigenvalue of $A_{22}$ is an eigenvalue of $A$. Let $w$ be a left eigenvector of $A_{22}$ corresponding to an eigenvalue $\lambda$. Then
\begin{aligned}
\begin{bmatrix}0&w^\top\end{bmatrix}
P^{-1}\begin{bmatrix}A-\lambda I&B\end{bmatrix}\begin{bmatrix}P\\ &I_m\end{bmatrix}
&=\begin{bmatrix}0&w^\top\end{bmatrix}\begin{bmatrix}P^{-1}(A-\lambda I)P&P^{-1}B\end{bmatrix}\\
&=\begin{bmatrix}0&w^\top\end{bmatrix}\begin{bmatrix}A_{11}&A_{12}&B_1\\ 0&A_{22}&0\end{bmatrix}\\
&=\begin{bmatrix}0&w^\top A_{22}&0\end{bmatrix}\\
&=0.
\end{aligned}
Therefore $\operatorname{rank}[A-\lambda I,B]<n$. 
