The Stacks project

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
\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

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

  2. equality holds in ( 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 ( 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)

Post a comment

Your email address will not be published. Required fields are marked.

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).

Unfortunately JavaScript is disabled in your browser, so the comment preview function will not work.

All contributions are licensed under the GNU Free Documentation License.

In order to prevent bots from posting comments, we would like you to prove that you are human. You can do this by filling in the name of the current tag in the following input field. As a reminder, this is tag 0C5V. Beware of the difference between the letter 'O' and the digit '0'.