Lemma 55.2.3. Let $A = (a_{ij})$ be a symmetric 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$. Assume

1. $Am = 0$,

2. there is no proper nonempty subset $I \subset \{ 1, \ldots , n\}$ such that $a_{ij} = 0$ for $i \in I$ and $j \not\in I$.

Then $x^ t A x \leq 0$ with equality if and only if $x = qm$ for some $q \in \mathbf{R}$.

First proof. After replacing $a_{ij}$ by $a_{ij}m_ im_ j$ we may assume $m_ i = 1$ for all $i$. Condition (1) means $-a_{ii} = \sum _{j \not= i} a_{ij}$ for all $i$. Recall that $x^ tAx = \sum _{i, j} x_ ia_{ij}x_ j$. Then

\begin{align*} \sum \nolimits _{i \not= j} -a_{ij}(x_ j - x_ i)^2 & = \sum \nolimits _{i \not= j} -a_{ij}x_ j^2 + 2a_{ij}x_ ix_ i - a_{ij}x_ i^2 \\ & = \sum \nolimits _ j a_{jj} x_ j^2 + \sum \nolimits _{i \not= j} 2a_{ij}x_ ix_ i + \sum \nolimits _ j a_{jj} x_ i^2 \\ & = 2x^ tAx \end{align*}

This is clearly $\leq 0$. If equality holds, then let $I$ be the set of indices $i$ with $x_ i \not= x_1$. Then $a_{ij} = 0$ for $i \in I$ and $j \not\in I$. Thus $I = \{ 1, \ldots , n\}$ by condition (2) and $x$ is a multiple of $m = (1, \ldots , 1)$. $\square$

Second proof. The matrix $A$ has real eigenvalues by the spectral theorem. We claim all the eigenvalues are $\leq 0$. Namely, since property (1) means $-a_{ii}m_ i = \sum _{j \not= i} a_{ij}m_ j$ for all $i$, we find that the matrix $A' = A - \lambda I$ for $\lambda > 0$ satisfies $|a'_{ii}m_ i| > \sum a'_{ij}m_ j = \sum |a'_{ij}m_ j|$ for all $i$. Hence $A'$ is invertible by Lemma 55.2.1. This implies that the symmetric bilinear form $x^ tAy$ is semi-negative definite, i.e., $x^ tAx \leq 0$ for all $x$. It follows that the kernel of $A$ is equal to the set of vectors $x$ with $x^ tAx = 0$. The description of the kernel in Lemma 55.2.2 gives the final statement of the lemma. $\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).