[proofplan] We first translate the PBH rank condition into the absence of a nonzero left eigenvector of $A$ annihilating $B$. Then we compare that condition with the Kalman matrix. A bad left eigenvector immediately annihilates every block $A^kB$ of the Kalman matrix. Conversely, if the Kalman matrix has deficient row rank, its left annihilator is a nonzero $A^*$-invariant subspace; over $\mathbb{C}$ this subspace contains an eigenvector, which becomes the required left eigenvector of $A$. [/proofplan]

[step:Rewrite the PBH rank failure as a left eigenvector condition]Fix $\lambda \in \mathbb{C}$ and define the block matrix \begin{align*} M_\lambda := \begin{bmatrix} \lambda I_n - A & B \end{bmatrix} \in \mathbb{C}^{n \times (n+m)}. \end{align*} The matrix $M_\lambda$ has rank strictly less than $n$ if and only if its row space is a proper subspace of $\mathbb{C}^{n+m}$ of dimension less than $n$, equivalently if and only if the [linear map](/page/Linear%20Map) \begin{align*} L_\lambda: \mathbb{C}^n \to \mathbb{C}^{n+m}, \qquad q \mapsto M_\lambda^*q \end{align*} has nonzero kernel. Thus $\operatorname{rank}M_\lambda<n$ if and only if there exists $q \in \mathbb{C}^n \setminus \{0\}$ such that $q^*M_\lambda=0$. Expanding the block product gives \begin{align*} q^*M_\lambda = \begin{bmatrix} q^*(\lambda I_n-A) & q^*B \end{bmatrix}. \end{align*} Therefore $\operatorname{rank}M_\lambda<n$ if and only if there exists $q \neq 0$ with \begin{align*} q^*(\lambda I_n-A)=0 \end{align*} and \begin{align*} q^*B=0. \end{align*} The first equality is exactly $q^*A=\lambda q^*$, so the PBH rank condition for every $\lambda \in \mathbb{C}$ is equivalent to the nonexistence of a nonzero left eigenvector of $A$ annihilating $B$.[/step]

[guided]Fix a complex number $\lambda \in \mathbb{C}$. The PBH matrix is \begin{align*} M_\lambda := \begin{bmatrix} \lambda I_n - A & B \end{bmatrix} \in \mathbb{C}^{n \times (n+m)}. \end{align*} Since $M_\lambda$ has $n$ rows, saying that $\operatorname{rank}M_\lambda<n$ means that the rows of $M_\lambda$ are linearly dependent over $\mathbb{C}$. Equivalently, there is a nonzero coefficient vector $q \in \mathbb{C}^n$ such that the corresponding linear combination of the rows is zero. Written with conjugate transpose notation, this condition is \begin{align*} q^*M_\lambda=0. \end{align*} Now expand the block multiplication. Because $M_\lambda$ is obtained by adjoining the $n \times n$ block $\lambda I_n-A$ and the $n \times m$ block $B$, we have \begin{align*} q^*M_\lambda = \begin{bmatrix} q^*(\lambda I_n-A) & q^*B \end{bmatrix}. \end{align*} Thus $q^*M_\lambda=0$ holds exactly when both block components vanish: \begin{align*} q^*(\lambda I_n-A)=0 \end{align*} and \begin{align*} q^*B=0. \end{align*} The first equation is equivalent, by distributing $q^*$ over the difference, to \begin{align*} q^*A=\lambda q^*. \end{align*} So failure of the rank condition at the spectral parameter $\lambda$ is precisely the existence of a nonzero left eigenvector $q^*$ of $A$ with eigenvalue $\lambda$ that also annihilates the input matrix $B$.[/guided]

[step:Show that a bad left eigenvector destroys Kalman controllability] Define the Kalman controllability matrix associated to $A$ and $B$ by \begin{align*} \mathcal{K}(A,B):=\begin{bmatrix}B & AB & A^2B & \cdots & A^{n-1}B\end{bmatrix} \in \mathbb{C}^{n \times nm}, \end{align*} where $A^0:=I_n$. We use the finite-dimensional Kalman rank criterion: for matrices $A \in \mathbb{C}^{n \times n}$ and $B \in \mathbb{C}^{n \times m}$, the pair $(A,B)$ is controllable if and only if $\operatorname{rank}\mathcal{K}(A,B)=n$. Assume there exist $\lambda \in \mathbb{C}$ and $q \in \mathbb{C}^n \setminus \{0\}$ such that $q^*A=\lambda q^*$ and $q^*B=0$. We prove by induction on $k \in \mathbb{N}\cup\{0\}$ that \begin{align*} q^*A^k=\lambda^k q^*. \end{align*} For $k=0$, this is $q^*I_n=q^*$. If it holds for $k$, then \begin{align*} q^*A^{k+1}=(q^*A^k)A=\lambda^k q^*A=\lambda^{k+1}q^*. \end{align*} Multiplying by $B$ gives, for every $k \in \mathbb{N}\cup\{0\}$, \begin{align*} q^*A^kB=\lambda^k q^*B=0. \end{align*} In particular, $q^*$ annihilates every block of $\mathcal{K}(A,B)$, so \begin{align*} q^*\mathcal{K}(A,B)=0. \end{align*} Since $q \neq 0$, the rows of $\mathcal{K}(A,B)$ are linearly dependent, and hence \begin{align*} \operatorname{rank}\mathcal{K}(A,B)<n. \end{align*} Thus $(A,B)$ is not controllable. [/step]

[step:Show that failure of Kalman controllability produces an invariant annihilator]Let $A^*$ denote the conjugate transpose of the matrix $A$. Assume now that $(A,B)$ is not controllable. By the Kalman rank criterion stated above, this means \begin{align*} \operatorname{rank}\mathcal{K}(A,B)<n. \end{align*} Define the annihilator subspace \begin{align*} W := \{q \in \mathbb{C}^n : q^*A^kB=0 \text{ for every } k \in \{0,1,\dots,n-1\}\}. \end{align*} Each condition $q^*A^kB=0$ is a homogeneous linear condition on $q$, so $W$ is closed under addition and scalar multiplication; hence $W$ is a complex vector subspace of $\mathbb{C}^n$. Since the rows of $\mathcal{K}(A,B)$ are linearly dependent, there exists $q \in \mathbb{C}^n \setminus \{0\}$ such that $q^*\mathcal{K}(A,B)=0$, so $W \neq \{0\}$. We show that $W$ is invariant under $A^*$. Let $q \in W$. For $k \in \{0,1,\dots,n-2\}$, \begin{align*} (A^*q)^*A^kB=q^*AA^kB=q^*A^{k+1}B=0. \end{align*} For the remaining exponent $k=n-1$, apply the [Cayley-Hamilton theorem](/theorems/865) to the square matrix $A \in \mathbb{C}^{n \times n}$. Since $A$ satisfies its characteristic polynomial, there exist coefficients $c_0,\dots,c_{n-1}\in\mathbb{C}$, determined by that characteristic polynomial, such that \begin{align*} A^n=\sum_{j=0}^{n-1}c_jA^j. \end{align*} Therefore \begin{align*} (A^*q)^*A^{n-1}B=q^*A^nB=q^*\left(\sum_{j=0}^{n-1}c_jA^j\right)B=\sum_{j=0}^{n-1}c_jq^*A^jB=0. \end{align*} Thus $A^*q \in W$, and $W$ is an $A^*$-invariant nonzero subspace of $\mathbb{C}^n$.[/step]

[guided]The failure of Kalman controllability gives a nonzero vector that annihilates the columns of the Kalman matrix. We package all such vectors into the subspace \begin{align*} W := \{q \in \mathbb{C}^n : q^*A^kB=0 \text{ for every } k \in \{0,1,\dots,n-1\}\}. \end{align*} Because \begin{align*} \mathcal{K}(A,B)=\begin{bmatrix} B & AB & A^2B & \cdots & A^{n-1}B \end{bmatrix}, \end{align*} the equation $q^*\mathcal{K}(A,B)=0$ is exactly the collection of equations $q^*A^kB=0$ for $0 \le k \le n-1$. Since $\operatorname{rank}\mathcal{K}(A,B)<n$, the rows of $\mathcal{K}(A,B)$ are linearly dependent, so some nonzero $q \in \mathbb{C}^n$ satisfies $q^*\mathcal{K}(A,B)=0$. Hence $W$ is nonzero. Let $A^*$ denote the conjugate transpose of $A$. Each condition $q^*A^kB=0$ is homogeneous and linear in $q$, so $W$ is closed under addition and scalar multiplication; hence $W$ is a complex vector subspace of $\mathbb{C}^n$. The crucial structural point is that $W$ is invariant under $A^*$. Let $q \in W$. We must prove that $A^*q$ also lies in $W$, meaning that \begin{align*} (A^*q)^*A^kB=0 \end{align*} for every $k \in \{0,1,\dots,n-1\}$. For $0 \le k \le n-2$, the computation is a shift of exponent: \begin{align*} (A^*q)^*A^kB=q^*AA^kB=q^*A^{k+1}B. \end{align*} Since $k+1 \in \{1,\dots,n-1\}$ and $q \in W$, the last expression is zero. The only exponent not covered by this shift is $k=n-1$, because it produces $A^nB$, while the definition of $W$ only controls powers up to $A^{n-1}B$. This is exactly where finite-dimensionality enters. By the [Cayley-Hamilton theorem](/theorems/923) applied to the square matrix $A \in \mathbb{C}^{n \times n}$, the matrix $A$ satisfies its characteristic polynomial, so there are coefficients $c_0,\dots,c_{n-1}\in\mathbb{C}$ such that \begin{align*} A^n=\sum_{j=0}^{n-1}c_jA^j. \end{align*} Therefore \begin{align*} (A^*q)^*A^{n-1}B=q^*A^nB=q^*\left(\sum_{j=0}^{n-1}c_jA^j\right)B=\sum_{j=0}^{n-1}c_jq^*A^jB. \end{align*} Each term $q^*A^jB$ is zero because $q \in W$ and $0 \le j \le n-1$. Hence \begin{align*} (A^*q)^*A^{n-1}B=0. \end{align*} We have verified every exponent in the defining condition of $W$, so $A^*q \in W$. Thus $W$ is a nonzero subspace invariant under $A^*$.[/guided]

[step:Extract a left eigenvector annihilating the input matrix] Since $W$ is a nonzero finite-dimensional complex [vector space](/page/Vector%20Space) and $A^*W \subset W$, the restriction \begin{align*} T: W \to W, \qquad q \mapsto A^*q \end{align*} is a well-defined linear map. The characteristic polynomial of $T$ has a root in $\mathbb{C}$, so $T$ has an eigenvector. Hence there exist $q \in W \setminus \{0\}$ and $\mu \in \mathbb{C}$ such that \begin{align*} A^*q=\mu q. \end{align*} Taking conjugate transposes gives \begin{align*} q^*A=\overline{\mu}q^*. \end{align*} Define $\lambda := \overline{\mu} \in \mathbb{C}$. Since $q \in W$, the case $k=0$ in the definition of $W$ gives \begin{align*} q^*B=0. \end{align*} Thus there exist $\lambda \in \mathbb{C}$ and $q \in \mathbb{C}^n \setminus \{0\}$ such that \begin{align*} q^*A=\lambda q^* \end{align*} and \begin{align*} q^*B=0. \end{align*} By the first step, the PBH rank condition fails for this $\lambda$. [/step]

[step:Combine the two implications]We have proved that the existence of a nonzero left eigenvector $q^*$ of $A$ satisfying $q^*B=0$ implies $\operatorname{rank}\mathcal{K}(A,B)<n$, and conversely that $\operatorname{rank}\mathcal{K}(A,B)<n$ implies the existence of such a left eigenvector. Therefore \begin{align*} \operatorname{rank}\mathcal{K}(A,B)=n \end{align*} if and only if there are no $\lambda \in \mathbb{C}$ and $q \in \mathbb{C}^n \setminus \{0\}$ with $q^*A=\lambda q^*$ and $q^*B=0$. By the rank-left-eigenvector equivalence established in the first step, this is equivalent to \begin{align*} \operatorname{rank}\begin{bmatrix} \lambda I_n-A & B \end{bmatrix}=n \end{align*} for every $\lambda \in \mathbb{C}$. This is exactly the Popov-Belevitch-Hautus controllability test.[/step]

[guided]We now connect the two implications proved above. The Kalman rank criterion, applied to the finite-dimensional matrices $A \in \mathbb{C}^{n \times n}$ and $B \in \mathbb{C}^{n \times m}$, says that $(A,B)$ is controllable exactly when \begin{align*} \operatorname{rank}\mathcal{K}(A,B)=n. \end{align*} The bad-left-eigenvector step proved the contrapositive direction: if there are $\lambda \in \mathbb{C}$ and $q \in \mathbb{C}^n \setminus \{0\}$ with $q^*A=\lambda q^*$ and $q^*B=0$, then $\operatorname{rank}\mathcal{K}(A,B)<n$, so $(A,B)$ is not controllable. The invariant-annihilator and eigenvector-extraction steps proved the reverse contrapositive: if $(A,B)$ is not controllable, then $\operatorname{rank}\mathcal{K}(A,B)<n$, hence there exist $\lambda \in \mathbb{C}$ and $q \in \mathbb{C}^n \setminus \{0\}$ such that \begin{align*} q^*A=\lambda q^* \end{align*} and \begin{align*} q^*B=0. \end{align*} Therefore controllability is equivalent to the nonexistence of such a pair $(\lambda,q)$. Finally, the first step identified failure of the PBH rank condition at a fixed $\lambda$ with the existence of a nonzero $q \in \mathbb{C}^n$ satisfying $q^*A=\lambda q^*$ and $q^*B=0$. Hence the nonexistence of such a left eigenvector for every $\lambda \in \mathbb{C}$ is equivalent to \begin{align*} \operatorname{rank}\begin{bmatrix} \lambda I_n-A & B \end{bmatrix}=n \end{align*} for every $\lambda \in \mathbb{C}$. This proves the Popov-Belevitch-Hautus controllability test.[/guided]