Linear Algebra – Connection Between Sum of Matrix Columns and Largest Eigenvalues

eigenvalues-eigenvectorslinear algebra

Let's say I have a matrix $A\in\mathbb{R}^{n\times n}$. 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?

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