$I-M$ is an non-invertible matrix

Question

Why if $M = (m_{ij})$, with dimension $n \times n$, is a stochastic matrix, then the matrix $I-M$ must be non-invertible? I think if we echelon $I-M$, then eventually we will get a zero line (i.e. $\det(I-M)=0$), but I am not sure how I can prove it.

Answer 1

Each column of your matrix sums to one so we have $$(I-M)^T\begin{bmatrix} 1 \\ 1 \\ \vdots \\ 1\end{bmatrix} = (I-M^T)\begin{bmatrix} 1 \\ 1 \\ \vdots \\ 1\end{bmatrix} = \begin{bmatrix} 1 \\ 1 \\ \vdots \\ 1\end{bmatrix} - M^T\begin{bmatrix} 1 \\ 1 \\ \vdots \\ 1\end{bmatrix} = \begin{bmatrix} 1 - \sum_{j=1}^n m_{j1} \\ 1 - \sum_{j=1}^n m_{j2} \\ \vdots \\ 1 - \sum_{j=1}^n m_{jn}\end{bmatrix} = 0$$ so the kernel of $(I-M)^T$ is nontrivial, which implies that $(I-M)^T$ is singular. Now of course $I-M$ is singular as well.