20.1 Gershgorin Discs

Chapter 16 bounded the whole spectrum with one number: every eigenvalue lies in the disc $\lvert z\rvert \le \left\| \mathbf{A} \right\|_{\infty}$ (Corollary 16.4.2). That disc is centered at $0$ , and it knows nothing about where in it the eigenvalues sit. For a matrix that is nearly diagonal the answer ought to be visible at a glance: the eigenvalues should sit near the diagonal entries, and the off-diagonal entries should say how near. This section makes that precise. It puts one disc around each diagonal entry, with radius measured from the rest of its row, and proves that the discs together hold every eigenvalue. It then sharpens the picture twice: by rescaling the coordinates, and, for irreducible matrices, by looking at the boundary.

Throughout, matrices are complex. A real matrix is read inside $M_n(\mathbb{C})$ , as in Chapter 16 §04, because its eigenvalues may be non-real, and they are what we want to locate.

20.1.1. Discs around the diagonal

Here is the situation to keep in mind. Take $\mathbf{A} = \begin{pmatrix} 6 & 2 & 5 \\ 1 & -1 & 1 \\ 1 & 1 & -1 \end{pmatrix} .$ The row-sum bound gives $\lvert\lambda\rvert \le \left\| \mathbf{A} \right\|_{\infty} = 13$ for every eigenvalue $\lambda$ , a disc of radius $13$ about $0$ . But if the off-diagonal entries were $0$ , the eigenvalues would be exactly $6, -1, -1$ . The off-diagonal entries are a perturbation of the diagonal matrix, and the natural guess is that each eigenvalue stays within reach of some diagonal entry, where the reach of row $i$ is measured by the size of the entries of row $i$ off the diagonal. We give that reach a name.

Around each diagonal entry, draw the disc whose radius is the total size of the other entries in its row.

Definition 20.1.1 (Gershgorin Discs)

Let $n \ge 1$ and $\mathbf{A} = (a_{ij}) \in M_n(\mathbb{C})$ . For $i = 1, \dots, n$ , the $i$ -th Gershgorin radius of $\mathbf{A}$ is the real number $r_i(\mathbf{A}) \mathrel{:=} \sum_{j \ne i} \lvert a_{ij}\rvert \ \ge 0 ,$ the sum over all $j \in \{1, \dots, n\}$ other than $i$ , and the $i$ -th Gershgorin disc is the closed disc $D_i(\mathbf{A}) \mathrel{:=} \{\, z \in \mathbb{C} : \lvert z - a_{ii}\rvert \le r_i(\mathbf{A}) \,\} .$ The discs $D_i(\mathbf{A}^{\top})$ , whose radii $r_i(\mathbf{A}^{\top}) = \sum_{j \ne i}\lvert a_{ji}\rvert$ are taken from the columns of $\mathbf{A}$ , are the column discs.

In words: the center of $D_i(\mathbf{A})$ is the diagonal entry $a_{ii}$ , and the radius adds up the moduli of the entries of row $i$ that are not on the diagonal. The disc includes its boundary circle. A radius may be $0$ , and then the disc is the single point $a_{ii}$ . Since $\mathbf{A}^{\top}$ has the same diagonal as $\mathbf{A}$ , the column discs have the same centers as the row discs and, in general, different radii. The letter $r$ is lowercase on purpose, since $R_{\mathbf{A}}$ is the Rayleigh quotient, and the plain $D_i$ is a set of complex numbers, not the bold diagonal matrix $\mathbf{D}$ .

Some examples, simplest first.

Diagonal matrices and $n = 1$ . For $\mathbf{A} = \operatorname{diag}(d_1, \dots, d_n)$ every radius is $0$ , because every off-diagonal entry is $0$ , and $D_i(\mathbf{A}) = \{d_i\}$ . The discs are the eigenvalues. A $1 \times 1$ matrix $(a)$ is the case $n = 1$ : the sum defining $r_1$ is empty, so $D_1 = \{a\}$ . These degenerate cases are the ones any theorem about the discs must get exactly right.
A $2 \times 2$ matrix. For $\mathbf{B} = \begin{psmallmatrix} 0 & 1 \\ 4 & 0 \end{psmallmatrix}$ , $r_1(\mathbf{B}) = 1$ and $r_2(\mathbf{B}) = 4$ , so the row discs are $\lvert z\rvert \le 1$ and $\lvert z\rvert \le 4$ . The column discs swap the radii: $\lvert z\rvert \le 4$ and $\lvert z\rvert \le 1$ .
The matrix above. $r_1(\mathbf{A}) = 2 + 5 = 7$ , $r_2(\mathbf{A}) = 1 + 1 = 2$ and $r_3(\mathbf{A}) = 1 + 1 = 2$ , so $D_1(\mathbf{A}) = \{\lvert z - 6\rvert \le 7\}$ and $D_2(\mathbf{A}) = D_3(\mathbf{A}) = \{\lvert z + 1\rvert \le 2\}$ . The column radii are $1 + 1 = 2$ , $2 + 1 = 3$ and $5 + 1 = 6$ .

Non-example by minimal change. Keep the radius and move the center to $0$ : replace $D_i(\mathbf{A})$ by $\{\lvert z\rvert \le r_i(\mathbf{A})\}$ . For $\operatorname{diag}(1, 2)$ both radii are $0$ and the modified “discs” are both $\{0\}$ , which misses both eigenvalues. The clause that changed is the center, and the diagonal example shows it is the part that carries the information: the radius only measures how far the off-diagonal part can pull an eigenvalue away from it.

20.1.2. The theorem

It turns out that the guess is right, with no loss at all in the constant:

Theorem 20.1.1 (Gershgorin’s Theorem)

Let $n \ge 1$ , $\mathbf{A} \in M_n(\mathbb{C})$ , and let $\lambda$ be an eigenvalue of $\mathbf{A}$ with eigenvector $\mathbf{x} = (x_1, \dots, x_n)$ . If $k$ is an index with $\lvert x_k\rvert = \max_j \lvert x_j\rvert$ , then $\lambda \in D_k(\mathbf{A})$ . Consequently:

(a) every eigenvalue of $\mathbf{A}$ lies in the union $D_1(\mathbf{A}) \cup \dots \cup D_n(\mathbf{A})$ of the row discs;
(b) every eigenvalue of $\mathbf{A}$ lies in the union $D_1(\mathbf{A}^{\top}) \cup \dots \cup D_n(\mathbf{A}^{\top})$ of the column discs;
(c) hence every eigenvalue lies in the intersection of the two unions.

Idea. We want $\lvert\lambda - a_{kk}\rvert$ to be small for one well-chosen $k$ , so look at row $k$ of $\mathbf{A}\mathbf{x} = \lambda\mathbf{x}$ and move the diagonal term across: $(\lambda - a_{kk})x_k = \sum_{j \ne k} a_{kj}x_j$ . The triangle inequality bounds the right side by $\sum_{j \ne k}\lvert a_{kj}\rvert\lvert x_j\rvert$ , and this becomes $r_k(\mathbf{A})\lvert x_k\rvert$ exactly when every $\lvert x_j\rvert \le \lvert x_k\rvert$ . So choose $k$ where the eigenvector is largest in modulus. Then divide by $\lvert x_k\rvert$ , which is positive because $\mathbf{x} \ne \mathbf{0}$ .

Proof. Let $\mathbf{A}\mathbf{x} = \lambda\mathbf{x}$ with $\mathbf{x} \ne \mathbf{0}$ , and let $k$ be as in the statement; such a $k$ exists because a finite set of real numbers has a largest element. Since $\mathbf{x} \ne \mathbf{0}$ , some $x_j \ne 0$ , so $\lvert x_k\rvert > 0$ . Row $k$ of $\mathbf{A}\mathbf{x} = \lambda\mathbf{x}$ reads $\sum_{j} a_{kj}x_j = \lambda x_k$ , that is, $(\lambda - a_{kk})\,x_k = \sum_{j \ne k} a_{kj}x_j .$ Taking moduli and using the triangle inequality (Theorem 0.6.4), then $\lvert x_j\rvert \le \lvert x_k\rvert$ for every $j$ , $\lvert\lambda - a_{kk}\rvert\,\lvert x_k\rvert \le \sum_{j \ne k}\lvert a_{kj}\rvert\,\lvert x_j\rvert \le \Bigl(\sum_{j \ne k}\lvert a_{kj}\rvert\Bigr)\lvert x_k\rvert = r_k(\mathbf{A})\,\lvert x_k\rvert .$ Dividing by $\lvert x_k\rvert > 0$ gives $\lvert\lambda - a_{kk}\rvert \le r_k(\mathbf{A})$ , that is, $\lambda \in D_k(\mathbf{A})$ .

(a) Every eigenvalue has an eigenvector, and the disc just found is one of the $D_i(\mathbf{A})$ .
(b) By Proposition 9.10.5 (b), $\mathbf{A}^{\top}$ has the same eigenvalues as $\mathbf{A}$ . Applying (a) to $\mathbf{A}^{\top}$ puts each of them in $D_1(\mathbf{A}^{\top}) \cup \dots \cup D_n(\mathbf{A}^{\top})$ .
(c) A point lying in each of two sets lies in their intersection. This proves the theorem.

The move in this proof is worth naming, since the chapter uses it again: choose the dominant coordinate of an eigenvector, then apply the triangle inequality to its row. The choice of the largest coordinate is exactly what lets every $\lvert x_j\rvert$ be replaced by $\lvert x_k\rvert$ without looking at the others.

The theorem recovers Chapter 16’s bound and improves on it. If $\lambda \in D_k(\mathbf{A})$ , then $\begin{aligned} \lvert\lambda\rvert &\le \lvert a_{kk}\rvert + \lvert\lambda - a_{kk}\rvert \le \lvert a_{kk}\rvert + r_k(\mathbf{A}) \\ &= \sum_{j}\lvert a_{kj}\rvert \le \left\| \mathbf{A} \right\|_{\infty} , \end{aligned}$ so (a) implies $\rho(\mathbf{A}) \le \left\| \mathbf{A} \right\|_{\infty}$ , and (b) likewise implies $\rho(\mathbf{A}) \le \left\| \mathbf{A} \right\|_1$ . The union of the discs is never larger than the row-sum disc, and it is usually much smaller, because it keeps the centers.

Example (Discs, eigenvectors, and where each eigenvalue sits)

Let $\mathbf{A} = \begin{pmatrix} 6 & 2 & 5 \\ 1 & -1 & 1 \\ 1 & 1 & -1 \end{pmatrix}$ . Describe the regions given by Theorem 20.1.1 (a) and (b). Then check that $(7, 1, 1)$ , $(-1, 1, 1)$ and $(1, 1, -2)$ are eigenvectors, and locate each eigenvalue in the disc the theorem assigns to it.

Solution. From the radii computed after Definition 20.1.1, the row discs give $\{\lvert z - 6\rvert \le 7\} \cup \{\lvert z + 1\rvert \le 2\} ,$ the second disc counted twice, and the column discs give $\{\lvert z - 6\rvert \le 2\} \cup \{\lvert z + 1\rvert \le 3\} \cup \{\lvert z + 1\rvert \le 6\}$ , where the middle disc lies inside the last. So every eigenvalue lies in $\{\lvert z - 6\rvert \le 2\} \cup \{\lvert z + 1\rvert \le 6\}$ , and also in $\{\lvert z - 6\rvert \le 7\} \cup \{\lvert z + 1\rvert \le 2\}$ . The column discs have separated the two groups of centers; the row discs have not.

Multiplying out, $\mathbf{A}\begin{pmatrix} 7 \\ 1 \\ 1 \end{pmatrix} = \begin{pmatrix} 49 \\ 7 \\ 7 \end{pmatrix}, \quad \mathbf{A}\begin{pmatrix} -1 \\ 1 \\ 1 \end{pmatrix} = \begin{pmatrix} 1 \\ -1 \\ -1 \end{pmatrix}, \quad \mathbf{A}\begin{pmatrix} 1 \\ 1 \\ -2 \end{pmatrix} = \begin{pmatrix} -2 \\ -2 \\ 4 \end{pmatrix},$ so the eigenvalues include $7$ , $-1$ and $-2$ . These are three distinct eigenvalues of a $3 \times 3$ matrix, hence three distinct roots of the degree- $3$ polynomial $p_{\mathbf{A}}$ (Theorem 9.2.1), so by Corollary 6.1.4 there are no others.

The eigenvector $(7, 1, 1)$ peaks at $k = 1$ , and indeed $\lvert 7 - 6\rvert = 1 \le 7$ : $7 \in D_1(\mathbf{A})$ .
The eigenvector $(1, 1, -2)$ peaks at $k = 3$ , and $\lvert -2 + 1\rvert = 1 \le 2$ : $-2 \in D_3(\mathbf{A})$ .
The eigenvector $(-1, 1, 1)$ has all three coordinates of modulus $1$ , so every $k$ is a peak and $-1$ must lie in every row disc. It does: $\lvert -1 - 6\rvert = 7 = r_1(\mathbf{A})$ , so it sits on the boundary circle of $D_1(\mathbf{A})$ , and it is the center of the other two.

Both unions pass the test, and the eigenvector tells us which disc to look in. The row-sum disc $\lvert z\rvert \le 13$ says only that $\lvert\lambda\rvert \le 13$ .

Warning. The union is the claim, not each disc. A single Gershgorin disc need not contain any eigenvalue. For $\mathbf{B} = \begin{psmallmatrix} 0 & 1 \\ 4 & 0 \end{psmallmatrix}$ , $p_{\mathbf{B}}(x) = x^2 - 4$ , so the eigenvalues are $\pm 2$ , while the first row disc is $\lvert z\rvert \le 1$ : it contains neither. Both eigenvalues lie in the second disc $\lvert z\rvert \le 4$ . Nor may the row disc and the column disc of the same index be intersected: $D_1(\mathbf{B}) \cap D_1(\mathbf{B}^{\top})$ and $D_2(\mathbf{B}) \cap D_2(\mathbf{B}^{\top})$ are both $\lvert z\rvert \le 1$ , and $\pm 2$ lies in neither. Part (c) of the theorem intersects the two unions.

Quick check. Without computing any eigenvalue, show that every eigenvalue of $\mathbf{M} = \begin{pmatrix} 5 & 2 & -1 \\ 1 & 6 & 2 \\ -1 & 0 & 3 \end{pmatrix}$ has real part at least $2$ .

Solution. The row discs are $\lvert z - 5\rvert \le 3$ , $\lvert z - 6\rvert \le 3$ and $\lvert z - 3\rvert \le 1$ . A point $z$ of the first has $\operatorname{Re} z \ge 5 - \lvert z - 5\rvert \ge 2$ , of the second $\operatorname{Re} z \ge 3$ , of the third $\operatorname{Re} z \ge 2$ . By Theorem 20.1.1 (a) every eigenvalue lies in one of them, so its real part is at least $2$ . In particular $0$ is not an eigenvalue, and $\mathbf{M}$ is invertible.

20.1.3. Diagonal dominance

The last sentence of the Quick check is a pattern. If $0$ lies outside every disc, then $0$ is not an eigenvalue, and the matrix is invertible. The point $0$ lies outside $D_i(\mathbf{A})$ exactly when $\lvert 0 - a_{ii}\rvert > r_i(\mathbf{A})$ , which is a condition on row $i$ alone.

Corollary 20.1.2 (Strict Diagonal Dominance Implies Invertibility)

Let $n \ge 1$ and $\mathbf{A} \in M_n(\mathbb{C})$ . Call $\mathbf{A}$ strictly diagonally dominant (by rows) if $\lvert a_{ii}\rvert > r_i(\mathbf{A}) = \sum_{j \ne i}\lvert a_{ij}\rvert \qquad\text{for **every** } i = 1, \dots, n .$ A strictly diagonally dominant matrix is invertible. The same holds if $\mathbf{A}$ is strictly diagonally dominant by columns, that is, if $\mathbf{A}^{\top}$ is strictly diagonally dominant.

Proof. Suppose $\mathbf{A}$ is strictly diagonally dominant. For every $i$ , $\lvert 0 - a_{ii}\rvert > r_i(\mathbf{A})$ , so $0 \notin D_i(\mathbf{A})$ . Hence $0$ lies in no row disc, and by Theorem 20.1.1 (a) it is not an eigenvalue. By Theorem 9.2.1, $0\mathbf{I} - \mathbf{A} = -\mathbf{A}$ is invertible, and so is $\mathbf{A}$ . If instead $\mathbf{A}^{\top}$ is strictly diagonally dominant, then $0$ lies in no column disc, and Theorem 20.1.1 (b) finishes in the same way.

This is the Lévy–Desplanques theorem. The word strictly carries the weight, and the definition asks it of every row. Examples: $\begin{psmallmatrix} 3 & 1 & 1 \\ 0 & 2 & 1 \\ 1 & -1 & 4 \end{psmallmatrix}$ is strictly dominant, since $3 > 2$ , $2 > 1$ , $4 > 2$ ; every diagonal matrix with non-zero diagonal is, since every radius is $0$ ; and a $1 \times 1$ matrix $(a)$ is strictly dominant exactly when $a \ne 0$ . A minimal change breaks it. $\begin{psmallmatrix} 1 & 1 \\ 1 & 1 \end{psmallmatrix}$ has $\lvert a_{ii}\rvert = 1 = r_i$ in both rows: it is dominant only weakly, and it is singular. The converse of the corollary is false: $\begin{psmallmatrix} 0 & 1 \\ 1 & 0 \end{psmallmatrix}$ is invertible and has zero diagonal. Diagonal dominance is a certificate of invertibility, cheap to check and often available, not a characterization.

20.1.4. Hermitian matrices, and intervals

For a Hermitian $\mathbf{A}$ the eigenvalues are real (Theorem 12.2.1), and so are the diagonal entries, since $a_{ii} = \overline{a_{ii}}$ . So only the part of each disc on the real line matters, which is the interval $[a_{ii} - r_i(\mathbf{A}),\, a_{ii} + r_i(\mathbf{A})]$ . Theorem 20.1.1 (a) then says $\min_i\bigl(a_{ii} - r_i(\mathbf{A})\bigr) \le \lambda_n(\mathbf{A}) \le \lambda_1(\mathbf{A}) \le \max_i\bigl(a_{ii} + r_i(\mathbf{A})\bigr) .$ For $\mathbf{A} = \begin{psmallmatrix} 4 & 1 & 0 \\ 1 & 6 & 2 \\ 0 & 2 & 9 \end{psmallmatrix}$ the intervals are $[3, 5]$ , $[3, 9]$ and $[7, 11]$ , so every eigenvalue lies in $[3, 11]$ , and $\mathbf{A}$ is positive definite by Theorem 13.1.5, since its eigenvalues are positive; Exercise C1 turns this into a general criterion. For a Hermitian matrix the row and column discs coincide, since $\lvert a_{ji}\rvert = \lvert\overline{a_{ij}}\rvert$ , so (b) adds nothing.

20.1.5. Scaling the discs

The discs depend on the matrix, and the eigenvalues depend only on its similarity class. So any similarity that is easy to compute gives new discs for the same eigenvalues. The cheapest one rescales the coordinates.

Proposition 20.1.3 (Rescaling the Gershgorin Discs)

Let $\mathbf{A} \in M_n(\mathbb{C})$ , let $d_1, \dots, d_n$ be positive real numbers, and $\mathbf{D} = \operatorname{diag}(d_1, \dots, d_n)$ . Then:

(a) $\mathbf{D}^{-1}\mathbf{A}\mathbf{D}$ has entries $a_{ij}d_j/d_i$ . It has the same diagonal as $\mathbf{A}$ , and the same eigenvalues with the same algebraic multiplicities.
(b) $r_i(\mathbf{D}^{-1}\mathbf{A}\mathbf{D}) = \dfrac{1}{d_i}\sum_{j \ne i}\lvert a_{ij}\rvert\,d_j$ for each $i$ .
(c) Every eigenvalue of $\mathbf{A}$ lies in $\bigcup_{i=1}^{n}\Bigl\{\, z : \lvert z - a_{ii}\rvert \le \frac{1}{d_i}\sum_{j \ne i}\lvert a_{ij}\rvert\,d_j \,\Bigr\} .$

Proof.

(a) $\mathbf{D}$ is invertible with $\mathbf{D}^{-1} = \operatorname{diag}(1/d_1, \dots, 1/d_n)$ , because every $d_i \ne 0$ . Multiplying by a diagonal matrix on the left scales rows and on the right scales columns, so $(\mathbf{D}^{-1}\mathbf{A}\mathbf{D})_{ij} = d_i^{-1}a_{ij}d_j$ , and for $i = j$ this is $a_{ii}$ . The matrices $\mathbf{A}$ and $\mathbf{D}^{-1}\mathbf{A}\mathbf{D}$ are similar, so they have the same characteristic polynomial (Theorem 7.10.3), hence the same eigenvalues with the same multiplicities.
(b) By (a) and $d_i, d_j > 0$ , $\lvert a_{ij}d_j/d_i\rvert = \lvert a_{ij}\rvert d_j/d_i$ ; sum over $j \ne i$ .
(c) Apply Theorem 20.1.1 (a) to $\mathbf{D}^{-1}\mathbf{A}\mathbf{D}$ and use (a) and (b).

Taking $d_1 > 1$ and the other $d_j = 1$ divides the first radius by $d_1$ and multiplies the entry $\lvert a_{i1}\rvert$ inside every other radius by $d_1$ . So scaling shrinks some discs at the expense of others, and the art is to shrink the disc we care about while the others can afford to grow. The same move appeared in Chapter 19 §09, where $\mathbf{D} = \operatorname{diag}(\mathbf{x})$ turned the entries of $\mathbf{B}\mathbf{x}$ into row sums.

Example (Separating a disc by scaling)

For $\mathbf{A} = \begin{pmatrix} 6 & 2 & 5 \\ 1 & -1 & 1 \\ 1 & 1 & -1 \end{pmatrix}$ of Example (Discs, eigenvectors, and where each eigenvalue sits), the row disc $D_1(\mathbf{A}) = \{\lvert z - 6\rvert \le 7\}$ overlaps $\{\lvert z + 1\rvert \le 2\}$ . Find a scaling $\mathbf{D} = \operatorname{diag}(d, 1, 1)$ whose row discs split into two disjoint groups, and find the range of $d$ that does it.

Solution. By Proposition 20.1.3 (b) with $d_1 = d$ and $d_2 = d_3 = 1$ , the scaled radii are $r_1 = \frac{2 + 5}{d} = \frac{7}{d}, \qquad r_2 = 1\cdot d + 1 = d + 1, \qquad r_3 = d + 1 ,$ with centers $6$ , $-1$ , $-1$ . The first disc is disjoint from the other two exactly when the distance $7$ between the centers exceeds the sum of the radii: $\frac{7}{d} + d + 1 < 7 \iff d^2 - 6d + 7 < 0 \iff 3 - \sqrt2 < d < 3 + \sqrt2 ,$ where we multiplied by $d > 0$ . For instance $d = 2$ gives $\mathbf{D}^{-1}\mathbf{A}\mathbf{D} = \begin{psmallmatrix} 6 & 1 & 5/2 \\ 2 & -1 & 1 \\ 2 & 1 & -1 \end{psmallmatrix}$ and the discs $\{\lvert z - 6\rvert \le \tfrac72\} \quad\text{and}\quad \{\lvert z + 1\rvert \le 3\} ,$ the second counted twice, which are disjoint since $\tfrac72 + 3 < 7$ . The eigenvalues $7$ , $-1$ , $-2$ are distributed one in the first disc and two in the second, as the figure shows.

$Diagram. Labels: scaled by mathrm diag(2,1,1), Row discs of the matrix of the example before and after scaling: the solid disc is centered\\ at 6, the dashed disc at -1 (rows 2 and 3), and the dots are the eigenvalues 7, -1, -2$

Scaling has bought a picture in which the eigenvalues fall into two groups, one near $6$ and two near $-1$ . What it has not yet bought is the statement that the first disc contains exactly one eigenvalue. Theorem 20.1.1 says only that the union holds all three, and nothing so far forbids all three from lying in the second disc. The counting statement is true, but it needs the eigenvalues to move continuously as the off-diagonal part is switched on, and §03 proves it. For a real matrix like this one, §03 will also show that an isolated disc centered on the real axis holds a real eigenvalue.

20.1.6. Eigenvalues on the boundary

Diagonal dominance fails for a matrix that matters. The second-difference matrix $\mathbf{K}_n$ of Chapter 19 §09 has $2$ on the diagonal and $-1$ beside it, so for $n \ge 3$ its interior rows have $\lvert a_{ii}\rvert = 2 = r_i(\mathbf{K}_n)$ . The discs $\lvert z - 2\rvert \le 2$ pass through $0$ , and Corollary 20.1.2 says nothing, although $\mathbf{K}_n$ is invertible. Only the first and last rows are strict. What rescues it is that the rows are linked: the dominant coordinate of an eigenvector cannot stay in the equality rows without spreading to the strict ones. The link is irreducibility, in the sense of Definition 19.2.3, and by Theorem 19.2.5 it means that the graph $G(\mathbf{A})$ , with an edge $j \to i$ whenever $a_{ij} \ne 0$ , is strongly connected.

Theorem 20.1.4 (Taussky’s Theorem)

Let $n \ge 1$ , let $\mathbf{A} \in M_n(\mathbb{C})$ be irreducible, and let $\lambda$ be an eigenvalue of $\mathbf{A}$ with $\lvert\lambda - a_{ii}\rvert \ge r_i(\mathbf{A}) \qquad\text{for **every** } i ,$ that is, $\lambda$ lies in no open disc $\{\lvert z - a_{ii}\rvert < r_i(\mathbf{A})\}$ . Then $\lvert\lambda - a_{ii}\rvert = r_i(\mathbf{A})$ for every $i$ : the eigenvalue lies on the boundary circle of every Gershgorin disc. Moreover, every eigenvector for $\lambda$ has all its coordinates of the same modulus. The hypothesis holds in particular when $\lambda$ is a boundary point (Definition 18.3.2) of $D_1(\mathbf{A}) \cup \dots \cup D_n(\mathbf{A})$ .

Idea. Run the proof of Theorem 20.1.1 at a peak index $k$ . The hypothesis $\lvert\lambda - a_{kk}\rvert \ge r_k$ makes the two ends of its chain of inequalities equal, so every inequality in the chain is an equality. The second one, $\sum_{j \ne k}\lvert a_{kj}\rvert\lvert x_j\rvert \le r_k\lvert x_k\rvert$ , is an equality only if $\lvert x_j\rvert = \lvert x_k\rvert$ whenever $a_{kj} \ne 0$ . So the set of peak indices is closed under following edges of $G(\mathbf{A})$ backwards. Strong connectivity then drags every index into it.

Proof. Let $\mathbf{A}\mathbf{x} = \lambda\mathbf{x}$ with $\mathbf{x} \ne \mathbf{0}$ , put $m = \max_j\lvert x_j\rvert > 0$ and $S = \{k : \lvert x_k\rvert = m\}$ , which is non-empty.

Claim. If $k \in S$ , then $\lvert\lambda - a_{kk}\rvert = r_k(\mathbf{A})$ , and every $j \ne k$ with $a_{kj} \ne 0$ lies in $S$ .

Proof. By the hypothesis and the chain of inequalities in the proof of Theorem 20.1.1, with $\lvert x_k\rvert = m$ , $r_k(\mathbf{A})\,m \le \lvert\lambda - a_{kk}\rvert\,m \le \sum_{j \ne k}\lvert a_{kj}\rvert\,\lvert x_j\rvert \le r_k(\mathbf{A})\,m .$ The two ends agree, so every inequality is an equality. The first gives $\lvert\lambda - a_{kk}\rvert = r_k(\mathbf{A})$ , after dividing by $m > 0$ . The last says $\sum_{j \ne k}\lvert a_{kj}\rvert\,(m - \lvert x_j\rvert) = 0$ . Each term is non-negative, so each is $0$ , and $a_{kj} \ne 0$ forces $\lvert x_j\rvert = m$ , that is, $j \in S$ .

Now let $i$ be any index and fix $k \in S$ . By Theorem 19.2.5, $G(\mathbf{A})$ has a walk $i = i_0, i_1, \dots, i_t = k$ . We show $i_s \in S$ for $s = t, t-1, \dots, 0$ . For $s = t$ this is $k \in S$ . If $i_s \in S$ with $s \ge 1$ , then $i_{s-1} \to i_s$ is an edge, so $a_{i_s i_{s-1}} \ne 0$ ; either $i_{s-1} = i_s \in S$ , or the Claim applied to $i_s$ puts $i_{s-1}$ in $S$ . Hence $i \in S$ . So $S = \{1, \dots, n\}$ : every coordinate of $\mathbf{x}$ has modulus $m$ , and the Claim gives $\lvert\lambda - a_{ii}\rvert = r_i(\mathbf{A})$ for every $i$ .

For the last sentence, suppose $\lvert\lambda - a_{ii}\rvert < r_i(\mathbf{A})$ for some $i$ , and put $\delta = r_i(\mathbf{A}) - \lvert\lambda - a_{ii}\rvert > 0$ . Every $z$ with $\lvert z - \lambda\rvert < \delta$ satisfies $\lvert z - a_{ii}\rvert \le \lvert z - \lambda\rvert + \lvert\lambda - a_{ii}\rvert < r_i(\mathbf{A})$ , so it lies in $D_i(\mathbf{A})$ and in the union. Then $\lambda$ is an interior point of the union, not a boundary point. This proves the theorem.

For $n = 1$ the theorem is empty but true: $r_1 = 0$ and the only eigenvalue is $a_{11}$ . For the all-ones matrix $\mathbf{J} \in M_n(\mathbb{C})$ , $n \ge 2$ , which is irreducible because every entry is non-zero, every disc is $\lvert z - 1\rvert \le n - 1$ , and the eigenvalue $n$ , with eigenvector $\mathbf{1}$ , satisfies $\lvert n - 1\rvert = n - 1$ : it lies on all of the boundary circles at once, and its eigenvector has equal coordinates, exactly as the theorem predicts.

The corollary is the one $\mathbf{K}_n$ needed: equality in most rows is allowed, provided one row is strict and the rows are linked.

Corollary 20.1.5 (Irreducible Diagonal Dominance Implies Invertibility)

Let $n \ge 1$ and let $\mathbf{A} \in M_n(\mathbb{C})$ be irreducible, with $\lvert a_{ii}\rvert \ge r_i(\mathbf{A}) \quad\text{for every } i, \qquad \lvert a_{ii}\rvert > r_i(\mathbf{A}) \quad\text{for **at least one** } i .$ Then $\mathbf{A}$ is invertible.

Proof. Suppose $\mathbf{A}$ is not invertible. By Theorem 9.2.1, $0$ is an eigenvalue. The first hypothesis says $\lvert 0 - a_{ii}\rvert \ge r_i(\mathbf{A})$ for every $i$ , so Theorem 20.1.4 applies to $\lambda = 0$ and gives $\lvert a_{ii}\rvert = r_i(\mathbf{A})$ for every $i$ . This contradicts the second hypothesis. Hence $\mathbf{A}$ is invertible.

Both hypotheses are needed. $\begin{psmallmatrix} 1 & 1 \\ 1 & 1 \end{psmallmatrix}$ is irreducible and weakly dominant, with no strict row, and it is singular: its eigenvalue $0$ lies on both circles $\lvert z - 1\rvert = 1$ . Exercise C2 shows that irreducibility cannot be dropped either.

Example (The second-difference matrix)

Show that $\mathbf{K}_n$ is invertible for every $n \ge 1$ , and that its eigenvalues lie in the open interval $(0, 4)$ .

Solution. For $n = 1$ , $\mathbf{K}_1 = (2)$ , with eigenvalue $2$ . Let $n \ge 2$ . (Chapter 19 §09 proved invertibility by exhibiting the inverse, Proposition 19.9.6; here the entries alone suffice.) The only non-zero entries off the diagonal are $a_{i,i+1} = a_{i+1,i} = -1$ , so $G(\mathbf{K}_n)$ has the edges $i \to i + 1$ and $i + 1 \to i$ , and walking along them reaches every vertex from every vertex. So $\mathbf{K}_n$ is irreducible by Theorem 19.2.5. Its rows have $r_1 = r_n = 1 < 2$ and, when $n \ge 3$ , $r_i = 2$ for $1 < i < n$ . So $\lvert a_{ii}\rvert \ge r_i$ everywhere, strictly in row $1$ , and $\mathbf{K}_n$ is invertible by Corollary 20.1.5.

$\mathbf{K}_n$ is real symmetric, so its eigenvalues are real, and by Theorem 20.1.1 (a) they lie in $\bigcup_i[2 - r_i, 2 + r_i] \subseteq [0, 4]$ . The value $0$ is excluded by invertibility. The value $4$ satisfies $\lvert 4 - 2\rvert = 2 \ge r_i$ for every $i$ , so if it were an eigenvalue, Theorem 20.1.4 would give $2 = r_1 = 1$ , which is false. Hence every eigenvalue lies in $(0, 4)$ . In particular $\mathbf{K}_n \succ 0$ , which Chapter 19 §09 obtained from its M-matrix structure.

Quick check. The all-ones matrix $\mathbf{J} \in M_3(\mathbb{C})$ is irreducible, and $0$ is an eigenvalue of it, since $\mathbf{J}$ has rank $1$ . But $0$ does not lie on the circle $\lvert z - 1\rvert = 2$ . Does this contradict Theorem 20.1.4?

Solution. No. The theorem applies only to an eigenvalue with $\lvert\lambda - a_{ii}\rvert \ge r_i(\mathbf{J})$ for every $i$ , and $\lvert 0 - 1\rvert = 1 < 2 = r_i(\mathbf{J})$ : the eigenvalue $0$ lies inside every open disc, so the hypothesis fails and the theorem says nothing about it. The other eigenvalue, $3$ , satisfies $\lvert 3 - 1\rvert = 2$ , and it does lie on every circle.

The picture to take away is this. The union of the discs holds the spectrum. An eigenvalue sits in the disc of the row where its eigenvector peaks. Scaling moves radius from one disc to another. And for an irreducible matrix, an eigenvalue can reach the outer edge of the union only by reaching the edge of every disc at once. §02 replaces the discs by other regions built from the same entries, and §03 counts the eigenvalues inside a group of discs.

20.1.7. Exercises

A. Check your understanding

Exercise (A1)

(a) Define the Gershgorin radius $r_i(\mathbf{A})$ and the disc $D_i(\mathbf{A})$ , and state Theorem 20.1.1, including the statement about the peak coordinate of an eigenvector.
(b) True or false: every Gershgorin disc of $\mathbf{A}$ contains an eigenvalue of $\mathbf{A}$ . Justify your answer.
(c) True or false: every eigenvalue of $\mathbf{A}$ lies in $\bigcup_i\bigl(D_i(\mathbf{A}) \cap D_i(\mathbf{A}^{\top})\bigr)$ . Justify your answer.
(d) True or false: an invertible matrix is strictly diagonally dominant by rows or by columns. Justify your answer.
(e) True or false: an irreducible matrix with $\lvert a_{ii}\rvert \ge r_i(\mathbf{A})$ for every $i$ is invertible. Justify your answer.
(f) Name the method of proof of Theorem 20.1.1 in one line.

Solution.

(a) $r_i(\mathbf{A}) = \sum_{j \ne i}\lvert a_{ij}\rvert$ and $D_i(\mathbf{A}) = \{z \in \mathbb{C} : \lvert z - a_{ii}\rvert \le r_i(\mathbf{A})\}$ . If $\mathbf{A}\mathbf{x} = \lambda\mathbf{x}$ with $\mathbf{x} \ne \mathbf{0}$ and $\lvert x_k\rvert = \max_j\lvert x_j\rvert$ , then $\lambda \in D_k(\mathbf{A})$ ; hence every eigenvalue lies in $\bigcup_i D_i(\mathbf{A})$ , in $\bigcup_i D_i(\mathbf{A}^{\top})$ , and in the intersection of these two unions.
(b) False. For $\begin{psmallmatrix} 0 & 1 \\ 4 & 0 \end{psmallmatrix}$ the eigenvalues are $\pm 2$ and the first disc is $\lvert z\rvert \le 1$ .
(c) False. For the same matrix both intersections are $\lvert z\rvert \le 1$ , which misses $\pm 2$ .
(d) False. $\begin{psmallmatrix} 0 & 1 \\ 1 & 0 \end{psmallmatrix}$ is invertible, and $\lvert a_{11}\rvert = 0 < 1$ both for rows and for columns.
(e) False. $\begin{psmallmatrix} 1 & 1 \\ 1 & 1 \end{psmallmatrix}$ is irreducible, with $\lvert a_{ii}\rvert = 1 = r_i$ , and singular. Corollary 20.1.5 needs one strict row.
(f) Choose the coordinate of the eigenvector of largest modulus, and apply the triangle inequality (Theorem 0.6.4) to that row of $\mathbf{A}\mathbf{x} = \lambda\mathbf{x}$ .

B. Practice

Exercise (B1: Deciding invertibility)

Determine which of the following matrices are invertible. Justify your answers, using the results of this section where they apply and a direct computation where they do not.

(a) $\begin{pmatrix} 5 & 2 & -2 \\ 1 & -4 & 2 \\ 0 & 3 & 4i \end{pmatrix}$
(b) $\begin{pmatrix} 3 & 1 & 2 \\ 1 & 3 & 1 \\ 1 & 1 & 3 \end{pmatrix}$
(c) $\begin{pmatrix} 2 & 1 & 1 \\ 1 & 2 & 1 \\ 1 & 1 & 2 \end{pmatrix}$
(d) $\begin{pmatrix} 1 & 1 & 0 \\ 1 & 1 & 0 \\ 0 & 1 & 2 \end{pmatrix}$

Solution.

(a) The radii are $4, 3, 3$ and the diagonal moduli $5, 4, \lvert 4i\rvert = 4$ , so every row is strictly dominant. The matrix is invertible by Corollary 20.1.2.
(b) Row $1$ has $3 = 1 + 2$ , and rows $2$ and $3$ have $3 > 2$ . Every off-diagonal entry is non-zero, so every edge $j \to i$ with $i \ne j$ is present in the graph, which is strongly connected, and the matrix is irreducible (Theorem 19.2.5). It is invertible by Corollary 20.1.5. (Indeed its determinant is $18$ .)
(c) Every row has $2 = 1 + 1$ : no row is strict, so neither corollary applies. Directly, the matrix is $\mathbf{I} + \mathbf{J}$ , and $\mathbf{J}\mathbf{1} = 3\cdot\mathbf{1}$ , while $\mathbf{J}\mathbf{v} = \mathbf{0}$ for $\mathbf{v} = (1, -1, 0)$ and $\mathbf{v} = (1, 0, -1)$ . So the eigenvalues of $\mathbf{I} + \mathbf{J}$ are $4, 1, 1$ , none zero, and the matrix is invertible, with determinant $4$ . The corollaries give sufficient conditions only.
(d) Rows $1$ and $2$ have equality and row $3$ is strict, but the matrix is singular: its first two rows are equal. The corollary does not apply because the matrix is reducible: column $3$ is zero outside row $3$ , so no edge leaves vertex $3$ , and there is no walk from $3$ to $1$ .

Exercise (B2: An interval for a symmetric matrix)

Let $\mathbf{A} = \begin{pmatrix} 5 & 1 & -1 \\ 1 & 3 & 1 \\ -1 & 1 & 6 \end{pmatrix}$ .

(a) Use Theorem 20.1.1 to find an interval containing every eigenvalue of $\mathbf{A}$ , and compare it with the interval $[-\left\| \mathbf{A} \right\|_{\infty}, \left\| \mathbf{A} \right\|_{\infty}]$ given by Corollary 16.4.2.
(b) Hence show that $\mathbf{A}$ is positive definite, and that $\det\mathbf{A}$ lies between $1$ and $8^3$ .

Solution.

(a) $\mathbf{A}$ is real symmetric, so its eigenvalues are real. The radii are $2, 2, 2$ , so the discs meet $\mathbb{R}$ in $[3, 7]$ , $[1, 5]$ , $[4, 8]$ , whose union is $[1, 8]$ . By Theorem 20.1.1 (a), every eigenvalue lies in $[1, 8]$ . The largest absolute row sum is $\left\| \mathbf{A} \right\|_{\infty} = 8$ , so Chapter 16’s bound gives only $[-8, 8]$ ; the upper ends agree, but only the discs see that the eigenvalues are positive.
(b) Every eigenvalue is at least $1 > 0$ , so $\mathbf{A} \succ 0$ by Theorem 13.1.5. The determinant is the product of the three eigenvalues, each in $[1, 8]$ , so $1 \le \det\mathbf{A} \le 8^3 = 512$ . (In fact $\det\mathbf{A} = 74$ .)

Exercise (B3: Choosing the scaling)

Let $\mathbf{A} = \begin{pmatrix} 7 & 4 & 4 \\ 1 & 0 & -1 \\ -1 & -2 & -1 \end{pmatrix}$ .

(a) Show that the row disc $D_1(\mathbf{A})$ meets the other two row discs.
(b) For $\mathbf{D} = \operatorname{diag}(d, 1, 1)$ with $d > 0$ , find the scaled radii, and find all $d$ for which the first scaled disc is disjoint from the other two.
(c) Check that $(-6, -1, 1)$ is an eigenvector of $\mathbf{A}$ , and that its eigenvalue lies in the first scaled disc for $d = 3$ .

Solution.

(a) The discs are $\lvert z - 7\rvert \le 8$ , $\lvert z\rvert \le 2$ and $\lvert z + 1\rvert \le 3$ . The point $0$ lies in the first two, and $-1$ in the first and third.
(b) By Proposition 20.1.3 (b), the radii of $\mathbf{D}^{-1}\mathbf{A}\mathbf{D}$ are $r_1 = 8/d$ , $r_2 = 1\cdot d + 1 = d + 1$ and $r_3 = 1\cdot d + 2 = d + 2$ , with centers $7, 0, -1$ . The first disc misses the second when $8/d + d + 1 < 7$ , and misses the third when $8/d + d + 2 < 8$ : both say $d + 8/d < 6$ . Multiplying by $d > 0$ , this is $d^2 - 6d + 8 < 0$ , that is, $(d - 2)(d - 4) < 0$ , so $2 < d < 4$ . At $d = 2$ the discs touch.
(c) Here $\begin{aligned} \mathbf{A}(-6, -1, 1) &= (-42 - 4 + 4,\ -6 + 0 - 1,\ 6 + 2 - 1) \\ &= (-42, -7, 7) = 7\,(-6, -1, 1) , \end{aligned}$ so $7$ is an eigenvalue. For $d = 3$ the first scaled disc is $\lvert z - 7\rvert \le \tfrac83$ , which contains $7$ . The eigenvector peaks at the first coordinate, so Theorem 20.1.1 already placed $7$ in $D_1$ ; the scaled theorem places it in the smaller disc.

C. Going deeper

Exercise (C1: Dominance and definiteness)

(a) Prove that a Hermitian matrix $\mathbf{A}$ with $a_{ii} > r_i(\mathbf{A})$ for every $i$ is positive definite.
(b) Prove that a Hermitian irreducible matrix with $a_{ii} \ge r_i(\mathbf{A})$ for every $i$ , strictly for at least one $i$ , is positive definite.
(c) Deduce that for every $n \ge 1$ and every real $t \ge 0$ , the matrix $\mathbf{K}_n + t\,\mathbf{e}_1\mathbf{e}_1^{\top}$ is positive definite.

Hint for (b): apply (a)’s argument to find where the eigenvalues can be, and then use Theorem 20.1.4.

Solution.

(a) The diagonal entries of a Hermitian matrix are real, and so are its eigenvalues (Theorem 12.2.1). By Theorem 20.1.1 (a), each eigenvalue $\lambda$ lies in some $D_k(\mathbf{A})$ , so $\lambda \ge a_{kk} - \lvert\lambda - a_{kk}\rvert \ge a_{kk} - r_k(\mathbf{A}) > 0$ . A Hermitian matrix with only positive eigenvalues is positive definite (Theorem 13.1.5).
(b) As in (a), every eigenvalue satisfies $\lambda \ge a_{kk} - r_k(\mathbf{A}) \ge 0$ for some $k$ , so it is enough to show that $0$ is not an eigenvalue. The hypothesis gives $\lvert 0 - a_{ii}\rvert = a_{ii} \ge r_i(\mathbf{A})$ for every $i$ , since $a_{ii} \ge r_i(\mathbf{A}) \ge 0$ . If $0$ were an eigenvalue, Theorem 20.1.4 would give $a_{ii} = r_i(\mathbf{A})$ for every $i$ , contradicting the strict row. Hence all eigenvalues are positive and $\mathbf{A} \succ 0$ . (This is also Corollary 20.1.5, together with the sign information from (a).)
(c) The matrix is real symmetric, and it differs from $\mathbf{K}_n$ only in the $(1,1)$ entry, which is $2 + t$ . The graph is unchanged, so for $n \ge 2$ it is irreducible, as shown in Example (The second-difference matrix). Its rows satisfy $a_{ii} \ge r_i$ , with $2 + t > 1$ in row $1$ . By (b), it is positive definite. For $n = 1$ the matrix is $(2 + t)$ with $2 + t > 0$ .

Exercise (C2: Irreducibility cannot be dropped)

(a) Give a $3 \times 3$ reducible matrix with $\lvert a_{ii}\rvert \ge r_i(\mathbf{A})$ for every $i$ , strictly in at least one row, that is singular. Which step of the proof of Theorem 20.1.4 fails for it?
(b) Let $\mathbf{A}$ be irreducible and let $\lambda$ be an eigenvalue with $\lvert\lambda - a_{ii}\rvert \ge r_i(\mathbf{A})$ for every $i$ . Prove that the eigenspace $E_\lambda(\mathbf{A})$ has dimension $1$ .

Hint for (b): given two independent eigenvectors, form a combination with a zero coordinate.

Solution.

(a) Take $\mathbf{A} = \begin{psmallmatrix} 1 & 1 & 0 \\ 1 & 1 & 0 \\ 0 & 1 & 2 \end{psmallmatrix}$ from Exercise (B1: Deciding invertibility) (d): rows $1$ and $2$ have equality, row $3$ is strict, and the first two rows are equal, so $\mathbf{A}$ is singular. The eigenvector $\mathbf{x} = (1, -1, \tfrac12)$ for $0$ has $\mathbf{A}\mathbf{x} = (0, 0, -1 + 1) = \mathbf{0}$ . Its peak set is $S = \{1, 2\}$ , and the Claim of the proof holds: the rows in $S$ have equality and their off-diagonal non-zero entries point into $S$ . What fails is the spreading step. There is no walk from $3$ to $1$ in $G(\mathbf{A})$ , so nothing forces $3 \in S$ , and the strict row $3$ is never reached.
(b) Suppose $\mathbf{x}$ and $\mathbf{y}$ are linearly independent eigenvectors for $\lambda$ . Since $\mathbf{y} \ne \mathbf{0}$ , choose $i$ with $y_i \ne 0$ , and put $\mathbf{z} = \mathbf{x} - (x_i/y_i)\mathbf{y}$ . Then $\mathbf{z} \ne \mathbf{0}$ , by independence, and $\mathbf{A}\mathbf{z} = \lambda\mathbf{z}$ , so $\mathbf{z}$ is an eigenvector for $\lambda$ with $z_i = 0$ . But by Theorem 20.1.4 every eigenvector for $\lambda$ has all coordinates of the same modulus, which is positive because the vector is non-zero. This contradiction shows $\dim E_\lambda(\mathbf{A}) \le 1$ , and $\dim E_\lambda(\mathbf{A}) \ge 1$ because $\lambda$ is an eigenvalue.