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.

If $A$ is Skew-Hermitian, then $-iA$ is a Hermitian matrix. The finite-dimensional spectral theorem gives $A=Q\mathrm{diag}(i{\theta }_j)Q^{†}$, with real ${\theta }_j$ and a unitary matrix $Q$. Since the matrix exponential respects similarity, $e^A=Q\mathrm{diag}(e^{i{\theta }_j})Q^{†}$. Each diagonal entry has modulus one, so $e^A$ is a unitary matrix. Thus a skew-Hermitian matrix generates norm-preserving linear evolution.

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 givesThe union preserves gaps that the single outer interval loses. If every $a_{ii}-r_i>0$, 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, $1.7\le \lambda \le 9.4$ gives a positive-definite matrix certificate and bounds its spectral condition number of a positive-definite matrix by $9.4/1.7\approx 5.529412$; the computed value is about $4.544364$.

Strictness matters. The symmetric matrix $\left(\begin{array}{cc}1& -1\\ -1& 1\end{array}\right)$ has positive diagonal and is a diagonally dominant matrix, but its eigenvalues are $0$ and $2$: it is singular. For a general complex matrix, the condition $\mathrm{Re}{a}_{ii}>r_i$ only puts the eigenvalues in the open right half-plane. The Hermitian matrix assumption is what converts that statement into positive definiteness.

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]

For a finite-dimensional Hermitian matrix $A$, the Rayleigh quotient has precisely the range $[{\lambda }_{\min },{\lambda }_{\max }]$, where the endpoints are its extreme eigenvalues. The finite-dimensional spectral theorem writes a nonzero vector as $x={\sum }_j{c}_j{e}_j$ in an orthonormal eigenbasis, givingThus the quotient is a convex combination of eigenvalues. The bounds follow immediately, and equality at either endpoint means that $x$ lies in the corresponding extreme eigenspace, including any repeated eigenvalue. Every intermediate value occurs: for orthonormal extreme eigenvectors, $x=\sqrt{1-t}{e}_{\min }+\sqrt{t}{e}_{\max }$ gives $R_A(x)=(1-t){\lambda }_{\min }+t{\lambda }_{\max }$ for $0\le t\le 1$. If all eigenvalues are equal, the quotient is constant.

The Hermitian hypothesis matters. The real matrix $B=\left(\begin{array}{cc}1& 4\\ 0& 1\end{array}\right)$ has only the eigenvalue $1$, but $(1,1)B(1,1{)}^T/2=3$. Its quotient is governed by the symmetric part of a matrix $(B+B^T)/2$, not by a real orthonormal eigenbasis of $B$. A nonsymmetric matrix therefore need not obey the displayed eigenvalue bounds.

For a real symmetric matrix $A$ with nonnegative eigenvalues, the finite-dimensional spectral theorem changes the equation to ${\sum }_i{\lambda }_i{q}_i^2=E$ in an orthonormal eigenbasis. If $E>0$ and $A$ has positive rank, the positive-eigenvalue coordinates form an ellipsoid, while the zero-eigenvalue coordinates are arbitrary. The level set is therefore a cylinder over that ellipsoid, with axis directions given by the kernel of a linear map of $A$. For rank two in three dimensions, it is an elliptic cylinder. At $E=0$ the level set is exactly the kernel of a linear map; for $E<0$ it is empty. This distinguishes a positive semidefinite matrix from a positive-definite matrix, whose positive level sets are bounded ellipsoids.

An orthonormal eigenbasis of a linear operator is an orthonormal basis consisting of eigenvectors. Each vector can be reconstructed from its scalar components along those mutually perpendicular unit directions. With the convention that the inner product is linear in its first argument,The finite-dimensional spectral theorem supplies such a basis for a self-adjoint operator. In its two-dimensional example, the coordinates of $x=(1,0{)}^T$ are $1/\sqrt{2}$ along $e_{+}$ and $-1/\sqrt{2}$ along $e_{-}$. The operator multiplies those coordinates by $3$ and $1$, and reconstruction gives $Ax=(2,1{)}^T$.

Repeated eigenvalues permit different orthonormal choices within one eigenspace, so the basis need not be unique. The spectral projection of a self-adjoint matrix onto that entire eigenspace is unique: it keeps the geometrically meaningful component without choosing individual axes inside it.

Self-adjointness means $⟨Tv,w⟩=⟨v,Tw⟩$ for all $v,w\in V$, or $T=T^{\ast }$. Take the inner product linear in its first variable. If $Tv=\lambda v$ with $v\ne 0$, thenTherefore every eigenvalue is real.

If $U$ is invariant and $w\in U^{\perp }$, then for every $u\in U$, $Tu\in U$ and $⟨Tw,u⟩=⟨w,Tu⟩=0$. Hence $Tw\in U^{\perp }$, proving invariance of the orthogonal complement.

Induct on $d=\dim V$. The zero-dimensional case is empty. For $d>0$, choose an eigenvector and normalize it to a unit vector $e$. Its span is invariant, so its orthogonal complement is invariant as just proved. The restriction of $T$ to that complement is again self-adjoint. Its dimension is $d-1$, so induction supplies an orthonormal basis of eigenvectors there. Adjoining $e$ gives an orthonormal eigenbasis of $V$. This proves the finite-dimensional spectral theorem without assuming it in the argument.

A self-adjoint operator satisfies $⟨Tx,y⟩=⟨x,Ty⟩$ for every $x,y$. The finite-dimensional finite-dimensional spectral theorem gives an orthonormal basis of eigenvectors and real eigenvalues; eigenvectors for distinct eigenvalues are orthogonal. Consequently a matrix represents a self-adjoint transformation in some, possibly nonorthonormal, basis exactly when it is diagonalizable with real eigenvalues.

For $A_0$, the eigenvalues are $2,1,0$, all distinct and real. Eigenvectors are $e_1$, $e_2$, and $(0,-1,1{)}^T$. Thus $A_0$ can represent a self-adjoint transformation after choosing a suitable basis.

For $A_1$, the eigenvalue one has algebraic multiplicity two but its eigenspace has dimension one. The lower $2\times 2$ block is a nontrivial Jordan block, so the matrix is not diagonalizable. Hence $A_1$ cannot represent a self-adjoint transformation in any basis.

For $A_2$, the eigenspace for two is spanned by $e_1$ and $(0,1,1{)}^T$, and the eigenvalue-one eigenspace is spanned by $e_2$. These three vectors form an eigenbasis. Therefore $A_2$ can represent a self-adjoint transformation. To see sufficiency on the given inner product space, first define the real diagonal transformation in an orthonormal basis and then apply the inverse of a diagonalizing basis change to obtain the requested matrix. Symmetry of the displayed matrix itself would be required only for an orthonormal representing basis.

Work in ${\mathbb{C}}^N$, the domain of the matrix $A$; the printed ${\mathbb{C}}^n$ in the introduction is a dimension typo. For a fixed nonempty support of a vector $S$, write $u$ for the coordinates of $x$ in $S$. ThenThe Gram matrix $A_S^{\ast }{A}_S$ is a Hermitian matrix, so its difference from the identity matrix is also a Hermitian matrix. By the finite-dimensional spectral theorem, its matrix 2-norm is the largest absolute eigenvalue, equivalentlyIndeed, an expansion in an orthonormal eigenbasis bounds every Rayleigh quotient by the largest absolute eigenvalue, and an appropriate eigenvector attains that bound. The restricted isometry constant must bound this quantity for every $S$ of size at most $s$, and the maximum of these quantities suffices for all sparse vectors of order $s$. There are finitely many sets, so the maximum exists. The empty set contributes zero. Therefore

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 relevant fixed coordinate subspace is $\{(u,0):u\in {\mathbb{R}}^k\}$. Let $G$ be the first $k$ columns of $X$ and letThe Gaussian empirical Gram matrix $G^{T}G/n$ is the empirical second moment with the known mean zero; no subtraction of an estimated mean is involved. For $\theta =(u,0)$, the ratio under consideration is $|u^{T}Du|/\Vert u{\Vert }_2^2$. Since $D$ is a real symmetric matrix, the finite-dimensional spectral theorem givesIndeed, diagonalizing $D$ bounds every unit-vector quadratic form by the largest absolute eigenvalue, and a corresponding unit eigenvector attains the bound.

We first construct a unit sphere net from ball covering. Enlarge the numerical covering constant, if necessary, to $A_0\ge 1$. Cover the unit ball in ${\mathbb{R}}^k$ with at most $(2A_0/\delta {)}^k$ balls of radius at most $\delta /2$. For each such ball meeting the unit sphere, choose a point of the sphere in it and discard the others. These selected points form a metric net $\mathcal{N}$ of the unit sphere with radius $\delta$: any two points in one covering ball have distance at most $\delta$. This argument ensures that the net points have unit length even if the original covering centers did not.

Take $\delta =1/4$ and put $B=8A_0$, so $|\mathcal{N}|\le B^k$. For unit vectors $u,v$ with $\Vert u-v{\Vert }_2\le \delta$,Taking a net point for every unit $u$ and then a supremum proves the quadratic form net boundIt follows that

Fix $v\in \mathcal{N}$. The rows of $G$ are independent vectors of independent random variables with the standard normal distribution, and $\Vert v{\Vert }_2=1$. Their scalar products with $v$ are therefore independent $N(0,1)$ variables $g_1,\dots ,g_n$, soUse the supplied chi-squared concentration inequality with $z=n/1024$. Its threshold isConsequently $P(|v^{T}Dv|>1/4)\le 2e^{-n/1024}$. The union bound gives the stronger fixed-subspace estimateThis is Gaussian Gram matrix concentration on a fixed subspace.

Since $1\le k<p$, we have $p\ge 2$. Under $n\ge Ck\log p$,Choose the numerical constant $C\ge 1024(1+\log B/\log 2)$. Then the parenthesis is at least one, so $C^{\prime }=1$ is a valid choice, andThe covering factor is only $B^k$ because the coordinate subspace is fixed. The ambient dimension enters through the assumed sample-size bound.

The linear-system residual at an approximate solution $x_m$ is $r_m=b-A{x}_m$. For symmetric positive definite $A$, the conjugate gradient method has $x_m\in x_0+K_m(A,r_0)$ and minimizes the squared $A$-norm of the error over that affine space; its residual is orthogonal to $K_m(A,r_0)$.

If $A$ has $t$ distinct eigenvalues, interpolate $q(\lambda )=1/\lambda$ on them with a polynomial of degree at most $t-1$. The finite-dimensional spectral theorem gives $A^{-1}=q(A)$, so the exact correction $x_{\ast }-x_0=A^{-1}{r}_0$ lies in $K_t(A,r_0)$. The minimum possible error at step $t$ is therefore zero. Thus $\boxed{\text{CG terminates in at most }t\text{ steps}}$ in exact arithmetic, possibly earlier if the initial residual has fewer eigencomponents. If $r_0=0$, it terminates immediately.

A symmetric positive definite matrix preconditioner $M$ changes the system to $M^{-1/2}A{M}^{-1/2}z=M^{-1/2}b$, with $x=M^{-1/2}z$; practical preconditioned CG applies solves with $M$. It can accelerate convergence by reducing the spectral condition number of a positive-definite matrix, which improves the usual bound involving $(\sqrt{\kappa }-1)/(\sqrt{\kappa }+1)$, and by clustering eigenvalues, which allows low-degree residual polynomials small on the spectrum even when the extreme-eigenvalue bound is pessimistic.

Choosing $\boxed{M=A}$ makes the transformed matrix $I$, so one step suffices. But applying $M^{-1}$ already requires solving the original problem, and constructing an exact factorization generally incurs its original computational cost. It is therefore not a useful shortcut for a single unsolved system, though an available factorization can be reused for multiple right-hand sides. Effective matrix preconditioning balances spectral improvement against inexpensive application.

A self-adjoint operator $T$ satisfies $⟨Tx,y⟩=⟨x,Ty⟩$. If $Tx=\lambda x$, then $\lambda ⟨x,x⟩=⟨Tx,x⟩=⟨x,Tx⟩=\overline{\lambda }⟨x,x⟩$, so $\lambda \in \mathbb{R}$. An eigenvector exists over $\mathbb{C}$; its orthogonal complement is $T$-invariant. Induction on dimension produces an orthonormal basis of eigenvectors, proving the finite-dimensional spectral theorem.

A self-adjoint $T$ is positive definite exactly when every eigenvalue is positive, since $⟨Tx,x⟩={\sum }_i{\lambda }_i|x_i{|}^2$ in an eigenbasis. The quadratic forms of two positive-definite operators add, so their sum is positive definite.

The same eigenbasis shows that $\mathrm{spec}T\subset [a,b]$ exactly when $T-\lambda I$ is positive definite for every $\lambda <a$ and negative definite for every $\lambda >b$. Finally, if $v$ is a unit eigenvector of $\alpha +\beta$ with eigenvalue $\gamma$, the Rayleigh quotient bounds giveThus every eigenvalue of $\alpha +\beta$ lies in $[a+c,b+d]$.

The printed definition of the restricted isometry constant omits the quantifier: the two inequalities must hold for every vector with at most $s$ nonzero entries. The constant is the smallest nonnegative value, or the infimum over positive values; it can be zero.

Let $T=\mathrm{supp}u\cup \mathrm{supp}v$ and $B=A_T^{\ast }{A}_T-I$. The restricted isometry property of order $s+t$ says $|z^{\ast }Bz|\le {\delta }_{s+t}\Vert z{\Vert }_2^2$ for every $z$ supported on $T$. Since $B$ is a Hermitian matrix, the finite-dimensional spectral theorem implies $\Vert B{\Vert }_{2\to 2}\le {\delta }_{s+t}$. Disjoint supports give $⟨u,v⟩=0$, henceThis argument works over $\mathbb{C}$ and avoids the loss of a factor caused by treating real and imaginary parts separately.

Put $p=⟨\psi |M_1^2|\psi ⟩\ge 1-\epsilon$. Since $M_1$ is a positive contraction, the successful post-measurement state is the pure state represented by $|{\psi }^{\prime }⟩=M_1|\psi ⟩/\sqrt{p}$. Its squared quantum fidelity with the input isThe finite-dimensional spectral theorem and $0\le M_1\le I$ give $M_1^2\le M_1$, so $⟨M_1⟩\ge p$. Therefore the pure-state gentle measurement bound isThe positive-operator assumption matters: an arbitrary unitary measurement operator can have success probability one while rotating the state to an orthogonal vector.

Put $H=A-B$. This is a nonzero Hermitian matrix. By the finite-dimensional spectral theorem, it has a unit eigenvector $v$ with a nonzero real eigenvalue $lambda$. Define the rank-one orthogonal projection matrixThe cyclic property of the matrix trace givesHence this $P$ distinguishes $A$ and $B$ through the required traces.

A linear operator $\alpha$ on a real inner-product space is self-adjoint whenfor all $v,w$.

To prove the finite-dimensional spectral theorem, first note that the continuous quadratic function $⟨\alpha v,v⟩$ has a maximum on the unit sphere. The Lagrange multiplier equation at a maximizing vector $v$ gives $\alpha v=\lambda v$, so $\alpha$ has a real unit eigenvector. Its orthogonal complement is invariant becauseInduction on the dimension supplies an orthonormal eigenbasis of that complement and hence of $V$.

For $f\ne 0$,while symmetry and bilinearity are immediate, so the displayed formula defines an inner product on $P_n$. Sinceintegration by parts givesThe boundary term vanishes for polynomials, proving that $\alpha$ is self-adjoint.

On the monomial $x^k$,Thus the matrix of $\alpha$ in the monomial basis is triangular with diagonalThese are therefore its eigenvalues. For $n=2$, corresponding eigenvectors arefor eigenvalues $0,-1,-2$, respectively. They are the first Laguerre polynomials up to normalization, as described by the Laguerre differential operator on polynomials.

Because $A$ is a real symmetric positive-definite matrix, the finite-dimensional spectral theorem supplies an orthonormal eigenbasis $u_1,\dots ,u_n$ withIts eigendecomposition is also its singular value decomposition. If $e=y^{(\delta )}-y$, thensoThe operator norms satisfy $\Vert A{\Vert }_2={\lambda }_n$ and $\Vert A^{-1}{\Vert }_2=1/{\lambda }_1$. Therefore the worst-case relative perturbation bound isThe ratio ${\kappa }_2(A)$ is the spectral condition number of a positive-definite matrix. A large ratio means that data noise aligned with an eigenvector for the smallest eigenvalue is strongly amplified, so the inverse problem is ill conditioned.

An $n\times n$ matrix is diagonalizable over a chosen field exactly when it has a basis of $n$ linearly independent eigenvectors. Equivalently, $P^{-1}AP$ is diagonal for some invertible $P$. Distinct eigenvalues suffice but are not necessary. For example,is not diagonalizable: its only eigenvalue is $1$ and its eigenspace is the one-dimensional span of $(1,0{)}^T$. It is a nontrivial Jordan block.

A Hermitian matrix satisfies $A^{†}=A$, where the dagger denotes conjugate transpose. If $Av=\lambda v$ with $v\ne 0$, thenThe denominator is positive real, soFor $Av=\lambda v$ and $Aw=\mu w$, Hermiticity also givesThusThis is the necessary qualification to the PDF's orthogonality wording: arbitrary eigenvectors belonging to a repeated eigenvalue need not be orthogonal. Within each repeated eigenspace, Gram-Schmidt orthogonalization produces an orthonormal basis; together the eigenspaces give an orthonormal eigenbasis by the finite-dimensional spectral theorem. For example, $(1,0{)}^T$ and $(1,1{)}^T$ are nonorthogonal eigenvectors of the identity matrix.