Matrix of non complete rank and existence of perpendicular vector (fundamental theorem of Markov chains)

Question

I'm reading a proof about fundamental theorem of Markov chains and I don't understand a part of the proof. If P is a $n \times n$ matrix of transition probabilities (i.e all its entries are greater or equal than $0$ and elements of every row sum $1$), we define the matrix $n \times (n+1)$, $A:=[P-I, \vec{1}]$ where $\vec{1}$ is a vector of $n$ entries equal to $1$. If rank of $A$ is less than $n\geq 2$, I don't understand why there exist a nonzero vector $\vec{w}$ which is perpendicular to $\vec{1}$ and a scalar $\alpha$ such that $(P-I)\vec{w}=\alpha\vec{1}$.

Answer 1

First, notice that $P\cdot \vec{1}=\vec{1}$, and thus $$A\cdot\begin{pmatrix}\vec{1} \\ 0\end{pmatrix}=\left((P-I)\cdot \vec{1}+\vec{1}\cdot 0\right)=0.$$

Now if $\operatorname{rank}(A)<n$, there must be a vector $\vec{u}=\begin{pmatrix} \vec{v} \\ -\alpha\end{pmatrix}$ which is not a multiple of $\begin{pmatrix}\vec{1} \\ 0\end{pmatrix}$ and shuch that $A\cdot u=0$. This last condition is equivalent to $$(P-I)\vec{v}=\alpha\vec{1} ;$$ so it remains to see that we can choose $\vec{v}\neq 0$ and such that $\vec{v}\bot \vec{1}$. To show this, first notice that we can assume that $\vec{v}$ is not a multiple of $\vec{1}$, as otherwise we would have $\alpha=0$ and $\vec{u}=\begin{pmatrix} \vec{v} \\ -\alpha\end{pmatrix}$ would be a multiple of $\begin{pmatrix}\vec{1} \\ 0\end{pmatrix}$. Now notice that $$\begin{pmatrix} \vec{w} \\ -\alpha\end{pmatrix}=\begin{pmatrix} \vec{v} \\ -\alpha\end{pmatrix}-\dfrac{\vec{1}^t\cdot v}{n}\begin{pmatrix}\vec{1} \\ 0\end{pmatrix}$$is still an element of $\ker A$; by the argument above, $w$ is nonzero, and $$\vec{1}^t\cdot \vec{w}=\vec{1}^t\cdot \vec{v}-\left(\dfrac{\vec{1}^t\cdot v}{n}\right)\vec{1}^t\cdot \vec{1}=\vec{1}^t\cdot \vec{v}-\vec{1}^t\cdot \vec{v}=0.$$

Answer 2

We are given $\operatorname{rank}(A) < n$ and since $\operatorname{rank}(A) + \operatorname{dim}\operatorname{kernel}(A) = n + 1$ this implies $\operatorname{dim}\operatorname{kernel}(A) \geq 2.$

Given any $x \in \operatorname{kernel}(A)$ with $x \neq 0$ we can extend to an orthogonal basis of $\operatorname{kernel}(A)$. In particular we find a $y \in \operatorname{kernel}(A)$ with $y \neq 0$ such that $x$ and $y$ are linearly independent and orthogonal.

Let $\mathbf{1}$ denote a $ n \times 1$ column vector of 1's where $n$ is the dimension of $P$.

Clearly $x = \left[ \begin{matrix} \mathbf{1} \\ 0 \end{matrix} \right] \in \operatorname{kernel}(A)$, so there is a $y \in \operatorname{kernel}(A), y = \left[\begin{matrix} \mathbf{w} \\ -\alpha \end{matrix} \right] \neq 0 $ orthogonal to $x$. We must have $\mathbf{w}^{\top}\mathbf{1} = x^{\top}y = 0$.

We cannot have $\mathbf{w} = 0$, for if $\mathbf{w} = 0$ and since $y \in \operatorname{kernel}(A)$, we would have $Ay = (P-I)\mathbf{w} - \alpha \mathbf{1} = -\alpha \mathbf{1} = 0$ which implies both $\alpha$ and $\mathbf{w}$ are 0 which contradicts $ y \neq 0.$

So $\mathbf{w} \neq 0$ is a vector orthogonal to $\mathbf{1}.$

Since $Ay = (P-I)\mathbf{w} -\alpha\mathbf{1} = 0$ we have the required result $(P-I)\mathbf{w} = \alpha\mathbf{1}.$