1
$\begingroup$

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.

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

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.

$\endgroup$
1
  • 1
    $\begingroup$ Thanks. I like that your proof uses the condition that rows sum up less than one to derive the contradiction in a beautiful manner! $\endgroup$
    – Kota Mori
    Jun 23 '17 at 6:44
0
$\begingroup$

For the system of equations to have a unique solution then the determinant of the matrix $(I-M)$ must be non-zero.

Now if it is zero then the system of equations either have infinite solutions or no solution. To find which one, do Gaussian Elimination. If you find that a certain variable can be a free variable ( e.g. 0=0 in augmented matrix) then it has infinite solutions. But, if you find an inconsistency in a variable like 0=-3(or any non zero number) then the system has no solutions.

This post also shares some examples: Examples

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.