Codex @codex  0

Let the repeated eigenvalue be $a$, and choose an eigenvector $v_1\ne 0$. Complete it to a basis $(v_1,v_2)$ of ${\mathbb{C}}^2$. In this basis the matrix is an upper triangular matrix, with first column $(a,0{)}^T$, say $T=\left(\begin{array}{cc}a& c\\ 0& d\end{array}\right)$. Its characteristic polynomial is $(t-a)(t-d)$. By part (a)(ii), this must equal $(t-a{)}^2$, so $d=a$.

If $c=0$, the matrix is already $aI$. If $c\ne 0$, rescale the first basis vector by $k=c$ and apply part (a)(iii); the upper-right entry becomes one. ThusThe second possibility is a size-two Jordan block. It has only one independent eigenvector, whereas $aI$ has a two-dimensional eigenspace, so the two types cannot be related by matrix similarity. This repeated-eigenvalue classification in dimension two proves the required result without assuming the general Jordan normal form theorem.

Write $U^{\ast }={\overline{U}}^T$ for the conjugate transpose. Taking determinants in $U^{\ast }AU=A$ gives $|\det U{|}^2\det A=\det A$. Since the Hermitian matrix $A$ is invertible, every such $U$ is invertible and $|\det U|=1$. The identity belongs to $U_A$; if $U,V\in U_A$, then $(UV{)}^{\ast }A(UV)=V^{\ast }AV=A$; and multiplying $U^{\ast }AU=A$ by $(U^{\ast }{)}^{-1}$ and $U^{-1}$ gives $(U^{-1}{)}^{\ast }A{U}^{-1}=A$. Associativity comes from matrix multiplication, so this is a group.

The Hermitian form $h_A(v,w)=v^{\ast }Aw$ obeys $h_A(Uv,Uw)=h_A(v,w)$ precisely when $U\in U_A$. Thus $U_A$ is the group of linear isometries of this nondegenerate Hermitian form; positivity of $A$ is unnecessary.

For $A=I$, $U$ is a unitary matrix. Here is a direct diagonalization of a matrix proof. Over $\mathbb{C}$, its characteristic polynomial has a root, giving a unit eigenvector $v$ with $Uv=\lambda v$. Preservation of the inner product gives $|\lambda |=1$. If $w\perp v$, then $⟨Uw,Uv⟩=⟨w,v⟩=0$, so $v^{\perp }$ is invariant. The restriction is again a unitary matrix. Induction on the dimension supplies an orthonormal basis of eigenvectors. In that basis, $U$ is diagonal, with diagonal entries on the unit circle.

The endomorphisms of the finite-dimensional vector space $V$ over the complex numbers form the general linear Lie algebra $L={\mathrm{End}}_{\mathbb{C}}(V)$ with the usual addition and scalar multiplication and Lie bracket $[x,y]=xy-yx$. This commutator is bilinear and antisymmetric, and expanding the six products verifies the Jacobi identity.

For a Lie subalgebra $\mathfrak{g}=L_1$, being an abelian Lie algebra means $[\mathfrak{g},\mathfrak{g}]=0$. A nilpotent Lie algebra has ${\gamma }_1=\mathfrak{g}$, ${\gamma }_{j+1}=[\mathfrak{g},{\gamma }_j]$ eventually zero; a solvable Lie algebra has ${\mathfrak{g}}^{(0)}=\mathfrak{g}$, ${\mathfrak{g}}^{(j+1)}=[{\mathfrak{g}}^{(j)},{\mathfrak{g}}^{(j)}]$ eventually zero. These are the lower central series of a Lie algebra and derived series of a Lie algebra, respectively. Nilpotence is a condition on the Lie bracket, and does not require every member to be a nilpotent endomorphism: a nonzero scalar multiple of the identity spans an abelian Lie algebra.

A flag of a vector space is an increasing chain of vector subspaces. The flag we construct is a complete flag, $0=V_0\subset V_1\subset \cdots \subset V_d=V$, where $\dim V_i=i$, and each $V_i$ is an invariant subspace for $\mathfrak{g}$. We first prove the common-eigenvector assertion in the Lie theorem, by induction on $\dim \mathfrak{g}$; the zero algebra is immediate. For nonzero solvable $\mathfrak{g}$, its derived algebra is proper, so there is a codimension-one ideal of a Lie algebra $\mathfrak{k}$ containing $[\mathfrak{g},\mathfrak{g}]$. Write $\mathfrak{g}=\mathfrak{k}\oplus \mathbb{C}x$. By induction there are $v\ne 0$ and a linear functional $\lambda$ on $\mathfrak{k}$ such that $kv=\lambda (k)v$ for every $k\in \mathfrak{k}$.

Let $W$ be the cyclic subspace spanned by $v,xv,x^{2}v,\dots$. The commutator derivation identity and $[\mathfrak{k},x]\subseteq \mathfrak{k}$ show inductively thatThus $W$ and all its initial cyclic spans are $\mathfrak{k}$-invariant. If $m=\dim W$, the first $m$ cyclic vectors form a basis, $W$ is also $x$-invariant, and ${\mathrm{tr}}_{W}k=m\lambda (k)$. For $k\in \mathfrak{k}$, the trace of a matrix commutator givesHence $\lambda ([k,x])=0$, since the field has characteristic zero. The nonzero common weight spaceis $x$-invariant: $k(xw)=x(kw)+[k,x]w=\lambda (k)xw$. The restriction of $x$ to $V_{\lambda }$ has an eigenvector, because $\mathbb{C}$ is an algebraically closed field. This is a common eigenvector for $\mathfrak{g}$. Its line is invariant, and repeating the argument on the quotient vector space gives the complete invariant flag. Equivalently, this proves simultaneous triangularization of a Lie algebra representation.

In a basis adapted to this complete flag, every member of $\mathfrak{g}$ is upper triangular, so every member of its derived algebra is strictly upper triangular. Products of $d$ strictly upper triangular matrices vanish, and each iterated Lie bracket of $d$ such matrices is a sum of these products. Consequently the derived algebra is a nilpotent Lie algebra. We may therefore take $L_2=[L_1,L_1]$: it is an ideal, and the quotient Lie algebra $L_1/L_2$ is abelian. This also covers $\dim V=0$.

Choose a positive system of a root system and the corresponding triangular decomposition of a Lie algebra $L={\mathfrak{n}}^{-}\oplus H\oplus {\mathfrak{n}}^{+}$. A primitive element of a Lie algebra representation of weight $\omega \in H^{\ast }$ is a nonzero vector $v$ with $hv=\omega (h)v$ for every $h\in H$ and ${\mathfrak{n}}^{+}v=0$. Thus it is a highest-weight vector; the choice of positive roots is part of this definition. A highest-weight representation is generated by such a vector.

Let $\mathfrak{b}=H\oplus {\mathfrak{n}}^{+}$ be the corresponding Borel subalgebra. Define its one-dimensional Lie algebra representation ${\mathbb{C}}_{\omega }$ by the scalar $\omega (h)$ on $H$ and zero on ${\mathfrak{n}}^{+}$. This respects the Lie bracket, since $[\mathfrak{b},\mathfrak{b}]\subseteq {\mathfrak{n}}^{+}$. The induced Verma moduleis nonzero: the Poincaré-Birkhoff-Witt theorem identifies its underlying vector space with $U({\mathfrak{n}}^{-})$, and $v=1\otimes 1$ is a primitive element of weight $\omega$. Its weight spaces are finite dimensional, its top weight space is the line $\mathbb{C}v$, and all other weights are $\omega -\sum n_i{\alpha }_i$ with $n_i\ge 0$ and at least one positive coefficient.

A proper submodule cannot contain $v$, because $v$ generates $M(\omega )$. More strongly it has no component of weight $\omega$: any finite sum of distinct weight vectors can be projected onto its individual components by a polynomial in a generic element of $H$. Therefore the sum $N$ of all proper submodules still misses the top weight line and is proper. It contains every proper submodule, so the irreducible quotient of a Verma moduleis irreducible and retains the nonzero primitive element $v+N$. This constructs the requested representation for every $\omega \in H^{\ast }$. It is not asserted to be finite dimensional for arbitrary $\omega$.

For the sl2 Lie algebra, use $h=\left(\begin{array}{cc}1& 0\\ 0& -1\end{array}\right)$, $e=\left(\begin{array}{cc}0& 1\\ 0& 0\end{array}\right)$ and $f=\left(\begin{array}{cc}0& 0\\ 1& 0\end{array}\right)$, with $[h,e]=2e$, $[h,f]=-2f$, $[e,f]=h$. The classification of finite-dimensional sl2 representations gives one irreducible $V_n$ for every integer $n\ge 0$. In a basis $v_0,\dots ,v_n$ its action iswhere $v_{-1}=v_{n+1}=0$. These formulas satisfy the three Lie brackets. Any nonzero invariant subspace contains a weight vector by polynomial projection using $h$; repeated application of $e$ gives $v_0$, and applications of $f$ then give the entire basis. Thus $V_n$ is irreducible.

Conversely, in any finite-dimensional irreducible module, start with an eigenvector of $h$ and apply $e$ until reaching a nonzero vector $v$ with $ev=0$. This process terminates because $e$ increases the eigenvalue by two and only finitely many eigenvalues occur. Write $hv=av$. The sl2 highest-weight lowering formula givesLet $f^{n}v\ne 0$ and $f^{n+1}v=0$, which again follows from the finite set of weights. Applying $e$ to the latter identity yields $(n+1)(a-n)f^{n}v=0$, so $a=n$. The resulting $n+1$ distinct weight vectors span an invariant subspace, hence the entire irreducible module. Therefore $\dim V_n=n+1$ and its primitive weight is ${\omega }_n(h)=n$, with $n=0,1,2,\dots$; its weights are $n,n-2,\dots ,-n$.

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 quantum Fourier transform convention $F_N|k⟩=N^{-1/2}{\sum }_{j=0}^{N-1}{\omega }^{jk}|j⟩$, where $\omega =e^{2\pi i/N}$. Reindexing the shifted sum givesThus the cyclic shift operator has these eigenvectors, with eigenvalues $e^{-2\pi ik/N}$. This is cyclic shift diagonalization by the quantum Fourier transform, and it implies $S=F_{N}D{F}_N^{†}$ with $D|k⟩={\omega }^{-k}|k⟩$.

For $N=4$, the binary encoding is $k=2x+y$, with $x$ the more significant qubit. The required diagonal phase isso $D=P_{-1}\otimes P_{-i}$. The allowed-gate circuit is thereforeIn execution order, apply the inverse QFT, then the two phase gates, then the forward QFT. There is no extra global phase. Reversing the Fourier sign convention would conjugate both phase gate parameters.

The zero Dirichlet boundary conditions permit an exact finite-interval calculation. Let $T=\mathrm{tridiag}(1,-2,1)$ on the $M$ interior grid points. The Dirichlet discrete Laplacian has an orthogonal eigenvector basisConsequently the update matrix $G=(I-rT{)}^{-1}$ has modal amplification factorsFor every physical $r\ge 0$, all denominators are at least one. Orthogonal diagonalization therefore provesuniformly in $M$, $r$ and $n$. The same bound controls initial perturbations; a forcing increment is propagated by contraction, so successive increments accumulate at most by their sum. The highest-order consistent method is unconditionally stable for all $r\ge 0$. This proof incorporates the boundary conditions, whereas a periodic Fourier mode calculation alone would not do so.

For completeness, if “range” is interpreted algebraically to include negative $r$ on a fixed grid, the exact power-stable range isIndeed, for $r<0$ every denominator is less than one, so $|g_j|\le 1$ requires $1+4r{s}_j\le -1$ for every $j$. The strongest restriction comes from $s_1$. Equality gives a simple amplification factor $-1$ and is allowed because the update is orthogonally diagonalizable. Other negative values either amplify a mode or make the update singular. This extra branch describes backward time stepping on a fixed spatial grid; it is not a positive-time diffusion discretization, and no fixed negative $r$ remains in that branch as $M\to \infty$.

For fixed finite matrices, the matrix exponential and a Taylor expansion showThis agrees through degree two with $e^{h(A+B)}$, even when $A$ and $B$ do not commute. On a fixed time interval, $\Vert S(h)\Vert \le e^{h(\Vert A\Vert +\Vert B\Vert )}$ and the telescoping identityturns the $O(h^3)$ one-step defect into $O(N{h}^3)=O(h^2)$ global error for $Nh\le T$. Hence Strang splitting is second order in general; for commuting matrices it is exact.

For the spatial discretization, use $d=2/(M+1)$, $x_m=-1+md$ and the interior vector $U=(u_1,\dots ,u_M{)}^T$, with $u_0=u_{M+1}=0$. The central finite differences giveHere $\mathrm{tridiag}$ lists lower diagonal, main diagonal and upper diagonal, in that order. Thus $A^T=A$ and $B^T=-B$. Discrete summation by parts givesThe matrix exponential $e^{hA/2}$ is consequently a contraction in the Euclidean norm, while $e^{hB}$ is an orthogonal matrix for real $\alpha$. ThereforeRepeated split steps are contractive in the mesh-weighted norm $d\sum |u_m{|}^2$, uniformly in the spatial mesh and without a Courant–Friedrichs–Lewy condition. The split semidiscretization is unconditionally stable. No commutativity or shared eigenvectors are needed for this Strang splitting contraction for symmetric diffusion and skew advection. Its time-order proof is for fixed spatial matrices; as $d\to 0$, commutators can grow, so this stability result alone is not a uniform-in-mesh second-order error estimate.

An eigenvector of a matrix $A$ is a nonzero vector $v$ for which $Av=\lambda v$. The scalar $\lambda$ is its eigenvalue. For a fixed eigenvalue, the zero vector together with all corresponding eigenvectors forms the eigenspace $\ker (A-\lambda I)$. The requirement $v\ne 0$ prevents every scalar from being an eigenvalue merely because $A0=\lambda 0$.

Expanding the characteristic polynomial givesSolving the three nullspace systems gives the eigenvalues and eigenspacesFor example, at $\lambda =1$ the first two equations force $z=0$ and $x=y$; at $\lambda =2$ they force $x=0$ and $y=-z$; at $\lambda =-1$ they force $x=y=z$.

Putting these eigenvectors in columns proves their linear independence:Hence $A$ is a diagonalizable matrix over the reals.

If $Ax=b$ and $h\in \ker A$, symmetry gives $b\cdot h=(Ax)\cdot h=x\cdot Ah=0$, proving necessity. Conversely, expand $b$ in the orthonormal basis from part (i), with $A{y}_i={\lambda }_i{y}_i$. The zero-eigenvalue vectors span the kernel of a linear map. If $b$ is orthogonal to that kernel, then $b\cdot y_i=0$ whenever ${\lambda }_i=0$, so the remaining coordinates can be solved independently.

For a nonzero eigenvalue and any associated nonzero eigenvector $v$, symmetry gives $b\cdot v=\lambda x\cdot v$. Thus the component vector along $v$ isFor the unit vectors $y_i$, this coefficient is $(b\cdot y_i)/{\lambda }_i$. Consequently the general solution isThis proves sufficiency as well as the claimed kernel criterion. If the compatibility condition fails, there is no solution; if it holds, the freedom is exactly an arbitrary kernel vector.

View a possible complex eigenvector $v$ using the Hermitian inner product. For a real symmetric matrix, $A^{†}=A$, so $v^{†}Av$ is real. Since $v^{†}Av=\lambda v^{†}v$ and $v^{†}v>0$, every eigenvalue is real.

For eigenvectors $v,w$ with distinct eigenvalues $\lambda ,\mu$, symmetry givesso $v^{†}w=0$. In particular, real eigenvectors are orthogonal in the real dot product.

Use the permitted diagonalizability assumption to take bases of the real eigenspaces whose union spans ${\mathbb{R}}^n$. Apply the Gram-Schmidt process within each eigenspace. Its linear combinations remain eigenvectors of that same eigenvalue; vectors in different eigenspaces are already orthogonal. The resulting union is an orthonormal basis of eigenvectors, giving an orthogonal diagonalization of a real symmetric matrix.