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
\begin{equation} \label{models-equation-ineq} -a_{ii}m_ i \geq \sum \nolimits _{j \not= i} a_{ij}m_ j \end{equation}
for each $i$, then $\mathop{\mathrm{Ker}}(A)$ is the vector space spanned by the vectors $x_ I$ such that
$a_{ij} = 0$ for $i \in I$, $j \not\in I$, and
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$
Comments (0)