A matrix and its transpose have the same characteristic polynomial, allowing two independent Gershgorin eigenvalue counting arguments for one spectrum. If isolated row discs certify simple eigenvalues near one group of centres and isolated column discs certify the remaining ones, pairwise separation of all the certified small discs establishes a simple spectrum even if neither full family has pairwise disjoint discs.
For example, let , the diagonal centres be , and all adjacent off-diagonal entries have magnitude strictly below . Add a corner entry . The row radii are below ; the column radii reverse the two endpoint bounds. If , rows isolate centres and columns isolate centres . The nearest potentially enlarged-disc contact has centre separation , while the radius sum is strictly less than . Each of the certified small discs contains one simple eigenvalue. For real entries these eigenvalues are real, since a nonreal conjugate pair would put two roots in the same conjugation-invariant isolated disc.
This is a sufficient uniform certificate. Overlap beyond this bound does not prove repeated eigenvalues; individual matrices can have simple real spectra well beyond a Gershgorin disc separation bound.
A positive diagonal matrix , with , is an invertible matrix and changes the coordinate scales through the similarity transformation . Its diagonal entries are still , while . Thus the Gershgorin discs have the same centres but different radii. Matrix similarity preserves the characteristic polynomial and eigenvalues, so the original and scaled disk unions are both valid bounds and may be intersected. Suitable scaling can compensate for badly unbalanced off-diagonal entries; it need not shrink every radius.[ref]
For example,
The original Gershgorin discs are and . Their union is simply the huge first disk; the small second disk contains no eigenvalue. After scaling, both radii are , giving or . The two Gershgorin discs overlap, so their individual eigenvalue counts are not certified. The scaled matrix is a real symmetric matrix, however, so matrix similarity now proves that the original matrix has real eigenvalues in and is an invertible matrix. Directly, both matrices have characteristic polynomial , hence
The scaling changes the available bounds, while these eigenvalues stay fixed.
Figure 1.
Diagonal similarity scaling replaces a radius-100 Gershgorin disc by two radius-1 discs while preserving both eigenvalues
. Details.
For a real symmetric matrix, or more generally a Hermitian matrix, the finite-dimensional spectral theorem makes all eigenvalues real. Intersecting its Gershgorin discs with the real axis gives
The union preserves gaps that the single outer interval loses. If every , all eigenvalues are positive, so the matrix is a positive-definite matrix. This is the positive-diagonal strictly diagonally dominant matrix criterion. For the three-by-three example, gives a positive-definite matrix certificate and bounds its spectral condition number of a positive-definite matrix by ; the computed value is about .
Strictness matters. The symmetric matrix has positive diagonal and is a diagonally dominant matrix, but its eigenvalues are and : it is singular. For a general complex matrix, the condition only puts the eigenvalues in the open right half-plane. The Hermitian matrix assumption is what converts that statement into positive definiteness.
Gershgorin circle theorem Created 2026-09-24 Updated 2026-10-18
The Gershgorin circle theorem locates every eigenvalue of a square matrix using only its entries. A diagonal entry supplies a centre in the complex plane, and the sum of the off-diagonal absolute values in its row supplies a radius. Small off-diagonal couplings therefore confine the eigenvalues near the diagonal entries. This turns a global eigenvalue problem into a picture built one row at a time.
Precisely, let , with , and define the closed Gershgorin discs
Every eigenvalue of satisfies , including eigenvalues on the boundaries. No symmetry or diagonalizability is required. Despite the name, the theorem uses filled disks, not just their circular boundaries.[ref]
The short reason is the triangle inequality. For a nonzero eigenvector with , choose with . The th row gives
Thus the largest eigenvector coordinate identifies a Gershgorin disc containing , even though that eigenvector need never be computed to use the bound.
This is useful when a full eigenvalue computation would be expensive: forming the Gershgorin discs needs one pass over the nonzero entries of a sparse matrix. If lies outside every Gershgorin disc, then is an invertible matrix, since zero is not an eigenvalue. The condition is exactly in every row, namely strict diagonal dominance. This connects diagonal dominance to solvability of a linear system; the inverse infinity-norm bound from diagonal dominance adds a quantitative bound. It is a sufficient test: failure to exclude zero does not prove singularity.
For a concrete symmetric matrix, take
The three Gershgorin discs have centres and are pairwise disjoint. The finite-dimensional spectral theorem makes the eigenvalues real, so their possible locations reduce to the intervals , , and . Gershgorin eigenvalue counting gives exactly one eigenvalue in each. Independently, the characteristic polynomial is
whose numerical polynomial roots are , , and , rounded to six decimal places. All are positive, as Gershgorin bounds for symmetric matrices already guarantee without finding those polynomial roots.
Figure 1.
Three separated Gershgorin discs, each containing one real eigenvalue of the symmetric example
. Details.
S. Gerschgorin published the result in 1931 in Über die Abgrenzung der Eigenwerte einer Matrix, in the Bulletin de l'Académie des Sciences de l'URSS, issue 6, pages 749–754. The original paper's §2 states both eigenvalue inclusion and counting in separated groups of Gershgorin discs; §3 already discusses column bounds and transformations preserving the eigenvalues. Thus both the localization picture and ways to sharpen it were part of the original development.[ref]
Gershgorin disc Created 2026-10-06 Updated 2026-10-31
A row Gershgorin disc of a square matrix is the closed disk in the complex plane with centre and radius . A zero radius gives a single point. The Gershgorin disc theorem places every eigenvalue in the union of these disks. For a Hermitian matrix, the real intervals cut out by the Gershgorin discs bound the eigenvalues, including energy levels when the matrix represents a Hamiltonian operator.
Applying the Gershgorin circle theorem to the transpose gives column Gershgorin discs with the same centres and radii . Since and have the same characteristic polynomial, every eigenvalue lies in the intersection of the row-disc union and the column-disc union. This is an intersection of two unions; one cannot generally replace each row radius by . An isolated row Gershgorin disc contains exactly one eigenvalue by Gershgorin eigenvalue counting.[ref]
Let be a connected component of the union of the row Gershgorin discs of an matrix. If comprises of the indexed Gershgorin discs, then it contains exactly eigenvalues, counted with algebraic multiplicity. Coincident disks still count separately, once for each row. In particular, a Gershgorin disc disjoint from all the others contains one simple eigenvalue. More generally, any union of indexed Gershgorin discs disjoint from the remaining contains exactly eigenvalues, whether or not that union is connected.[ref]
The separation is essential: overlapping Gershgorin discs do not individually promise one eigenvalue each. Discs that touch at a boundary point belong to the same connected component. For example, the matrix has Gershgorin discs of radii with centres . The component around comprises two indexed disks and contains the eigenvalue with algebraic multiplicity two; the isolated point at contains the remaining eigenvalue.
For intuition, continuously turn on the off-diagonal entries using the diagonal matrix and , . At the eigenvalues are the disk centres; at every later time the Gershgorin discs stay inside their final union. The continuity of the eigenvalues as a collection means that no eigenvalue can cross a gap between final components. The count gives a useful certificate that an eigenvalue cluster is complete.[ref]
To exclude zero as an eigenvalue of , it is enough that every row has positive real diagonal entry exceeding the sum of the absolute values of its off-diagonal entries. All Gershgorin discs then lie strictly in the right half-plane. For
the three diagonal-dominance margins of are , all positive for . Thus is nonsingular for negative real . Working with the pencil directly avoids computing either a determinant polynomial or .
Gershgorin gap bound for an adiabatic history path Created 2026-10-06 Updated 2026-11-05
For in the unary history subspace, the first Gershgorin disc lies in and every other disc has real part at least . For , the first disc is isolated and contains the unique ground state energy. Thus the spectral gap is at least , in particular at least for .
A symmetric matrix obtained from a conservative five-point discretization of a diffusion equation has row centre and radius at most , where is the grid spacing and is the sum of its four nonnegative edge coefficients. Here the matrix represents the diffusion generator, with nonnegative off-diagonal entries; boundary elimination may reduce the row radius. If every coefficient is at most , then , and the Gershgorin bounds for symmetric matrices place every eigenvalue in .
For the forward Euler method, an eigenvalue has amplification factor . Requiring for every such eigenvalue gives the sufficient absolute stability condition . Symmetry makes this also prevent growth of the Euclidean norm. For and , the bound is and . At that step size the interval maps to amplification factors in . This illustrates why cheap Gershgorin disc bounds can select a stable time step before any eigenvalues are computed.
Part (a) shows that is invariant throughout the interpolation. As the Hamiltonians are Hermitian, is invariant as well: evolution starting in has no leakage into other sectors. The quantum adiabatic theorem may therefore be applied using the restricted spectral gap, even if other sectors of the full Hamiltonian have different low-energy levels.
Combining (b)(iv) with the supplied bound for gives for a constant . The matrix has diagonal entries and off-diagonal entries . Its Gershgorin discs all lie in , so . Thus the runtime criterion for adiabatic preparation of a computational history state is satisfied by
with a sufficiently large constant.
Starting from the supplied initial ground state , the resulting state obeys
Here the trace norm follows the question's convention; the conventional trace distance is half this norm. The Hamiltonian has explicitly specified terms, each acting on at most five qubits, so its description and the runtime are polynomial in circuit size. If is polynomially bounded, the whole preparation has polynomial cost. The initial computational input is assumed to have been prepared, as in the premise of the quantum adiabatic theorem.
The Gershgorin circle theorem states that every eigenvalue of belongs to at least one of the closed Gershgorin discs
The eigenvalue may be complex even though the matrix is real. To prove the theorem, choose a nonzero complex eigenvector with and an index at which is maximal. Then , and the th row gives
The triangle inequality yields
Thus , proving the assertion without any symmetry assumption.
The second theorem, or Gershgorin eigenvalue counting, states: if a union of indexed Gershgorin discs is disjoint from all remaining discs, it contains exactly 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 and 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 . Rows have sums less than , and the last row has sum , since . 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 . Since the sum is strictly below , the coefficient-independent bounds
guarantee that zero is outside every Gershgorin disc. Consequently zero is not an eigenvalue and is an invertible matrix. Equality at is allowed because the off-diagonal entry bounds are strict. These are sufficient strict diagonal dominance bounds; values of between them can also give invertible matrices.
Put . With , the row Gershgorin discs have centres and radii
Applying the theorem to the transpose gives column Gershgorin discs with radii
The 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 is also disjoint from the enlarged disc at if
For the column family, every small disc at is disjoint from the enlarged disc at by the same estimate, since . Thus the Gershgorin eigenvalue counting theorem certifies one simple eigenvalue near each of from rows, and near each of from columns. The certified small discs from the two families are themselves disjoint, so these are different eigenvalues.
The largest nonnegative certified by these uniform row-and-column separation bounds is
More generally the argument works for . The endpoint is included because all actual entry bounds, and hence all actual radius estimates above, are strict. For , : row discs isolate centres , and column discs isolate centres .
Figure 1.
For n=8 and c=13/4 the row Gershgorin discs isolate the four lower centres; the enlarged disc is centred at 8
. Details.
Figure 2.
The transpose moves the enlarged Gershgorin disc to centre 1 and isolates the four upper centres
. Details.
For , taking the adjacent entries sufficiently close to makes the enlarged row disc meet the small disc at , and the enlarged column disc meet the small disc at . 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 gives
Thus every , and the diagonal matrix has inverse . The iteration matrix has entries
Each row Gershgorin disc for is centred at zero and has radius
Therefore every eigenvalue of satisfies
Equivalently, the induced matrix norm satisfies , bounding the spectral radius. This is the usual Jacobi convergence from strict diagonal dominance; the Jacobi error matrix is , with the same eigenvalue magnitudes.
Source: Oxford Part A, A7 Numerical Analysis, A13759W1, 23 June 2023; parent PDF pages 135–137, paper pages 1–3. These original solutions cover all three questions and all eleven lettered subparts. In Question 1(d), the unrefined Gershgorin discs alone are inconclusive for the shift ; a further exact calculation resolves it. In Question 2(c), clearing denominators produces a linear system whose solution need not define a rational interpolant at every interpolation node. Question 3 uses the paper's normalized convention for the local truncation error.
For a complex matrix , put
The Gershgorin circle theorem states that
To prove it, let with , and choose for which . The th coordinate of the eigenvalue equation gives
The triangle inequality, followed by division by , gives
Thus , proving the assertion for every eigenvalue.
The second theorem, Gershgorin eigenvalue counting, says that if a union of indexed Gershgorin discs is disjoint from the remaining Gershgorin discs, that union contains exactly eigenvalues, counted with algebraic multiplicity. In particular,
Discs that touch are not disjoint; overlapping Gershgorin discs cannot individually be assigned one eigenvalue each.
The four row Gershgorin discs have centres and radii , respectively. Their real-axis intersections are
None of the Gershgorin discs contains zero, so the Gershgorin circle theorem gives
The discs centred at and are each isolated. By Gershgorin eigenvalue counting, they contain exactly one eigenvalue apiece, and both eigenvalues are simple. Each must be real: the characteristic polynomial is real, so a nonreal root would bring a distinct conjugate root into the same disc. Denote these eigenvalues by and . The remaining two eigenvalues lie in the union of the negative-centred discs.
For the shift , the distances satisfy
for either of the other eigenvalues , since its real part is at most . Thus is uniquely closest to . Once is checked not to be an eigenvalue, the natural full target-disc interval enclosure and a conservative asymptotic direction factor are
As always, inverse iteration requires a nonzero initial target component. The following calculation verifies the shift and gives sharper information.
For the tridiagonal matrix, let be the determinant of the leading block of . Expansion along the last row gives
In particular, , and . Both shifted linear systems are nonsingular. Further exact evaluations are
The intermediate value theorem gives a real root in each of , , and . As has polynomial degree four, these are all its roots and each is simple. In particular, is a diagonalizable matrix, and . The closest competitor to at the shift is , so this refinement yields
For the shift , the original Gershgorin discs only give and ; those bounds do not decide which is closer. The refined interval enclosures do:
for the negative eigenvalues. Therefore the answer for this particular matrix is yes:
Both shifts select the same eigenvector line and alternate signs because . The factor bounds concern asymptotic directional convergence, rather than a universal error reduction from the first iterate for a nonsymmetric matrix. The wider interval remains a valid full-disc enclosure for both shifts; records the stronger information obtained from the characteristic polynomial.
For with , the three Gershgorin discs have positive real centres , , , and radii , , . Centre minus radius is respectively
Thus none of the discs contains zero. By the Gershgorin circle theorem, zero is not an eigenvalue, so is nonsingular for every . Consequently