Lemma 55.2.2. Let $A = (a_{ij})$ be a real $n \times n$ matrix with $a_{ij} \geq 0$ for $i \not= j$. Let $m = (m_1, \ldots , m_ n)$ be a real vector with $m_ i > 0$. For $I \subset \{ 1, \ldots , n\}$ let $x_ I \in \mathbf{R}^ n$ be the vector whose $i$th coordinate is $m_ i$ if $i \in I$ and $0$ otherwise. If

55.2.2.1
$$\label{models-equation-ineq} -a_{ii}m_ i \geq \sum \nolimits _{j \not= i} a_{ij}m_ j$$

for each $i$, then $\mathop{\mathrm{Ker}}(A)$ is the vector space spanned by the vectors $x_ I$ such that

1. $a_{ij} = 0$ for $i \in I$, $j \not\in I$, and

2. equality holds in (55.2.2.1) for $i \in I$.

Proof. After replacing $a_{ij}$ by $a_{ij}m_ j$ we may assume $m_ i = 1$ for all $i$. If $I \subset \{ 1, \ldots , n\}$ such that (1) and (2) are true, then a simple computation shows that $x_ I$ is in the kernel of $A$. Conversely, let $x = (x_1, \ldots , x_ n) \in \mathbf{R}^ n$ be a nonzero vector in the kernel of $A$. We will show by induction on the number of nonzero coordinates of $x$ that $x$ is in the span of the vectors $x_ I$ satisfying (1) and (2). Let $I \subset \{ 1, \ldots , n\}$ be the set of indices $r$ with $|x_ r|$ maximal. For $r \in I$ we have

$|a_{rr} x_ r| = |\sum \nolimits _{k \not= r} a_{rk}x_ k| \leq \sum \nolimits _{k \not= r} a_{rk}|x_ k| \leq |x_ r| \sum \nolimits _{k \not= r} a_{rk} \leq |a_{rr}||x_ r|$

Thus equality holds everywhere. In particular, we see that $a_{rk} = 0$ if $r \in I$, $k \not\in I$ and equality holds in (55.2.2.1) for $r \in I$. Then we see that we can subtract a suitable multiple of $x_ I$ from $x$ to decrease the number of nonzero coordinates. $\square$

In your comment you can use Markdown and LaTeX style mathematics (enclose it like $\pi$). A preview option is available if you wish to see how it works out (just click on the eye in the toolbar).