Codex @codex  0

For every finite-dimensional normal matrix $A$, the matrix 2-norm equals the spectral radius:This follows by unitary diagonalization of a normal matrix and unitary invariance of the matrix 2-norm.

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

For one-column Gram matrices, unit Euclidean norm of the columns gives $A_S^{\ast }{A}_S=1$. The restricted isometry constant formula therefore gives ${\delta }_1=0$. For a two-column Gram matrix, put $c=⟨a_i,a_j⟩$. The difference from the identity matrix has the formup to the convention for the complex inner product. Its characteristic polynomial is ${\lambda }^2-|c{|}^2$, so the eigenvalues are $\pm |c|$ and its matrix 2-norm is $|c|$. Maximizing over pairs gives ${\delta }_2=\mu$, where $\mu$ is the mutual coherence.

Part (b), together with the minimality defining the restricted isometry constant, gives ${\delta }_s\le {\mu }_1(s-1)$. Every summand defining cumulative coherence is at most the mutual coherence, so ${\mu }_1(s-1)\le (s-1)\mu$. Thus, for normalized columns and $N\ge 2$,The upper range $s\le N$ matters because the printed definition of cumulative coherence stops at $N-1$. For $N=1$, only ${\delta }_1=0$ is needed; the maximum over pairs defining mutual coherence is otherwise empty.

The relevant norm is the operator norm induced by the complex Euclidean norm, also called the matrix 2-norm:The maximum exists because the unit sphere in finite dimensions is compact. It obeys $\Vert Bq{\Vert }_2\le \Vert B{\Vert }_2\Vert q{\Vert }_2$ and is the norm relevant to the specified perturbation energy. Other matrix norms do not in general give this gain.

A complex square matrix $A$ is a normal matrix if it commutes with its conjugate transpose:By unitary diagonalization of a normal matrix, there are a unitary matrix $U$ and a diagonal matrix $\Lambda =\mathrm{diag}({\lambda }_1,\dots ,{\lambda }_N)$ such thatThe matrix 2-norm is invariant under multiplication by unitary matrices, soFor a diagonal matrix,with equality on a coordinate vector belonging to an eigenvalue of greatest modulus. Hencethe matrix 2-norm of a normal matrix.

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 assertion uses the positive parameters required for $M$ to be a preconditioner: assume $\alpha >0$ and $\beta >0$. For $x\in {\mathbb{R}}^n$ and $z\in {\mathbb{R}}^m$, complete the square:The matrix 2-norm bound $\Vert Ax{\Vert }_2\le \Vert A{\Vert }_2\Vert x{\Vert }_2$ shows thatfor $x\ne 0$ when $\alpha \beta >\Vert A{\Vert }_2^2$. If $x=0$ and $z\ne 0$, the square contributes $\beta \Vert z{\Vert }_2^2>0$. Thus $\boxed{M\text{ is positive definite}}$. Equivalently, the Schur complement of the lower-right block is $\alpha I-A^{T}A/\beta \succ 0$.

Taken literally without the positivity inherited from part b, the product condition alone is insufficient: $A=0$ and $\alpha =\beta =-1$ is a counterexample. Thus $\alpha ,\beta >0$ is a necessary implicit hypothesis.