Eigenvalues of this stochastic matrix

Question

Consider the matrix $I - P + Q$, where $P$ and $Q$ stochastic matrices that satisfy $$PQ = QP = QQ = Q$$ I want to show that $I - P + Q$ is invertible, so I am analyzing its eigenvalues. I know that the eigenvalues of $P$ and $Q$ are between -1 and 1 because they are stochastic. Since $$I - P + Q = I - P + PQ = I - P(I + Q)$$ it should be enough to see what happens to the eigenvalues of $P(I + Q)$. Any hints for this part?

Answer 1

$I-P+Q$ is not necessarily invertible.

Consider, for instance, $P=I$ and $$Q = \begin{bmatrix}0.5 & 0.5 \\ 0.5 & 0.5 \end{bmatrix}.$$

Answer 2

As shown in the other answer, with the given conditions, $I-P+Q$ may be singular. However, we will prove that when $P$ and $Q$ are also irreducible (e.g. when both matrices are entrywise positive), $I-P+Q$ must be invertible.

Suppose $Q$ is irreducible. Then $1$ is a simple eigenvalue of $Q$. Since $Q$ by assumption is also idempotent, it is a rank-one projection matrix and we may write $Q=uv^T$ for some vectors $u$ and $v$ such that $v^Tu=1$. As $Q$ is irreducible, these two vectors must be entrywise nonzero. Yet, $Q$ is entrywise nonnegative. Hence we may assume that both $u$ and $v$ are entrywise positive.

(We may also take $u$ as the vector of ones because $Q$ is row-stochastic, but this is unimportant here.)

Since $PQ=QP$, we have $(Pu)v^T=u(v^TP)$. Hence $Pu$ is a scalar multiple of $u$ and $v^TP$ is a scalar multiple of $v^T$. In other words, $u$ is a right eigenvector of $P$ and $v$ is a left eigenvector of $P$. Yet, as $P$ is nonnegative, only the eigenvalue $\rho(P)=1$ can possibly possess any left or right positive eigenvector. Therefore $Pu=u$ and $v^TP=v^T$.

(We have not used the assumption that $PQ=Q$ in the above. Nevertheless, it follows from $Pu=u$ and $v^TP=v^T$ that $PQ=Puv^T=uv^T=Q$. Therefore $PQ=Q$ is a necessary consequence of the other conditions.)

Now suppose $(I-P+Q)x=0$. Then \begin{align} 0&=v^T(I-P+Q)x\\ &=v^T(I-P+uv^T)x\\ &=v^Tx-(v^TP)x+(v^Tu)(v^Tx)\\ &=v^Tx-v^Tx+v^Tx\quad\text{(as $v^TP=v^T$ and $v^Tu=1$)}\\ &=v^Tx.\tag{1} \end{align} Therefore $0=(I-P+Q)x=(I-P+uv^T)x=x-Px$. That is, $Px=x$.

If $P$ is irreducible, then $1$ is a simple eigenvalue of $P$. Since $Pu=u$ and $Px=x$, we must have $x=ku$ for some scalar $k$. So, from $(1)$, we obtain $0=v^Tx=kv^Tu=k$. Thus $x$ is necessarily zero and $I-P+Q$ is nonsingular.