Let \(A=(a_{ij})\) be a real \(n\times n\) matrix with nonnegative entries such that \[ \sum_{j=1}^n a_{ij}=1 \qquad(1\le i\le n). \] Prove that no eigenvalue of \(A\) has absolute value greater than \(1\).
Solution
1. Let \(\lambda\in\CC\) be an eigenvalue of \(A\), and choose a nonzero vector\[ v=(v_1,\ldots,v_n)^T\in\CC^n \]such that\[ Av=\lambda v. \]
Although \(A\) is real, its eigenvalues may be complex, so it is enough to work over \(\CC\).
2. Choose an index \(i\) such that\[ \abs{v_i}=\max_{1\le j\le n}\abs{v_j}. \]Then \(v_i\ne0\).
Such an index exists because there are finitely many coordinates. Since \(v\ne0\), the maximum modulus is positive.
3. One has\[ \abs\lambda\le1. \]
Taking the \(i\)th coordinate of \(Av=\lambda v\) and using nonnegativity of the entries gives \[ \begin{aligned} \abs\lambda\,\abs{v_i} &=\abs{\sum_{j=1}^n a_{ij}v_j}\\ &\le\sum_{j=1}^n a_{ij}\abs{v_j}\\ &\le\sum_{j=1}^n a_{ij}\abs{v_i}\\ &=\abs{v_i}. \end{aligned} \] Since \(v_i\ne0\) by step 2, division by \(\abs{v_i}\) yields \(\abs\lambda\le1\).
4. Therefore no eigenvalue of \(A\) has absolute value greater than \(1\).
Step 3 applies to an arbitrary eigenvalue \(\lambda\) of \(A\).
5. Q.E.D.
Step 4 is the required conclusion.