# Connection between Sum of Columns in Matrix and largest eigenvalues

Let's say I have a matrix A, $nx n$ and $\in \mathbb{R}$. Matrix A satisfies the condition that the absolute value sum of its columns is always less than or equal to 1, show that all eigenvalues are less than or equal to 1.

What's the connection between the columns and the eigenvalues?

• Do you mean $\sum_{i=1}^n|a_{ij}|\leq 1$ for all $j$? – Davide Giraudo Sep 26 '12 at 17:09
• Yes, that's what I meant. – Edgar Aroutiounian Sep 26 '12 at 17:11

## 1 Answer

$A$ has the same eigenvalues as its transpose, that I will denote $B$. For $B$, the hypothesis means that $\sum_{j=1}^n|a_{ij}|\leq 1$ for all $i$. If $x\neq 0$ is an eigenvector for $\lambda$, and $i$ is such that $x_i=\lVert x\rVert_{\infty}$, then we have $\sum_{j=1}^na_{ij}x_j=\lambda x_i$ hence $\sum_{j\neq i}a_{ij}x_j=(\lambda-a_{ii})x_i$ and $$\lVert x\rVert_{\infty}|\lambda-a_{ii}|\leq \sum_{j\neq i}|a_{ij}|\cdot |x_j|\leq \sum_{j\neq i}|a_{ij}|\cdot\lVert x\rVert_{\infty}\leq (1-|a_{ii}|)\cdot\lVert x\rVert_{\infty}.$$ As $x\neq 0$, we get $|\lambda-a_{ii}|\leq 1-|a_{ii}|$ hence $|\lambda|\leq 1$.

(we proof the Gershgorin circle theorem)