Given irreducible transition matrix $P$, why does the matrix $(P−I|\mathbb{1})(P−I|\mathbb{1})^T$ have full rank?

Question

Given irreducible transition matrix $P$, why does the matrix $(P−I|\mathbb{1})(P−I|\mathbb{1})^T$ have full rank?

I know this is partially due to the fact that since $P$ is irreducible, there exists an eigenvector $\mathbb{v}$ with eigenvalue 1, where $\mathbb{v}$ is in fact the stationary distribution, but I am not sure exactly how.

Answer 1

Let $P\in Mat_{n \times n}$ be an irreducible transition matrix.

Since the rows of $P-I$ sum to $0$ (the rows of $P$ sum to $1$ and the rows of the identity matrix sum to $1$), the $rk(P-I)\leq n-1$. This implies that $\exists$ an eigenvector $v$ such that $vP=v$.

Continuing with the proof, we find that if $P$ is irreducible, then $\exists$ a unique solution to $\pi P=\pi$ with $\sum_x \pi_x=1$ and $\pi_x>0 \quad \forall x$. This is the stationary distribution of the transition matrix.

Since $\pi P=\pi$, $\quad\!\!\pi(P-I)=0$. But since we also have the restriction that $\sum_x \pi_x=1$, we can add this restriction and we have $\quad\!\!\pi(P-I|1)=\begin{pmatrix} 0&0&\cdot\cdot\cdot&0&1 \end{pmatrix}$ where $(P-I|1)$ is the matrix $P-I$ with the last column replaced by $1$'s.

Since $\pi$ is unique, we have that $\pi=\begin{pmatrix} 0&0&\cdot\cdot\cdot&0&1 \end{pmatrix}(P-I|1)^{-1}$. Thus, because $(P-I|1)$ is invertible, it must have full rank. Also, since $\det(A)=\det(A^t)$, $\quad\!\! (P-I|1)^t$ is also invertible and has full rank. Since both matrices $(P-I|1)$ and $(P-I|1)^t$ are invertible, their product$(P-I|1)(P-I|1)^t$ must also be invertible.

Answer 2

Let $A$ be the $n\times (n+1)$ matrix obtained by attaching a column of ones to $P-I$, and let $x$ be a row vector of length $n$ with $AA^T x^T={\bf 0}.$

Then $\| xA\|^2=xAA^Tx^T=0$ so that $xA={\bf 0}.$ This shows that $x$ is an invariant measure for the Markov chain. But since $P$ is irreducible, all invariant measures are of the form $\lambda \pi$, where $\lambda\in\mathbb{R}$ and $\pi$ is the unique invariant probability measure. Write $x=\lambda \pi$.

Because of the column of ones, $xA={\bf 0}$ also implies that $0=\sum_i x_i = \lambda \sum_i \pi_i=\lambda.$ In other words, $x^T={\bf 0}.$

This shows that the matrix $AA^T$ is invertible, and hence has full rank, equal to $n$.