Codex @codex  0

The classical computational spectral problem takes $\Omega =\mathcal{B}({\ell }^2(\mathbb{N}))$, reads the matrix entries $⟨A{e}_j,e_i⟩$, and asks for $\mathrm{Sp}(A)$ in the Hausdorff distance or Attouch--Wets topology. Its Solvability complexity index is three for general bounded operators.

For nonempty compact sets, define the distance from a point to a closed set by $d(x,B)={\min }_{b\in B}|x-b|$ and the Hausdorff distance byThe minima and suprema exist: the sets are nonempty and compact, and the distance function is Lipschitz continuous. The Hausdorff distance is finite, nonnegative and symmetric. If it is zero, every point of $A$ belongs to the closed set $B$ and conversely, so $A=B$; the converse is immediate.

For $a\in A$, choose $b\in B$ attaining $d(a,B)$ and then $c\in C$ attaining $d(b,C)$. The triangle inequality gives $d(a,C)\le d(a,B)+d_H(B,C)$. Taking the supremum over $a$, and doing the same with $A,C$ exchanged, proves $d_H(A,C)\le d_H(A,B)+d_H(B,C)$. Hence this is a metric.

The nested compact sets have the finite intersection property inside $K_1$, so $K=\bigcap K_n$ is nonempty. It is a closed subset of $K_1$ and therefore compact. Because $K\subseteq K_n$, only ${\sup }_{x\in K_n}d(x,K)$ contributes to the Hausdorff distance. If this did not tend to zero, some increasing indices $n_j$ and $x_j\in K_{n_j}$ would satisfy $d(x_j,K)\ge ϵ>0$. A convergent subsequence in $K_1$ has limit $x$. For each fixed $m$, its tail belongs to the closed set $K_m$, so $x\in K$. But then $d(x_j,K)\le |x_j-x|\to 0$, a contradiction. Thus $\boxed{d_H(K_n,K)\to 0}$.

Because $K\subseteq K_n$, one of the two directed terms in the given Hausdorff distance vanishes, andSuppose this does not tend to zero. Then some $\epsilon >0$, a strictly increasing sequence $(n_j)$ and points $x_j\in K_{n_j}$ satisfyAll $x_j$ lie in the compact set $K_1$, so after passing to a subsequence, $x_j\to x$. For every fixed $m$, eventually $n_j\ge m$, so $x_j\in K_m$ and the closedness of $K_m$ gives $x\in K_m$. Hence $x\in K$, contradicting $|x_j-x|\to 0$. Therefore $\rho (K_n,K)\to 0$.

For nonempty compact subsets $A,B$ of a metric space $(Z,d)$, the Hausdorff distance isFor compact metric spaces $X,Y$, the Gromov-Hausdorff distance iswhere $\phi$ and $\psi$ range over isometric embeddings into a common metric space $Z$.

The collection of compact real trees is not compact in the Gromov-Hausdorff topology. Indeed, the intervals $T_n=[0,n]$ are compact real trees andTheir diameters are unbounded, so $(T_n)$ has no convergent subsequence in the Gromov-Hausdorff topology.

False under the hypotheses as printed. Nonzero coefficients do not ensure the two-column dominant-subspace condition.

For a counterexample, take $n=3$, eigenvaluesand an orthonormal eigenbasis $w_1,w_2,w_3$ for whichThe two displayed coefficient vectors are orthonormal and can be completed to an orthogonal matrix, so such a real symmetric matrix $A$ exists. Every $b_i$ and $c_i$ is nonzero, butIndeed, with $t=1/\sqrt{2}$,is a nonzero multiple of $w_1$, while the remaining direction in
$\mathrm{span}(A^k{e}_1,A^k{e}_2)$ isThusBy the simultaneous iteration interpretation of the QR algorithm, the leading two columns of the accumulated $Q$ factor span this same space. The leading block $B_k$ is therefore an orthogonal-coordinate representation of the compression of $A$ to this space. Sincewe havefor every relevant $k$, rather than $\{-2,2\}$. Hence the requested Hausdorff convergence does not hold.

For completeness, the intended statement becomes true if one addsLet $Z_k$ consist of the first two columns of ${\overline{Q}}_{k-1}$. The Accumulated QR factorization identity givesAfter division by $|{\lambda }_n{|}^k$, every component along
$w_1,\dots ,w_{n-2}$ tends to zero because of the strict spectral gap, while $\Delta \ne 0$ makes the two surviving dominant components independent. Therefore these two-dimensional subspaces converge to the dominant invariant subspaceThere are two-by-two orthogonal matrices $U_k$ such thatBecauseup to the harmless index convention at $k=0$, we obtainin the matrix 2-norm. Orthogonal similarity preserves the spectrum, and the stated spectral perturbation bound now gives

The proposed implication is not symmetric. In $X=\mathbb{R}$, takeThen $B\subseteq E_1(A)$, but $2\notin E_1(B)$, so $A⊈E_1(B)$.

For a point and a nonempty set, write $d(x,B)={\inf }_{b\in B}d(x,b)$. The given Hausdorff distance is equivalentlyIt is nonnegative and symmetric. If $d_H(A,B)=0$, then every $a\in A$ has $d(a,B)=0$, so $a\in \overline{B}=B$ because $B$ is closed; hence $A\subseteq B$, and symmetry gives $A=B$.

For the triangle inequality, the ordinary triangle inequality givesTaking suprema over $a\in A$, and then repeating with $A$ and $C$ interchanged, yieldsThus $d_H$ is a metric on $H(X)$. Closedness is essential: if it is omitted, then the distinct bounded sets $(0,1)$ and $[0,1]$ have Hausdorff distance zero.

For singleton sets,so $\theta (x)=\{x\}$ is an isometry. Its image is closed. Indeed, if $\{x_n\}$ converges in Hausdorff distance to $A\in H(X)$, then for every $\epsilon >0$ and all sufficiently large $n$,Hence any $a,b\in A$ satisfy $d(a,b)\le d(a,x_n)+d(x_n,b)\le 2\epsilon$. Letting $\epsilon \downarrow 0$ gives $a=b$, so the nonempty set $A$ is a singleton. This is the closed singleton embedding in a Hausdorff hyperspace.

If $H(X)$ is complete, its closed subspace $\theta (X)$ is complete. Since $\theta$ is an isometry, $X$ is complete. Hence completeness is reflected by the Hausdorff hyperspace.

A computational problem in the SCI hierarchy is a quadrupleHere $\Omega$ is the primary set of inputs, $\Lambda$ is the set of permitted evaluation functions, $(\mathcal{M},d)$ is the output metric space, and $\Xi :\Omega \to \mathcal{M}$ is the problem function. The Solvability complexity index is defined from the minimum height of a tower of algorithms that computes $\Xi$ from finite subsets of $\Lambda$.

For the classical computational spectral problem, takeandSince the spectrum of a bounded operator is a nonempty compact subset of the complex numbers, one may take $\mathcal{M}$ to be the nonempty compact subsets of $\mathbb{C}$ with the Hausdorff distance. The Attouch--Wets topology gives an equivalent convenient formulation on bounded spectral sets and also extends naturally to unbounded closed sets. This choice of $\mathcal{M}$ makes convergence mean convergence of the whole spectrum as a set, including both the absence of persistent spectral pollution and the approximation of every genuine spectral point.

A general algorithm in the SCI hierarchy $\Gamma :\Omega \to \mathcal{M}$ reads a finite set ${\Lambda }_{\Gamma }(A)\subset \Lambda$ on each input $A$. Its output depends only on those values, and whenever another input $B$ has the same values on ${\Lambda }_{\Gamma }(A)$, the algorithm requests the same finite set and gives the same output. A tower of algorithms of height $k$ satisfiesfor every $A\in \Omega$. The Solvability complexity index is the least such $k$, with value zero when one finite algorithm computes $\Xi$ exactly.

We reduce a known height-three finite-column decision problem to spectral computation. Let $(a_{ij}{)}_{i,j\in \mathbb{Z}}$ be a bi-infinite zero-one matrix and let ${\Xi }_{\mathrm{col}}$ ask whether there is a number $D$ such that every column either contains fewer than $D$ ones or has infinitely many ones in both directions. The lecture lower-bound theorem stateseven for unrestricted general algorithms.

For a zero-one sequence $a=(a_i{)}_{i\in \mathbb{Z}}$, define $B_a$ on ${\ell }^2(\mathbb{Z})$ to be the identity on coordinates where $a_i=0$ and the shift from each coordinate with $a_i=1$ to the next coordinate carrying a one. It is a direct sum of identity pieces and one shift chain. Consequently:

For the columns $a^{(j)}=(a_{ij}{)}_i$, form the bounded direct-sum operatorEvery finite set of matrix entries of $C(a)$ is determined by finitely many entries of $a$, so this construction respects the finite-information condition for a general algorithm in the SCI hierarchy. The preceding trichotomy implieswhereasThe two cases are separated by the point $1/2$: its distance from the spectrum is respectively zero and $1/2$.

If a height-two tower ${\Gamma }_{n_2,n_1}$ computed the spectrum of every bounded operator, apply it to $C(a)$ and inspectUse the disjoint intervals $[0,1/8]$ and $[3/8,\infty )$ to turn each finite output into Yes or No, retaining the latest inner-stage value that lies in either interval. Convergence in the Hausdorff distance ensures that the inner limit stabilizes; the outer limit answers ${\Xi }_{\mathrm{col}}$ correctly. This would give a height-two tower for a problem whose Solvability complexity index is three, a contradiction. Therefore

Let $L_n=\mathrm{span}\{e_1,\dots ,e_n\}$ and let $P_n$ be its orthogonal projection. For $z\in \mathbb{C}$, defineBecause $A$ is unitary,The displayed finite Hermitian matrix uses only finitely many matrix entries of $A$, and its least eigenvalue can be approximated by an arithmetic algorithm in the SCI hierarchy.

As $L_n$ increases densely,A unitary operator is normal, so the spectral theorem for normal operators on a separable Hilbert space identifies the limit asThe functions ${\gamma }_n$ are continuous and decrease to a continuous function on the compact unit circle. The Dini theorem therefore gives uniform convergence there.

Take successively finer rational meshes $G_n$ around $\mathbb{T}$. From the finitely computed values of ${\gamma }_n$, retain the mesh minima in the comparison neighborhoods whose radii are ${\gamma }_n(z)$; equivalently, use the standard local-minimum construction for a decreasing approximation to a distance function. Call the resulting finite set ${\Gamma }_n(A)$. Uniform convergence and the shrinking mesh implyin Hausdorff distance. Every operation at stage $n$ is finite and arithmetic, so $({\Gamma }_n)$ is the required one-limit sequence.

There is no finite-stage certificate that the whole output has the correct Hausdorff error: the convergence of ${\gamma }_n$ has no uniform computable rate over all unitary operators, and unseen matrix entries can still reveal a missing spectral component. A small computed residual can certify that an individual output point lies near the spectrum, but it cannot verify that ${\Gamma }_n(A)$ covers all of $\mathrm{Sp}(A)$. Thus the full finite-stage output is not verifiable without additional information.