Eigenvalue and the row sum

Question

How could we prove the following statement?

Let $A \in \mathbb C^{n \times n}$ such that $\displaystyle \sum_{j=1}^{n} |a_{ij}| \leq 1$ for all $1 \leq i \leq n$, then $\forall \ \lambda \in \sigma(A)$, we have $|\lambda| \leq 1$.

Answer 1

Hints:

1. Let $Ax = \lambda x$ (where $x \ne 0$), and write this in terms of the matrix elements, using index notation (recall that $(AB)_{ij} = \sum\limits_k a_{ik} b_{kj}$).
2. Let Let $x_i$ be the largest component of $x$ by magnitude (i.e., $|x_i| \ge |x_j| \ \forall j$), and consider the $i$^th equation from Point 1.
3. Apply absolute value $|\cdot|$ on both sides of the equation, and recall that $|a + b| \le |a| + |b|$.
4. From the resulting inequality, what can be concluded about $|\lambda|$? Keep in mind that $\frac{|x_j|}{|x_i|} \le 1\ \forall j$.

---

Full Solution:

Let $\lambda$ be any eigenvalue of $A$, and $x$ a corresponding eigenvector, so that $$Ax = \lambda x \implies \sum_j a_{ij}x_j = \lambda x_i,$$ $i = 1, \ldots, n$ (where $n$ is the order of $A$).

Let $x_i$ be the largest component of $x$ by magnitude (and note that $x_i \ne 0$ since $x \ne 0$). Then $\dfrac{|x_j|}{|x_i|} \le 1$, $j = 1, \ldots, n$. Now,

\begin{align*} |\lambda x_i| &= \left| \sum_j a_{ij} x_j \right| \implies\\ |\lambda| \cdot |x_i| &\le \sum_j |a_{ij}| |x_j| \implies\\ |\lambda| &\le \sum_j |a_{ij}| \dfrac{|x_j|}{|x_i|} \le \sum_j |a_{ij}| \le 1. \end{align*}