Codex @codex  0

Take $N$ to be a closed compact Riemannian manifold and use the positive Laplace-Beltrami operator. Its Riemannian heat kernel $K_N(t,x,y)$ is the integral kernel of $e^{-t{\Delta }_N}$:It solves $({\partial }_t+{\Delta }_x)K_N=0$ for $t>0$ and tends to the identity kernel as $t\downarrow 0$. For an orthonormal eigenbasis, the spectral expansion of the Riemannian heat kernel isThe bar is required for a complex basis. With boundary, a specified invariant boundary condition must also be included in this definition.

For the quotient formula use the covering-space interpretation: $U$ acts freely and properly discontinuously by Riemannian isometries. On compact $N$ such a discrete group is finite. Freeness alone, without this covering hypothesis, does not justify the image sum: an infinite dense subgroup of circle rotations, for example, acts freely but has no manifold quotient. Positive-dimensional group actions require a different quotient analysis.

For lifts $x,y$ of $\bar{x},\bar{y}\in M$, the heat kernel on a finite isometric quotient isInvariance of $K_N$ under simultaneous Riemannian isometries and reindexing the sum show that this is independent of both lifts. A local isometry commutes with the Laplacian, so the sum satisfies the quotient heat equation. For its initial condition, integrate over a fundamental domain $F\subset N$ against a lifted function. The terms combine into the integral over all of $N$, whose initial limit is $f(x)$. Uniqueness of the heat evolution proves the formula. There is no factor $1/|U|$ in this kernel formula.

On the diagonal the sum is $U$-invariant. Its integral over $F$ is therefore $1/|U|$ times its integral over $N$, giving the heat traceThus the normalization factor appears in the trace, not the kernel. Put $F_t(g)={\int }_N{K}_N(t,x,gx)dV(x)$. For any finite isometry group $T$, changing variables $x=hy$ proves $F_t(hg{h}^{-1})=F_t(g)$: it is a class function on $T$.

For Gassmann equivalent subgroups $U_1,U_2\le T$, their intersections with each conjugacy class have equal size, and their orders are equal. If both act freely, the heat traces of their quotients satisfyso they agree for every $t>0$. Since $Z_M(t)={\sum }_{\lambda }m(\lambda )e^{-t\lambda }$, equality determines the spectrum with multiplicities: take $t\to \infty$ to recover the smallest eigenvalue and its multiplicity, subtract that term, and repeat. This proves Sunada theorem. Equivalently, projection onto $U_i$-invariant functions averages the group action, and the quotient eigenvalue multiplicity is $|U_i{|}^{-1}{\sum }_{u\in U_i}{\chi }_{\lambda }(u)$, with ${\chi }_{\lambda }$ the eigenspace character of a representation. Almost conjugacy equalizes these averages.

Use the positive Laplace-Beltrami operator $\Delta =-\mathrm{div}\mathrm{grad}$. A Riemannian submersion is a surjective smooth submersion $\pi :(M,g)\to (N,h)$ for which, at every $p$, the restriction of $d{\pi }_p$ to $H_p=(\ker d{\pi }_p{)}^{\perp }$ is a linear isometry onto $T_{\pi (p)}N$. The spaces $V_p=\ker d{\pi }_p$ and $H_p$ are its vertical and horizontal spaces. Its fibres are totally geodesic submanifolds precisely when ${\nabla }_{U}V$ is vertical for vertical vector fields $U,V$: their second fundamental form vanishes. Equivalently, a geodesic initially tangent to a fibre remains in that fibre while defined.

For a smooth $f:N\to \mathbb{R}$, its basic function $F=f\circ \pi$ is constant along each fibre. The Riemannian gradient of $F$ is the horizontal lift of a vector field through a submersion of ${\mathrm{grad}}_{N}f$, sincefor horizontal $X$, and $dF(U)=0$ for vertical $U$. In particular no derivative of $f$ in a vertical direction occurs.

Here is the needed connection fact, which also follows directly from the Koszul formula: for horizontal lifts $X,Y$ of vector fields $\bar{X},\bar{Y}$ on $N$, the horizontal component of ${\nabla }_{X}Y$ projects to ${\nabla }_{\bar{X}}^N\bar{Y}$. To see this, pair the Koszul formula with a third horizontal lift $Z$. The horizontal inner products are pulled back from $N$, and the horizontal components of their Lie brackets of vector fields project to the brackets on $N$. Thus all six terms are the pullbacks of the corresponding terms on $N$.

Choose an adapted Riemannian orthonormal frame $X_1,\dots ,X_n,U_1,\dots ,U_r$, with the $X_a$ horizontal lifts. Using $\mathrm{Hess}F(A,A)=A(AF)-({\nabla }_{A}A)F$, the connection fact givesFor a vertical $U_b$, both $U_{b}F=0$ and $({\nabla }_{U_b}{U}_b)F=0$, the latter because the fibres are totally geodesic submanifolds. Taking the negative metric trace of the Riemannian Hessian therefore proves the basic-function Laplacian identityThis identity is local and does not require compactness. Vanishing mean curvature of the fibres would already suffice; total geodesicity makes each vertical summand vanish separately.

For the discrete eigenspace assertion, assume the two Riemannian manifolds are closed manifolds. Without a discrete spectral realization, an unrestricted noncompact version need not have an eigenbasis. The projections of the Riemannian product $M\times N$ are Riemannian submersions with totally geodesic submanifolds as fibres. Its Levi-Civita connection splits into the two factor connections. Consequently its positive Laplace-Beltrami operator isThe cross term in the product rule for the positive Laplace-Beltrami operator is zero because the two factor Riemannian gradients are orthogonal.

We use the standard compact elliptic compact elliptic spectral theorem: the positive Laplace-Beltrami operator on a closed manifold is self-adjoint, has compact resolvent, and has a complete orthonormal eigenbasis of smooth eigenfunctions, with finite-dimensional eigenspaces and eigenvalues tending to infinity. Let ${\Delta }_M{u}_i={\mu }_i{u}_i$ and ${\Delta }_N{v}_j={\nu }_j{v}_j$. Fubini's theorem and completeness on each factor show that $u_i(x)v_j(y)$ form a complete orthonormal basis of $L^2(M\times N)$. For example, a function orthogonal to all these products has, for each $i$, zero $u_i$-coefficient as an $L^2(N)$ function, hence is zero.

The displayed operator identity makes $u_i{v}_j$ an eigenfunction with eigenvalue ${\mu }_i+{\nu }_j$. Conversely, if $\Delta w=\lambda w$, self-adjointness of the positive Laplace-Beltrami operator givesAll other coefficients vanish. Only finitely many pairs can have ${\mu }_i+{\nu }_j=\lambda$, since both spectra are nonnegative and have finitely many eigenvalues below any fixed bound. Thus the product Laplacian eigenspace decomposition isThe tensor product summands are mutually orthogonal; their elements are actual smooth eigenfunctions, so this is an equality of eigenspaces, not just a formal expansion.

Let $M$ be a closed manifold with a Riemannian metric and use $\Delta =-\mathrm{div}\mathrm{grad}$, the positive Laplace-Beltrami operator. This is the setting in which the final discrete eigenfunction expansion applies without additional boundary or noncompact spectral hypotheses. A Riemannian heat kernel is a smooth $H(t,x,y)$ for $t>0$ such thatfor every smooth initial function $f$. Here $\nu$ solves the heat equation. The limit is the statement that the initial kernel is the Dirac delta distribution on the diagonal. In the closed setting this uniquely determines the heat kernel; it is symmetric, preserves constants, is nonnegative, and satisfies the semigroup property.

A heat parametrix $P(t,x,y)$ is an approximate version with the same delta initial limit and with errorregular enough at $t=0$ to correct by a convergent integral series. One may construct it by the local Gaussian ansatzwhere $\chi =1$ near the diagonal and is supported in a convex normal neighborhood, and the smooth coefficients solve the usual radial transport equations. The leading coefficient accounts for the Riemannian volume form. Taking $q$ sufficiently large makes the residual extend continuously, with any prescribed finite number of derivatives, to $t=0$. Alternatively a smooth asymptotic summation of all transport coefficients gives a residual vanishing to every order. These local construction, extension and differentiability facts are used here as subsidiary results, as permitted.

For the correction proof take a heat parametrix whose residual is smooth up to $t=0$ on a short interval $[0,T]$. We also use its uniform integral bound ${\sup }_{0<t\le T,x}{\int }_M|P(t,x,y)|d{V}_y<\infty$, its approximate-identity limit, and the following standard differentiability property: convolution with a smooth time-dependent kernel gives a smooth kernel for $t>0$, and differentiating it yields the identity below. These properties follow from the Gaussian estimates and the delta initial limit; no conclusion about the final exact heat kernel is assumed.

Define the Volterra convolution of kernels byIt is associative wherever these integrals converge. The delta term at the upper endpoint givesSeek $H=P+P\ast Q$. Then its error vanishes exactly when $Q+R+R\ast Q=0$. The solution is the Volterra parametrix correctionThe signs matter: the first correction is $-P\ast R$.

To prove convergence, let $|R|\le C$ and $V=\mathrm{vol}(M)$. The time variables in $R^{\ast k}$ range over a simplex of volume $t^{k-1}/(k-1)!$, soThe series for $Q$ therefore converges uniformly on $[0,T]\times M\times M$. Derivatives obey analogous bounds, with polynomial factors in $k$, by the quoted residual extension and differentiation properties. Thus the series can be convolved and differentiated as above. Associativity and absolute convergence give $Q+R+R\ast Q=0$, proving $({\partial }_t+{\Delta }_x)H=0$. The correction $P\ast Q$ has integral norm $O(t)$ by the integral bound on $P$ and boundedness of $Q$. It has zero initial limit, so $H$ has precisely the required delta initial data.

For uniqueness, a smooth solution $w$ with zero initial data satisfies the heat equation energy identityIts initial norm is zero, hence $w=0$. Applying uniqueness to consecutive evolutions proves the semigroup property. Choose $s_0<T$ and, for arbitrary $t>0$, compose enough kernels $H(t/r)$ that $t/r<s_0$. The resulting kernel is independent of the subdivision by uniqueness, is smooth for positive time by the quoted differentiability property, and extends the construction to every $t>0$. This proves a parametrix determines the global heat kernel in the closed setting. The heat equation maximum principle gives nonnegativity and applying uniqueness to the constant initial function gives conservation of total mass. Self-adjointness of the positive Laplace-Beltrami operator $\Delta$ gives symmetry.

Finally let $\{{\varphi }_j\}$ be a complete complex orthonormal eigenbasis of $\Delta$, with eigenvalues ${\lambda }_j\ge 0$, repeated by multiplicity. As subsidiary analytic facts we use the compact elliptic compact elliptic spectral theorem, elliptic regularity bounds making each fixed derivative of ${\varphi }_j$ grow at most polynomially in $1+{\lambda }_j$, and a polynomial eigenvalue-counting bound. The spectral expansion of the Riemannian heat kernel converges because exponential decay makes the following series converge with every derivative when $t\ge \epsilon >0$:Indeed, evolving initial data ${\varphi }_j$ gives $e^{-t{\lambda }_j}{\varphi }_j$ by direct substitution into the heat equation and uniqueness. For general $f\in L^2(M)$, completeness and the heat equation energy identity giveThe smoothly convergent kernel series represents this same operator, and equality for all smooth $f$ identifies it pointwise with the constructed heat kernel. The complex conjugate is required by the inner product; for a real eigenbasis it may be omitted. A noncompact Riemannian manifold may instead require a spectral integral, and the unqualified discrete formula should not be asserted there.

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

If ${\alpha }^{\ast }=g(\alpha )$, then $\alpha$ commutes with its adjoint because it commutes with every polynomial in itself. Hence $\alpha$ is a normal operator.

Conversely let ${\lambda }_1,\dots ,{\lambda }_r$ be the distinct eigenvalues of a normal $\alpha$. The orthonormal eigenbasis from part (ii) reduces the desired identity to $g({\lambda }_j)={\overline{\lambda }}_j$. Lagrange interpolation polynomial provides the polynomialRepeated eigenvalues cause no difficulty because interpolation uses only distinct values. If $V=\{0\}$, use $g=0$. This proves both directions of the third equivalence.

We prove the finite-dimensional spectral theorem for normal operators by induction on dimension. A complex linear operator has an eigenvector $v$ with eigenvalue $\lambda$, by the fundamental theorem of algebra. For a normal operator $T$, the operator $T-\lambda I$ is also normal, andfor every $w$. Applying this to $v$ shows $T^{\ast }v=\overline{\lambda }v$.

Normalize $v$. Its orthogonal complement $W=v^{\perp }$ is invariant under both $T$ and $T^{\ast }$: the adjoint operator identities pair $Tw$ with $v$ through $T^{\ast }v$, and $T^{\ast }w$ with $v$ through $Tv$. The restricted operator on $W$ remains normal, and its adjoint is the restriction of $T^{\ast }$. Induction supplies an orthonormal eigenbasis of $W$, which together with $v$ gives one for $V$.

Conversely, in an orthonormal basis of eigenvectors, $T$ is diagonal and $T^{\ast }$ is the diagonal matrix of the conjugate eigenvalues. The two diagonal operators commute. Thus normality is equivalent to an orthonormal eigenbasis. The zero-dimensional case is immediate.

Use an orthonormal eigenbasis of the Hermitian operator $A$ and set $b_j=⟨{\alpha }_j|B|{\alpha }_j⟩$. Since $B$ is a positive contraction,For $0<r<d$, the missing weight among the first $r$ entries equals the weight in the remaining entries:The ordered eigenvalues satisfy ${\lambda }_j\ge {\lambda }_{r-1}$ for $j<r$ and ${\lambda }_j\le {\lambda }_{r-1}$ for $j\ge r$. ThereforeThis argument does not require the eigenvalues of $A$ to be positive. For $r=0$, positivity and zero trace give $B=0$; for $r=d$, the same argument applied to $I-B$ gives $B=I$. Thus in every caseThe orthogonal projection onto the leading $r$ eigenvectors attains equality. This is the Hermitian effect variational principle, extending the Ky Fan maximum principle to all positive contractions with the prescribed trace.

The absolute value of an operator, trace norm, and operator norm are respectivelyThe positive square root of an operator makes $|L|$ well defined. Its eigenvalues $s_j\ge 0$ are the singular values of $L$, so $\Vert L{\Vert }_1={\sum }_j{s}_j$ and $\Vert L{\Vert }_{\mathrm{op}}={\max }_j{s}_j$.

Use the polar decomposition of a bounded operator $L=U|L|$, with the given unitary operator $U$. In an orthonormal eigenbasis $e_j$ for $|L|$,The operator norm assumption and unitarity imply $|⟨e_j|ZU|e_j⟩|\le \Vert Z{\Vert }_{\mathrm{op}}\le 1$. The triangle inequality therefore yields the required trace estimate:Choosing $Z=U^{†}$ attains equality, which also gives the finite-dimensional trace duality formula $\Vert L{\Vert }_1={\max }_{\Vert Z{\Vert }_{\mathrm{op}}\le 1}|\mathrm{Tr}(ZL)|$. A singular $L$ causes no difficulty: in a finite-dimensional square space the polar factor can be extended to a unitary operator on the complementary subspaces.

Take the real inner productThe stationary distribution is strictly positive for an irreducible Markov chain. Detailed balance gives $⟨Pf,g{⟩}_{\pi }=⟨f,Pg{⟩}_{\pi }$, so $P$ is a self-adjoint operator. Choose a real orthonormal eigenbasis $f_1,\dots ,f_m$, where $m=|S|$, $P{f}_j={\lambda }_j{f}_j$, $f_1\equiv 1$, ${\lambda }_1=1$, and $\pi (f_j)=0$ for $j\ge 2$.

For fixed $y$, apply the spectral decomposition to $g_y(z)=1_{\{y\}}(z)/\pi (y)$. Its coefficient against $f_j$ is $f_j(y)$, whereas $(P^t{g}_y)(x)=P^t(x,y)/\pi (y)$. Thus the spectral kernel expansion of a reversible chain isThis holds for all integers $t\ge 0$; at $t=0$ each multiplier is one, including when ${\lambda }_j=0$. Negative eigenvalues are allowed, and retain their signs for odd $t$.

Use $⟨f,g{⟩}_{\pi }={\sum }_x\pi (x)f(x)g(x)$. The Dirichlet form of a Markov chain isThe equality follows by expanding the square and using row sums one and the stationary distribution identity. For the reversible Markov chain, detailed balance makes $P$ a self-adjoint operator, with real orthonormal eigenbasis $f_1\equiv 1,f_2,\dots ,f_m$ and ordered eigenvalues $1={\lambda }_1>{\lambda }_2\ge \cdots \ge {\lambda }_m$.

Adding a constant changes neither the variance nor the Dirichlet form of a Markov chain. Expand the centered function as $f-\pi (f)={\sum }_{j\ge 2}{a}_j{f}_j$. ThenFor every nonconstant $f$ the quotient is at least $1-{\lambda }_2$, and equality is attained at $f=f_2$. This provesEquivalently minimize the Dirichlet form of a Markov chain over centered unit-norm functions. This is the variational characterization underlying the Poincare inequality for a reversible Markov chain, and does not require the transition matrix to have nonnegative eigenvalues. For a one-state chain there is no nonconstant test function; the displayed minimization concerns $m\ge 2$.

Use the unscaled penalty convention consistent with the displayed bound:For an objective with averaged squared loss, the corresponding penalty parameter would be $\lambda /n$. We retain the unscaled $\lambda$ throughout.

By the representer theorem, the kernel ridge regression minimizer lies in the span of $k(x_i,\cdot )$. A valid coefficient vector is $\hat{a}=(K+\lambda I_n{)}^{-1}Y$, givingThe kernel matrix is a positive semidefinite matrix, so the inverse exists even if $K$ is singular. In the coefficient objective $\Vert Y-Ka{\Vert }_2^2+\lambda a^{T}Ka$, this choice satisfies $K\{(K+\lambda I_n)a-Y\}=0$; there is no need to cancel $K$. The function itself is unique because of the strictly convex squared Hilbert norm. The matrix $H$ is the kernel-ridge hat matrix in the present normalization.

Let $m^0=(f^0(x_i){)}_{i=1}^n$. Since $Y=m^0+\epsilon$, the zero mean and covariance assumption give the exact bias-variance decomposition for linear predictionNo normality of the noise is required for this identity.

Choose an orthonormal eigenbasis $v_i$ of $K$, with eigenvalues $d_i\ge 0$. Its shrinkage factors are $d_i/(d_i+\lambda )$, soThe first bound follows from $(d_i+\lambda {)}^2\ge 4d_i\lambda$ and from each shrinkage factor being at most one.

To control the bias by the Reproducing-kernel Hilbert space norm, for $d_i>0$ defineThe reproducing property gives $⟨g_i,g_{\ell }{⟩}_{\mathcal{H}}={\delta }_{i\ell }$ andIf $d_i=0$, the corresponding unscaled kernel combination has Hilbert norm squared $v_i^{T}K{v}_i=0$, so $v_i^T{m}^0=0$. There is therefore no bias component in a zero-eigenvalue direction. For the remaining directions,The scalar bound is again $(d_i+\lambda {)}^2\ge 4d_i\lambda$, and the final step is Bessel inequality. Combining the variance and bias bounds proves the prediction-risk bound for kernel ridge regression:

Replace coordinate inequalities by the Loewner order and coordinate sums by matrix trace. The maximizing semidefinite program isIts feasible set is the fantope. In an orthonormal eigenbasis of $X$, its objective is ${\sum }_i{\lambda }_i(X)Y_{ii}$, and the diagonal entries of $Y$ belong to the capped simplex. Choosing $Y$ as the orthogonal projection matrix onto the largest $k$ eigenvectors attains the sum of the largest eigenvalues, as in the Ky Fan maximum principle.

The minimizing semidefinite program isFor example, its Lagrangian arises by assigning $S⪰0$ to $I-Y⪰0$, keeping $Y⪰0$ in the domain, and using free $t$ for $\mathrm{tr}Y=k$. Finiteness of the supremum over $Y$ requires $S+tI-X⪰0$.

Equality follows directly by choosing $S$ to have eigenvalues $({\lambda }_i(X)-t{)}_{+}$ in the same orthonormal eigenbasis, with $t$ between the $k$th and $(k+1)$st eigenvalues, or below the smallest one for $k=n$. This is the threshold semidefinite program for the largest eigenvalues, and it also verifies the endpoint case $k=n$.

For a finite irreducible Markov chain with at least two states satisfying detailed balance, its Dirichlet form of a Markov chain obeysExpand $f-\pi (f)$ in an orthonormal eigenbasis. The denominator is ${\sum }_{j\ge 2}{a}_j^2$, and the numerator is ${\sum }_{j\ge 2}(1-{\lambda }_j)a_j^2$. Their ratio is at least $1-{\lambda }_2$ and equality holds for the second eigenfunction. Thus the optimal Poincare inequality for a reversible Markov chain constant is $1/\gamma$, for the ordinary rather than absolute spectral gap.

On a closed manifold with a Riemannian metric, an orthonormal eigenbasis for the positive Laplace-Beltrami operator gives this formula, with eigenvalues counted with multiplicity. Polynomial elliptic bounds and exponential time decay give convergence of every derivative away from time zero. The conjugate is necessary for a complex basis.

For a finite irreducible Markov chain satisfying detailed balance with $\pi$, its transition matrix is a self-adjoint operator for $⟨f,g{⟩}_{\pi }={\sum }_x\pi (x)f(x)g(x)$. For a real orthonormal eigenbasis $(f_j)$ with eigenvalues $({\lambda }_j)$,Indeed, apply the spectral decomposition of $P^t$ to the function $1_{\{y\}}/\pi (y)$, whose coefficient against $f_j$ is $f_j(y)$. For $t=0$, every eigenvalue multiplier is interpreted as one.

For random walk on $\{-1,1{\}}^n$ that chooses a coordinate uniformly and flips it with probability $1/2$, the Walsh characters $f_J(x)={\prod }_{j\in J}{x}_j$ form an orthonormal eigenbasis under the uniform distribution on a finite set. Flipping a coordinate in $J$ negates $f_J$, so $P{f}_J=(1-|J|/n)f_J$. Hence $1-k/n$ has multiplicity $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$, and the ordinary and absolute spectral gaps both equal $1/n$.

For a real symmetric matrix $X$ with eigenvalues ${\lambda }_1\ge \cdots \ge {\lambda }_n$, the sum of its $k$ largest eigenvalues is the support function of the fantope:Here $⪯$ is the Loewner order. In an orthonormal eigenbasis for $X$, the objective depends only on the diagonal entries of $Y$, which lie in the capped simplex. Thus the identity reduces to the sum of the largest components of the eigenvalues.