# Condition for this linear equation to have a solution: $x = q + Px$

I am working with a linear equation of the following form.

$$x = q + Px,$$ where $x, q$ are vectors of size $K$ and $P$ is a square matrix of size $K$. The variables satisfy: (1) $q > 0$, (2) $0 \le P_{i,j} \le 1$ for all $i,j$ and (3) $\sum_j P_{i,j} < 1$ for each $i$.

If $(I-P)$ is nonsingular, then the equation can be solved by $x = (I-P)^{-1} q$. My question is whether or not $(I-P)$ is always nonsingular under the above conditions, and if not, what is the condition to add on to make sure the invertibility. I conjecture that it has something to do with the eigenvalues of the matrix but cannot figure out an answer.

Any hint would be appreciated.

• So every entry is strictly between 0 and 1, but the columns must sum to less than 1 on each row? Jun 23 '17 at 5:56
• The rows sum up to strictly less than 1. Each entry entry can be 0. Jun 23 '17 at 6:31

Given those conditions, $(I-P)$ is nonsingular. It is slightly easier to show that $(I-P)^T=I-P^T$ is nonsingular, and this is sufficient, since then we deduce that $$\det(I-P)=\det((I-P)^T)=\det((I-P^T)\neq 0.$$
Suppose there exists $y\neq 0$ in the kernel of $I-P^T$, i.e. $(I-P^T)y=0$. Then $y=P^Ty$. On $\mathbb R^K$, let us use the $\ell^1$ norm $\|.\|_1:z\mapsto \sum_1^K |z_i|$. Then $$\|y\|_1=\|P^Ty\|_1=\sum_{i=1}^K\left|\sum_{j=1}^KP_{j,i}y_j\right|.$$ By the triangle inequality, $$\|y\|_1\le\sum_{j=1}^K|y_j|\sum_{i=1}^K|P_{j,i}|<\sum_{j=1}^K|y_j|=\|y\|_1.$$ This contradicts $y\neq 0$, so we conclude that $\ker(I-P^T)=\{0\}$ is trivial, and $I-P^T$ is nonsingular.
For the system of equations to have a unique solution then the determinant of the matrix $(I-M)$ must be non-zero.