Gershgorin's theorem

Theorem (Linear Algebra): Let A be a complex-valued square matrix. All of the eigenvalues of A lie inside discs centered at the diagonal entries a_ii of A, with radii equal to the sum of the absolute values of the non-diagonal elements in the respective row.

Formally: If λ is an eigenvalue of a matrix A which has entries a_ij then:

              ----
              \     
 |arr - λ| <=  /   |ari|
              ----
              i!=r

Gershgorin's theorem is remarkably useful in numerical analysis for placing a priori bounds on the location of eigenvalues. As a trivial example, it can be used as a one-line proof that a "diagonally dominant" matrix (one for which the diagonal element in each row is larger than the sum of the absolute values of its rest of its row) is invertible: if this is true, then by Gershgorin every eigenvalue lies in a disc that is bounded away from 0. Thus, the matrix has no zero eigenvalues, and is therefore nonsingular.

Proof: split A into D + F, where D contains only the diagonal terms of A, and F contains only the off-diagonal terms. If λ is an eigenvalue of A then Av = λv for some eigenvector v. Substitute the splitting A = D + F above:

(D + F)v = λv                        (1)

We can normalize v so that the infinity norm of v (its largest element) is = 1. This will be true for some element v_r. Equating the elements on the left and the right of (1) we get:

a_rr + (f_r,v) = λ

where fr is row r of F, and (fr,v) is an inner product. Rearranging and taking norms on both sides we get:

| λ - a_rr | = | (f_r,v) | <= | f_r |₁ * | v |_inf = | f_r |₁

since we normalized v so that | v |_inf = 1. This is the bound we wanted, and we're done.

A variant of the Gershgorin argument produces an even more interesting result: for every eigenvalue λ of A there exists indices r, s for which

| λ - a_rr | * | λ - a_ss | <= S_r * S_s

Where S_r and S_s are the sums of the off-diagonal terms in rows r and s, respectively.

This is remarkable, as λ need lie inside only one of the Gershgorin discs; if it lies in the disc around a_rr it may be quite far away from the center of disc s, but this says that the farther away it gets from the center of the other disc, the closer it will be to the center of the disc in which it is contained. The resulting areas are called "Ovals of Cassini" and are important in Geometry.