Codex @codex  0

For normalized columns and $1\le s\le N$, the restricted isometry constant is bounded by the cumulative coherence at $s-1$. A restricted Gram matrix has diagonal one and every off-diagonal row sum at most ${\mu }_1(s-1)$. The Gershgorin circle theorem and the finite-dimensional spectral theorem bound its eigenvalues between $1-{\mu }_1(s-1)$ and $1+{\mu }_1(s-1)$. At $s=1$ the distortion is zero, and at $s=2$ it is exactly the mutual coherence.

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 $A=(a_{ij})\in {\mathbb{C}}^{n\times n}$, with $n\ge 1$, and define the closed Gershgorin discsEvery eigenvalue $\lambda$ of $A$ satisfies $\lambda \in {\bigcup }_i{D}_i(A)$, 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 $x$ with $Ax=\lambda x$, choose $i$ with $|x_i|={\max }_j|x_j|>0$. The $i$th row givesThus the largest eigenvector coordinate identifies a Gershgorin disc containing $\lambda$, 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 $0$ lies outside every Gershgorin disc, then $A$ is an invertible matrix, since zero is not an eigenvalue. The condition is exactly $|a_{ii}|>r_i$ 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, takeThe three Gershgorin discs have centres $2,5,9$ and are pairwise disjoint. The finite-dimensional spectral theorem makes the eigenvalues real, so their possible locations reduce to the intervals $[1.7,2.3]$, $[4.5,5.5]$, and $[8.6,9.4]$. Gershgorin eigenvalue counting gives exactly one eigenvalue in each. Independently, the characteristic polynomial iswhose numerical polynomial roots are $1.985811$, $4.989942$, and $9.024247$, rounded to six decimal places. All are positive, as Gershgorin bounds for symmetric matrices already guarantee without finding those polynomial roots.

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]

A row Gershgorin disc of a square matrix $A=(a_{ij})$ is the closed disk in the complex plane with centre $a_{ii}$ and radius $r_i={\sum }_{j\ne i}|a_{ij}|$. 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 $A^T$ gives column Gershgorin discs with the same centres and radii $c_i={\sum }_{j\ne i}|a_{ji}|$. Since $A$ and $A^T$ 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 $\min (r_i,c_i)$. An isolated row Gershgorin disc contains exactly one eigenvalue by Gershgorin eigenvalue counting.^[ref]

Use the natural empty-sum convention ${\mu }_1(0)=0$ for cumulative coherence. This is needed for the printed case $s=1$. For $x=0$ the conclusion is immediate. Otherwise let $S$ be its support of a vector, with $k=|S|\le s$. The Gram matrix $G=A_S^{\ast }{A}_S$ has diagonal entries one because the columns have unit Euclidean norm. Each off-diagonal row sum is bounded byThe last inequality uses monotonicity of cumulative coherence: enlarging an index set only adds nonnegative summands. There are enough indices to enlarge it because $s\le N$.

The Gershgorin circle theorem places every eigenvalue of $G$ within distance ${\mu }_1(s-1)$ of one. Since $G$ is a Hermitian matrix, its eigenvalues are real, and the finite-dimensional spectral theorem givesThis is the cumulative coherence bound for restricted isometry. The lower bound remains valid when ${\mu }_1(s-1)>1$, although it is then nonpositive. No assumption that the matrix is already a near isometry is required. The distortion is bounded by ${\mu }_1(s-1)$ on every order-$s$ sparse vector.

The Gershgorin circle theorem says that every eigenvalue of a square matrix lies in at least one disc centred at a diagonal entry with radius the sum of the absolute values of the off-diagonal entries in that row.

For interior unknowns write the update as $u^{n+1}=B{u}^n$. The matrix is real symmetric and tridiagonal, with diagonal $1-\mu (a_{m-1/2}+a_{m+1/2})$ and adjacent entries $\mu a_{m+1/2}$. Each Gershgorin radius is at most $\mu (a_{m-1/2}+a_{m+1/2})$. Its real interval is therefore contained inFor $0<\mu \le 1/(2a_{+})$, every eigenvalue lies in $[-1,1]$. Symmetry gives an orthogonal diagonalization, so $\Vert B^n{\Vert }_2\le 1$ for every $n$: errors in initial data cannot grow. This is stability in the discrete ${\ell }^2$ norm, also in its $h$-weighted version. One can additionally see maximum-norm stability directly: the update weights are nonnegative with row sums at most one once the zero boundary unknowns are removed. Hence $\Vert B{\Vert }_{\infty }\le 1$.

Here the only nonzero coefficients of $a$ areTherefore, for each $(m,n)\in {\Lambda }_N$, the truncated system iswhere a coefficient is omitted when its index is outside ${\Lambda }_N$ or equals $(0,0)$.

For wavevectors $\mathbf{k}=(m,n)$ and $\mathbf{\ell }=(p,q)$, the matrix entry isBecause ${\hat{a}}_{\mathbf{r}}={\hat{a}}_{-\mathbf{r}}$, $A_{\mathbf{k},\mathbf{\ell }}=A_{\mathbf{\ell },\mathbf{k}}$, so the matrix is symmetric. Its diagonal entry is $5{\pi }^2|\mathbf{k}{|}^2$. The sum of absolute off-diagonal entries is at mostbecause $|\mathbf{k}{|}^2\pm k_j\ge 0$ for nonzero integer $\mathbf{k}$; truncation can only reduce the sum. Hence $A$ is strictly diagonally dominant with positive diagonal. The Gershgorin circle theorem places every eigenvalue in the positive intervalfor at least one row. Since the symmetric matrix has only real eigenvalues, all are positive, and $A$ is a positive-definite matrix. Any one-dimensional ordering merely conjugates $A$ by a permutation matrix, preserving symmetry and positive definiteness.

The Gershgorin circle theorem states that every eigenvalue $\lambda$ of a complex matrix $A=(a_{ij})$ lies in at least one diskTo prove it, choose a nonzero eigenvector $x$ for $\lambda$ and an index $i$ such that $|x_i|={\max }_j|x_j|>0$. The $i$th component of $Ax=\lambda x$ givesTaking absolute values and using $|x_j|\le |x_i|$ yieldsDivision by $|x_i|$ proves the theorem.

Let $L_h$ be the spatial matrix, so the forward Euler method isThe conservative use of shared edge coefficients makes $L_h$ a real symmetric matrix. In an interior row, put $s=\alpha +\beta +\gamma +\delta <4a_{\max }$. Its diagonal entry is $-s/h^2$, and the sum of the absolute off-diagonal entries is $s/h^2$. Boundary rows have no larger disk because homogeneous Dirichlet data remove some unknown neighbors.

The Gershgorin circle theorem and symmetry therefore place every eigenvalue of $L_h$ inIf $\mu =k/h^2$, each amplification eigenvalue is $1+k\lambda$. It lies in $[-1,1]$ wheneverorSince the amplification matrix is symmetric, bounding all its eigenvalues in modulus by one bounds its discrete Euclidean operator norm by one. This proves the stated stability condition and is the Gershgorin stability bound for a variable-coefficient diffusion stencil.

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.

For a complex $n\times n$ matrix $B=(b_{ij})$, putThe Gershgorin circle theorem states thatTo prove it, let $Bv=\lambda v$ with $v\ne 0$, and choose $i$ for which $|v_i|={\max }_j|v_j|>0$. The $i$th coordinate of the eigenvalue equation givesThe triangle inequality, followed by division by $|v_i|$, givesThus $\lambda \in D_i$, proving the assertion for every eigenvalue.

The second theorem, Gershgorin eigenvalue counting, says that if a union of $k$ indexed Gershgorin discs is disjoint from the remaining $n-k$ Gershgorin discs, that union contains exactly $k$ 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 $9,3,-4,-5$ and radii $1,2,2,1$, respectively. Their real-axis intersections areNone of the Gershgorin discs contains zero, so the Gershgorin circle theorem givesThe discs centred at $9$ and $3$ 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 $\beta \in [8,10]$ and $\alpha \in [1,5]$. The remaining two eigenvalues lie in the union of the negative-centred discs.

For the shift $4$, the distances satisfyfor either of the other eigenvalues $\gamma$, since its real part is at most $-2$. Thus $\alpha$ is uniquely closest to $4$. Once $4$ is checked not to be an eigenvalue, the natural full target-disc interval enclosure and a conservative asymptotic direction factor areAs always, inverse iteration requires a nonzero initial target component. The following calculation verifies the shift and gives sharper information.

For the tridiagonal matrix, let $p_j(t)$ be the determinant of the leading $j\times j$ block of $tI-A$. Expansion along the last row givesIn particular, $\det A=577$, $p_4(4)=-239$ and $p_4(5)=-583$. Both shifted linear systems are nonsingular. Further exact evaluations areThe intermediate value theorem gives a real root in each of $(-6,-5)$, $(-4,-3)$, $(3,4)$ and $(8,9)$. As $p_4$ has polynomial degree four, these are all its roots and each is simple. In particular, $A$ is a diagonalizable matrix, $\alpha \in (3,4)$ and $\beta \in (8,9)$. The closest competitor to $\alpha$ at the shift $4$ is $\beta$, so this refinement yieldsFor the shift $5$, the original Gershgorin discs only give $|\alpha -5|\le 4$ and $|\beta -5|\ge 3$; 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 $\alpha <\mu$. The factor bounds concern asymptotic directional convergence, rather than a universal error reduction from the first iterate for a nonsymmetric matrix. The wider interval $[1,5]$ remains a valid full-disc enclosure for both shifts; $[3,4]$ records the stronger information obtained from the characteristic polynomial.

The Gershgorin circle theorem states that every complex eigenvalue $\lambda$ of $A=(a_{ij})$ belongs to at least one closed discTo prove it, take an eigenvector $v\ne 0$ and choose $i$ with $|v_i|={\max }_j|v_j|>0$. The $i$th row of $Av=\lambda v$ givesDivision by $|v_i|$ proves the assertion. The proof works for real matrices even when their eigenvalues or eigenvectors are complex.

For $B+\mu I$, the three discs have centres $2+\mu ,3+\mu ,4+\mu$ and radii $2,3,4$. Every point in their union has real part at least $\mu$. Thus for $\mu >0$ no disc contains zero, and zero cannot be an eigenvalue. Hence $B+\mu C$ is nonsingular.

The Gershgorin circle theorem states that every eigenvalue of $A$ lies in at least one discFor a nonzero complex eigenvector $v$, choose an index $i$ with $|v_i|={\max }_j|v_j|>0$. The $i$th row of $Av=\lambda v$ givesDividing by $|v_i|$ proves membership in $D_i$. This is valid for real matrices even when the eigenvalues are complex.

For $A+\gamma B$ with $\gamma \ge 0$, the three Gershgorin discs have positive real centres $a+\gamma$, $2c+2\gamma$, $6b+6\gamma$, and radii $b+c$, $a+b+\gamma$, $a+c+\gamma$. Centre minus radius is respectivelyThus none of the discs contains zero. By the Gershgorin circle theorem, zero is not an eigenvalue, so $A+\gamma B$ is nonsingular for every $\gamma \ge 0$. Consequently

Gershgorin circle theorem places every complex eigenvalue of $A$ in at least one disk $D_i=\{z:|z-a_{ii}|\le {\sum }_{j\ne i}|a_{ij}|\}$. To prove it, take a nonzero eigenvector $v$ and choose $i$ with $|v_i|={\max }_j|v_j|>0$. The $i$th eigenvector equation givesDivision by $|v_i|$ proves the disk bound.

Here $C=I$, and the three disks for $B+\mu I$ have real centres $2+\mu$, $3+\mu$, $4+\mu$ and radii $2,3,4$ respectively. Every point in every disk has real part at least $\mu >0$. Hence zero cannot be an eigenvalue, proving $B+\mu C$ is nonsingular for every $\mu >0$.

The Gershgorin circle theorem states that every eigenvalue of $A$ lies in at least one discFor a nonzero complex eigenvector $v$, choose an index $i$ with $|v_i|={\max }_j|v_j|>0$. The $i$th row of $Av=\lambda v$ givesDividing by $|v_i|$ proves membership in $D_i$. This is valid for real matrices even when the eigenvalues are complex.

For $A+\gamma B$ with $\gamma \ge 0$, the three Gershgorin discs have positive real centres $a+\gamma$, $2c+2\gamma$, $6b+6\gamma$, and radii $b+c$, $a+b+\gamma$, $a+c+\gamma$. Centre minus radius is respectivelyThus none of the discs contains zero. By the Gershgorin circle theorem, zero is not an eigenvalue, so $A+\gamma B$ is nonsingular for every $\gamma \ge 0$. Consequently

The Gershgorin circle theorem states that every complex eigenvalue of a square matrix $A$ lies in at least one closed disc $D_i=\{z:|z-a_{ii}|\le {\sum }_{j\ne i}|a_{ij}|\}$. To prove it, take a nonzero eigenvector $v$ for $\lambda$ and choose $i$ with $|v_i|$ maximal. The $i$th row of $Av=\lambda v$ givesDivision by $|v_i|>0$ proves the claim. The proof applies to real and complex matrices alike.

The second part of the Gershgorin circle theorem states that if a union of $k$ of the discs is disjoint from every remaining disc, that union contains exactly $k$ eigenvalues, counted with algebraic multiplicity. In particular, a single isolated disc contains precisely one eigenvalue. Connected components of the full union therefore carry the corresponding disc counts.

Write $q=1/4+ϵ$ and take $0<ϵ<1/4$, as intended by the small-parameter assumption. The row discs have centers $1,\dots ,n$ and radii $ϵ,q,\dots ,q,1/4$. They are pairwise disjoint because the sum of neighboring radii is below one. The second Gershgorin circle theorem places one eigenvalue in each disc. Since $A$ is real, nonreal eigenvalues occur in conjugate pairs; a disc centered on the real axis would have to contain both members, contradicting its count of one. Thus all eigenvalues are real andAlternatively, a positive diagonal change of basis symmetrizes the tridiagonal matrix, with transformed off-diagonal entries $\sqrt{ϵ}/2$, also proving reality.