Gershgorin circle theorem

1 Basic Definitions and Setup

1.1 Eigenvalues in the Complex Plane

For a complex square matrix \(A\), an eigenvalue is a complex number \(\lambda\) such that there exists a nonzero vector \(v\) with \(Av=\lambda v\). The set of eigenvalues of \(A\) is finite and, in general, can occupy various regions of the complex plane. The Gershgorin circle theorem gives enclosure regions for these eigenvalues using only the matrix entries, rather than solving for eigenvalues directly.

1.2 Complex Square Matrices and Notation

Let \(A=(a_{ij})\in \mathbb{C}^{n\times n}\). Indices satisfy \(i,j\in\{1,2,\dots,n\}\). The diagonal entries are \(\{a_{11},a_{22},\dots,a_{nn}\}\), and the remaining entries \(a_{ij}\) for \(i\neq j\) form the off-diagonal part.

1.3 Diagonal Entries and Off-Diagonal Magnitudes

The theorem uses absolute values of off-diagonal entries in each row or each column. These magnitudes measure how strongly the \(i\)-th coordinate couples to other coordinates through \(A\). The diagonal term \(a_{ii}\) acts as the center location for a corresponding disk in the complex plane.

1.4 Row and Column Sums of Absolute Values

Two quantities are fundamental:

Row sums of off-diagonal magnitudes:

R_i=\sum_{\substack{j=1\\ j\neq i}}^{n}	a_{ij}	.

Column sums of off-diagonal magnitudes:

C_j=\sum_{\substack{i=1\\ i\neq j}}^{n}	a_{ij}	.

\] These radii determine the size of Gershgorin disks in the row and column versions of the theorem.

2 Statement of the Gershgorin Circle Theorem

2.1 Row Version (Gershgorin Disks from Rows)

2.1.1 Construction of Row Gershgorin Disks

For each \(i\in\{1,\dots,n\}\), define the row Gershgorin disk \[

D_i=\{z\in\mathbb{C}:	z-a_{ii}	\le R_i\}.

\] Here, \(a_{ii}\) is the disk center, and \(R_i\) is the radius obtained by summing absolute values of the off-diagonal entries in row \(i\).

2.1.2 Eigenvalue Containment in Row Disks

The row Gershgorin theorem states: every eigenvalue \(\lambda\) of \(A\) lies in at least one of the disks \(D_i\). Equivalently, the spectrum \(\sigma(A)\) is contained in the union \[ \sigma(A)\subseteq \bigcup_{i=1}^{n} D_i. \] This enclosure holds without additional structural assumptions.

2.2 Column Version (Gershgorin Disks from Columns)

2.2.1 Construction of Column Gershgorin Disks

For each \(j\in\{1,\dots,n\}\), define the column Gershgorin disk \[

\widetilde{D}_j=\{z\in\mathbb{C}:	z-a_{jj}	\le C_j\},

\] where \(C_j\) is the off-diagonal magnitude sum in column \(j\).

2.2.2 Eigenvalue Containment in Column Disks

Similarly, every eigenvalue \(\lambda\) of \(A\) lies in at least one column disk, so \[ \sigma(A)\subseteq \bigcup_{j=1}^{n} \widetilde{D}_j. \] Thus, either row-based or column-based information can be used to bound spectral locations.

2.3 Relationship Between Row and Column Forms

The row and column versions apply the same geometric idea—disks centered at diagonal entries—but use different radii derived from different orientations of the matrix. Since \(C_j\) for \(A\) equals \(R_j\) for \(A^\top\) (up to conjugation conventions), the column statement can be viewed as a row statement for a related transpose. In practice, one version may yield tighter disks depending on whether row or column off-diagonal couplings dominate.

3 Geometric Interpretation

3.1 Viewing Disks and Their Unions

Each Gershgorin disk is a closed disk in the complex plane, and the theorem asserts that the spectrum is trapped within the union of these disks. The centers track the diagonal entries, while the radii reflect how much the corresponding row or column is “perturbed” away from being purely diagonal.

3.2 Intersections and Overlaps of Gershgorin Disks

Disks can overlap substantially. When multiple disks cover the same region, the union gives only coarse localization: a given eigenvalue that lies in an overlap area may have no unique disk membership based on the enclosure alone.

3.3 Interpreting Disk Separation

When disks are well separated—especially when one disk lies far from all others—each eigenvalue must align with the disk that contains its neighborhood. Separation improves interpretability: it becomes more plausible to associate particular eigenvalues with particular diagonal-dominance patterns in the matrix.

3.4 Tightness and Heuristic Meaning of Disk Radii

Large radii correspond to strong off-diagonal activity, producing loose bounds. Small radii suggest that the matrix is close to diagonal in that row or column, which typically leads to more informative spectral enclosures. Although Gershgorin disks are not always tight, the radii provide a heuristic measure of how strongly off-diagonal entries can shift eigenvalues away from diagonal values.

4 Counting Eigenvalues Using Disk Clustering

4.1 Multiplicity Correspondence to Disk Coverage

Beyond containment, Gershgorin theory can be used to count eigenvalues in clusters. Under suitable separation conditions, the number of eigenvalues (counted with algebraic multiplicity) inside a group of disks matches the number of disks in that group, reflecting how eigenvalues cannot “escape” beyond the union barriers created by disk gaps.

4.2 Disks Isolated from Others

Suppose a subset of disks lies at a positive distance from the remaining disks. Then eigenvalues associated with those isolated regions can be separated from eigenvalues belonging to other regions. The isolation gap serves as a geometric barrier that prevents eigenvalues from crossing between groups.

4.3 Eigenvalue Localization for Isolated Clusters

When disks split into distinct clusters with non-overlapping unions, eigenvalues localize according to the cluster membership. In such cases, one can identify how many eigenvalues fall into each cluster by analyzing the corresponding disk unions.

4.4 Examples of Eigenvalue Counting by Disk Groups

Consider a matrix whose row disks consist of two well-separated clusters. The theorem’s counting refinements imply that eigenvalues cannot mix between these clusters, allowing a partition of the spectrum into two groups whose sizes equal the counts of disks within each cluster. The precise statements typically rely on lower bounds for the distance between cluster unions and do not require explicit eigenvalue computation.

5 Consequences and Corollaries

5.1 Sufficient Conditions for Nonsingularity

5.1.1 Strict Diagonal Dominance Implications

If a matrix is strictly diagonally dominant by rows, meaning \[

a_{ii}	>\sum_{j\ne i}	a_{ij}	\quad \text{for all } i,

\] then \(0\) cannot belong to any row Gershgorin disk. Since every eigenvalue lies in the union of these disks, it follows that \(0\) is not an eigenvalue; hence \(A\) is nonsingular.

5.1.2 More General Dominance Conditions

More general versions allow dominance to be formulated with additional structure, such as dominance relative to a particular shift. For example, applying the theorem to \(A-\mu I\) yields criteria guaranteeing that no eigenvalue equals \(\mu\). This provides a way to certify invertibility of shifted matrices based on entrywise bounds.

5.2 Positive Definiteness and Spectral Location (Matrix-Property Links)

For Hermitian matrices, eigenvalues are real, so Gershgorin disks can be interpreted as real intervals with endpoints derived from diagonal entries and row or column radii. While Gershgorin alone does not fully characterize positive definiteness, it can offer sufficient conditions: if all disks lie strictly in the positive real half-line (for Hermitian \(A\)), then all eigenvalues are positive, implying positive definiteness.

5.3 Bounds on Spectral Radius

The spectral radius \(\rho(A)=\max\{	\lambda	:\lambda\in\sigma(A)\}\) can be bounded by the disks’ geometry. If a disk is centered at \(a_{ii}\) with radius \(R_i\), then any eigenvalue within that disk satisfies

\lambda	\le	a_{ii}	+R_i.

\] Taking the maximum over \(i\) yields an explicit computable upper bound on \(\rho(A)\).

In numerical analysis, spectral location is tied to stability of linear dynamics (e.g., whether iterates contract). Gershgorin-based bounds can serve as entrywise tests: if disks are contained in a region known to correspond to stable eigenvalues (such as lying strictly away from the origin for invertibility or within a disk of radius less than one for contraction in certain contexts), then stability can be concluded without computing eigenvalues.

6.1 Improved Gershgorin-Type Bounds

Refinements modify how radii are computed so that the resulting inclusion set better tracks the spectrum. One common theme is to apply Gershgorin to transformed matrices or to redistribute coupling strengths, producing disks that can be smaller than the basic row/column disks.

6.2 Inclusion Sets for Eigenvalues of Submatrices

A variant applies Gershgorin-style reasoning to principal submatrices. By restricting attention to a subset of indices, one can bound eigenvalues of that submatrix in terms of its own diagonal and off-diagonal magnitudes. This is useful in structured computations where local spectral information is required.

6.3 Scaled/Weighted Gershgorin Theorem (Diagonal Similarity)

A powerful refinement introduces positive weights (or equivalently applies a diagonal similarity transform). If one replaces \(A\) by a scaled matrix \(D^{-1}AD\) with an invertible diagonal \(D\), the diagonal entries remain the same while radii change to reflect weighted off-diagonal couplings. Choosing weights strategically can reduce overestimation and provide tighter disks.

6.4 Tightening via Choice of Weights or Transformations

Different weight choices can yield different disk families; tighter enclosures often arise when the weights match the matrix’s anisotropy. In computational settings, optimization over weights can be used to minimize the union’s extent or to enforce stronger separation between disk clusters.

7 Applications in Numerical Linear Algebra

7.1 Estimating Eigenvalue Regions Without Full Computation

Eigenvalue computation can be expensive for large matrices. Gershgorin disks provide quick region estimates from raw data, which helps determine whether iterative methods are likely to converge and whether a matrix is close to singular.

7.2 Error Control and Conditioning Intuition

Small changes in entries can shift eigenvalues. If the origin is far from all Gershgorin disks, then \(A\) is likely well-conditioned with respect to invertibility (in a qualitative sense). Conversely, disks that come near \(0\) indicate potential sensitivity, guiding choices such as regularization.

7.3 Iterative Methods and Diagonal Dominance Assumptions

Many stationary iterative schemes rely on diagonal dominance or related properties to ensure convergence. Since dominance can be checked entrywise, Gershgorin provides a direct link between diagonal dominance and the spectral behavior underpinning convergence.

7.4 Detecting Structural Issues in Matrix Data

Data-driven matrices—such as those arising from discretizations or network models—may contain poorly scaled or unexpectedly large off-diagonal couplings. Disk plots can reveal when diagonal entries do not adequately dominate, indicating that a computation may require preconditioning or reformulation.

8 Worked Examples

8.1 Constructing Disks for a 2×2 Matrix

Let \[ A=\begin{pmatrix} a_{11} & a_{12}\\ a_{21} & a_{22} \end{pmatrix}. \]

Row radii are \(R_1=	a_{12}	\) and \(R_2=	a_{21}	\). Thus the row disks are

D_1=\{z:	z-a_{11}	\le	a_{12}	\},\quad
D_2=\{z:	z-a_{22}	\le	a_{21}	\}.

\] The theorem implies each eigenvalue lies in \(D_1\cup D_2\). For a \(2\times 2\) matrix, one can compare this enclosure with the exact eigenvalues computed from the characteristic polynomial.

8.2 Constructing Disks for a 3×3 Matrix

For \[ A=(a_{ij})_{i,j=1}^3, \] the row disks use radii \[

R_1=	a_{12}	+	a_{13}	,\quad
R_2=	a_{21}	+	a_{23}	,\quad
R_3=	a_{31}	+	a_{32}	.

\] Each disk is centered at the corresponding diagonal entry \(a_{ii}\). Plotting the three disks gives an immediate visual region containing all three eigenvalues.

8.3 Demonstrating Eigenvalue Localization with Disk Separation

Suppose two of the disks form a cluster near one diagonal entry, while the third disk is separated and does not intersect the cluster. The separation implies that one eigenvalue is contained in the isolated disk region, while the remaining eigenvalues lie in the union of the clustered disks. This provides a qualitative eigenvalue “assignment” guided solely by disk geometry.

Let \(D\) be a diagonal matrix with nonzero diagonal entries chosen to balance magnitudes of off-diagonal terms. Consider \(B=D^{-1}AD\). The diagonal of \(B\) matches that of \(A\), but the off-diagonal contributions change, altering the radii. Recomputing Gershgorin disks for \(B\) can reduce overlap and tighten the spectral enclosure compared with the unweighted row disks of \(A\).

9 Limitations and Practical Considerations

9.1 Cases Where Disks Are Too Loose

If off-diagonal magnitudes are large in many rows or columns, radii become substantial and disks overlap heavily. In such situations, the union may cover a large portion of the plane, offering weak localization even though the theorem remains correct.

9.2 When Overlaps Reduce Localization Power

Overlapping disks can obscure which disk contains which eigenvalue. Even when the spectrum is structured, overlaps can prevent the counting-by-cluster interpretation from being informative.

9.3 Floating-Point and Computation of Radii

Radii involve sums of absolute values. In finite precision arithmetic, cancellation does not occur in the same way as for signed sums, but rounding can still affect bounds. Careful implementation should use appropriate numeric types and consider scaling to avoid overflow or underflow when entries have extreme magnitudes.

9.4 How to Choose Between Row and Column Forms

The tighter inclusion set depends on whether row off-diagonal totals or column off-diagonal totals are smaller relative to diagonal terms. When matrix data indicate stronger coupling in one orientation (e.g., column-dominant behavior), using the corresponding Gershgorin form can provide better-enclosed regions.

10 Exercises and Further Reading

10.1 Problem Set: Computing Gershgorin Disks

Compute the row and column Gershgorin disks for given matrices and sketch the resulting unions. For each case, identify which disks include the origin and determine whether nonsingularity can be concluded via diagonal dominance-type criteria.

10.2 Problem Set: Eigenvalue Counting in Clusters

Construct examples where Gershgorin disks form two well-separated groups. Determine, using disk clustering conditions, how many eigenvalues lie in each group, and compare with exact eigenvalues for small matrices.

10.3 Problem Set: Nonsingularity via Dominance

For a set of matrices, test nonsingularity using strict diagonal dominance by rows or columns, and also using shifted versions \(A-\mu I\). Discuss which choice of shift yields the strongest conclusion.

10.4 References and Standard Sources

Consult standard texts in matrix analysis and numerical linear algebra for proofs, refinements (including weighted versions), and applications to invertibility and spectral bounds. Look for sections covering Gershgorin’s theorem, diagonal similarity refinements, and eigenvalue localization results.