Past exam of the numerical analysis course of the University of Oxford / 2014 / 3

The Gershgorin circle theorem states that every eigenvalue of $A=(a_{ij})\in {\mathbb{R}}^{n\times n}$ belongs to at least one of the closed Gershgorin discsThe eigenvalue may be complex even though the matrix is real. To prove the theorem, choose a nonzero complex eigenvector $v$ with $Av=\lambda v$ and an index $i$ at which $|v_i|$ is maximal. Then $|v_i|>0$, and the $i$th row givesThe triangle inequality yieldsThus $\lambda \in D_i$, proving the assertion without any symmetry assumption.

The second theorem, or Gershgorin eigenvalue counting, states: if a union of $k$ indexed Gershgorin discs is disjoint from all remaining discs, it contains exactly $k$ eigenvalues, counted with algebraic multiplicity. In particular, an isolated Gershgorin disc contains exactly one simple eigenvalue. The separation condition is essential; merely drawing overlapping discs does not assign one eigenvalue to each.

The determinant is invariant under transpose. Therefore the characteristic polynomials coincide:Their polynomial roots, including their algebraic multiplicities, are the same, so $A$ and $A^T$ have the same eigenvalues. This allows column sums as well as row sums to supply Gershgorin discs for the same spectrum.

The first row has off-diagonal sum $a_{12}<1/4$. Rows $2,\dots ,n-1$ have sums less than $1/2$, and the last row has sum $c+a_{n,n-1}<5/4$, since $0<c<1$. Every row except the second therefore has its Gershgorin disc strictly away from zero: its centre is at least one in the first row and at least three in the remaining rows.

For the second row, an exact sufficient condition is $|b|>a_{21}+a_{23}$. Since the sum is strictly below $1/2$, the coefficient-independent boundsguarantee that zero is outside every Gershgorin disc. Consequently zero is not an eigenvalue and $A$ is an invertible matrix. Equality at $\pm 1/2$ is allowed because the off-diagonal entry bounds are strict. These are sufficient strict diagonal dominance bounds; values of $b$ between them can also give invertible matrices.

Put $n=2m$. With $b=2$, the row Gershgorin discs have centres $1,2,\dots ,n$ and radiiApplying the theorem to the transpose gives column Gershgorin discs with radiiThe enlarged disc moves from the last centre to the first centre. All small discs in either family are mutually disjoint, because adjacent centres are one unit apart and their radii have sum strictly below one.

For the row family, the small disc at any $i\le m$ is also disjoint from the enlarged disc at $n$ ifFor the column family, every small disc at $i\ge m+1$ is disjoint from the enlarged disc at $1$ by the same estimate, since $i-1\ge m$. Thus the Gershgorin eigenvalue counting theorem certifies one simple eigenvalue near each of $1,\dots ,m$ from rows, and near each of $m+1,\dots ,n$ from columns. The certified small discs from the two families are themselves disjoint, so these are $n$ different eigenvalues.

The largest nonnegative $c$ certified by these uniform row-and-column separation bounds isMore generally the argument works for $|c|\le c_{\mathrm{G}}$. The endpoint is included because all actual entry bounds, and hence all actual radius estimates above, are strict. For $n=8$, $c_{\mathrm{G}}=13/4$: row discs isolate centres $1,2,3,4$, and column discs isolate centres $5,6,7,8$.

For $c>c_{\mathrm{G}}$, taking the adjacent entries sufficiently close to $1/4$ makes the enlarged row disc meet the small disc at $m$, and the enlarged column disc meet the small disc at $m+1$. Hence this particular uniform disc-separation certificate stops there. This is a Gershgorin guarantee, not a necessary spectral threshold: failure of disc separation does not prove repeated or nonreal eigenvalues for the actual matrix.

Finally, a real matrix has nonreal eigenvalues in complex conjugate pairs. Every certified small disc has a real centre and is invariant under conjugation. A nonreal eigenvalue in it would bring its distinct conjugate into the same disc, contradicting its count of exactly one. Therefore all the certified eigenvalues are real and simple. The two-family argument is Complementary row and column Gershgorin isolation.

Strict diagonal dominance givesThus every $b_{ii}\ne 0$, and the diagonal matrix $D$ has inverse $D^{-1}=\mathrm{diag}(1/b_{11},\dots ,1/b_{nn})$. The iteration matrix has entriesEach row Gershgorin disc for $T$ is centred at zero and has radiusTherefore every eigenvalue of $T$ satisfiesEquivalently, the induced matrix norm satisfies $\Vert T{\Vert }_{\infty }<1$, bounding the spectral radius. This is the usual Jacobi convergence from strict diagonal dominance; the Jacobi error matrix is $-T$, with the same eigenvalue magnitudes.