$P = \begin{pmatrix}P_1 & 0 \\ R & Q \end{pmatrix}$ is a stochastic $n \times n$ matrix. With $P_1$ being $r \times r$ and $R \neq 0$.
Show that:
a) $P_1$ is an $r \times r$ stochastic matrix and $Q$ has at least one row sum less than 1.
b) the left eigenvectors corresponding to the eigenvalue 1 must have the form $p^\top = (p_1^\top 0)$ where $p^\top$ is an r-vector.
Alright so I have no clue how to solve this. This is what I have come up with this far.
Since P is a stochastic matrix we can reorder the rows columns, so for example if
$$P = \begin{pmatrix} 0.5 & 0 & 0.5 \\
0 & 1 & 0 \\
0 & 0.5 & 0.5
\end{pmatrix}$$
We can change place on the first and second column and then change place of the first and second row aswel to get
$$P = \begin{pmatrix} 1 &0 & 0 \\
0 & 0.5 & 0.5\\
0.5 & 0 & 0.5
\end{pmatrix} = \left(\begin{array}{c|c c}
1 &0 & 0\\
\hline
0 & 0.5 & 0.5 \\
0.5 & 0 & 0.5
\end{array}\right) = \left(\begin{array}{c|c}
P_1 & 0 \\ \hline R & Q
\end{array}\right)$$
For b) if we if we raise $P^n$ we get $\left(\begin{array}{c|c}
I & 0 \\ \hline \star & 0
\end{array}\right)$ when $n$ gets large.
Where $\star = (I+Q+Q^2+… +Q^{n+1})R$. Then perhaps the first row will somehow, magically, be the r-vector $p^\top$.
A solution would be great, a source for theory that will help me tackle this problem and others like it would be even better 🙂
Thanks in advance.
Best Answer
$P$ is given and the question asks you about the properties of $P_1$ and $Q$. You cannot permute the rows and columns of $P$ at will, although you may permute the first $r$ rows/columns and the last $n-r$ rows/columns separately, so that the original block structure remains intact.
Part (a) is easy. If $R\ne0$, then some entry $r_{ik}$ is positive. Therefore $$ 1=\sum_jr_{ij}+\sum_lq_{il}\ge r_{ik}+\sum_lq_{il}>\sum_lq_{il}. $$ Part (b) as it stands is not true. Here is a counterexample: $$ \left[\begin{array}{ccc}0&0&1\end{array}\right] \left[\begin{array}{c|cc}1&0&0\\ \hline\frac12&\frac12&0\\ 0&0&1\end{array}\right] =\left[\begin{array}{ccc}0&0&1\end{array}\right]. $$ However, the problem statement is true if every row of $R$ is nonzero. In this case, every row sum of $Q$ is less than $1$. Hence the induced maximum norm $\|Q\|_\infty$ is less than $1$ and $\lim_{n\to\infty}Q=0$.
Now suppose $v^TP=v^T$. Then $v^TP^2=(v^TP)P=v^TP$ and in turn, $v^TP^n=v^T$ for every $n\ge1$. Therefore $\lim_{n\to\infty}v^TP^n$ exists and is equal to $v^T$. However, if we partition $v^T$ as $(x^T,y^T)$, then $v^TP^n$ is in the form of $(\ast,y^TQ^n)$. It follows that $$ v^T=\lim_{n\to\infty}v^TP^n=\lim_{n\to\infty}(\ast,y^TQ^n)=(\ast,\,y^T\lim_{n\to\infty}Q^n)=(\ast,0). $$