Codex @codex  0

Insert the complete orthonormal basis of energy eigenstates on either side of the Boltzmann factor. The spectral theorem givesAt low temperature, the gap $\hslash \omega$ suppresses excited energy eigenstates. The harmonic oscillator eigenfunction of the ground state isThereforeThe common zero-point energy factor cancels. Dividing the kernel by its trace would give the position probability density of the canonical ensemble; at zero temperature this tends to $|{\phi }_0(x){|}^2$, whose variance is $\hslash /(2m\omega )$. Thus zero temperature projects onto the ground state and retains its quantum spread, rather than concentrating at the minimum of the classical potential energy.

There is also a check on the first correction. With $q=\sqrt{m\omega /\hslash }x$, the first excited harmonic oscillator eigenfunction satisfies $|{\phi }_1(x){|}^2=2q^2|{\phi }_0(x){|}^2$ and ${\phi }_1(0)=0$. Hence the spectral theorem gives $R=e^{-q^2}[1+2q^2{e}^{-z}+O(e^{-2z})]$, in agreement with part (c).

Proceed by induction on the dimension. For positive dimension, the fundamental theorem of algebra gives a root of the characteristic polynomial, hence a nonzero eigenvector $v$. Normalize it to have norm one. Its span is an invariant subspace, and part (ii) makes its orthogonal complement invariant too:The restriction of $T$ to the complement remains skew-adjoint, since the same inner product identity holds there. The induction hypothesis supplies an orthonormal eigenbasis for that smaller space. Adjoining $v$ gives an orthonormal eigenbasis for $V$.

The zero-dimensional base case is immediate. Thus $T$ is diagonalizable, indeed unitarily diagonalizable. This proves the finite-dimensional case of the spectral theorem for a skew-adjoint operator without assuming that distinct eigenvalues have multiplicity one.

For a self-adjoint operator on a finite-dimensional complex inner product space, every eigenvalue is real and eigenspaces for distinct eigenvalues are orthogonal. The spectral theorem gives an orthonormal eigenbasis. Accordinglyand the $E_i$ are orthogonal projections satisfying $E_i^{\ast }=E_i$. Since $T$ is nonsingular, none of its eigenvalues is zero. Its representing matrix in the orthonormal eigenbasis is real diagonal.

The finite-dimensional spectral theorem says that a self-adjoint operator on a complex inner-product space has an orthonormal basis of eigenvectors and all its eigenvalues are real. Equivalently, its matrix is unitarily diagonalisable with real diagonal entries.

For $a\in \mathbb{R}$, the matrix is equal to its conjugate transpose:Thus it represents a self-adjoint operator for the standard inner product on ${\mathbb{C}}^3$. The theorem applies directly, proving

For a nonzero eigenvector $u$ of $S^{\ast }S$,Therefore $\overline{\lambda }=\Vert Su{\Vert }^2/\Vert u{\Vert }^2$ is real and nonnegative, and so every eigenvalue $\lambda$ is real and nonnegative.

The preceding adjoint identities give $(S^{\ast }S{)}^{\ast }=S^{\ast }S$, so this linear operator is self-adjoint. The stated finite-dimensional spectral theorem supplies an orthonormal basis $e_j$ with $S^{\ast }S{e}_j={\lambda }_j{e}_j$. If $v={\sum }_j{c}_j{e}_j$, thenSince ${\lambda }_{-}\le {\lambda }_j\le {\lambda }_{+}$,Taking nonnegative square roots provesThe square roots of these extreme eigenvalues are the smallest and largest singular values of $S$; the lower bound can be zero if $S$ has a nontrivial kernel of a linear map.

By the spectral theorem, the nonscalar unitary V has orthonormal eigenvectors $|v_0⟩,|v_1⟩$ with distinct eigenvalues ${\lambda }_0\ne {\lambda }_1$. Choose $|b⟩=(|v_0⟩+|v_1⟩)/\sqrt{2}$. Then $V|b⟩=({\lambda }_0|v_0⟩+{\lambda }_1|v_1⟩)/\sqrt{2}$ is not proportional to $|b⟩$.

On the product input $|+⟩\otimes |b⟩$, the controlled unitary gate producesIts two conditional target vectors are linearly independent, so the conditional-vector product-state criterion proves that the output is entangled. Equivalently, in the control computational basis and target eigenbasis its coefficient matrix is $\frac{1}{2}\left(\begin{array}{cc}1& 1\\ {\lambda }_0& {\lambda }_1\end{array}\right)$, whose determinant is $({\lambda }_1-{\lambda }_0)/4\ne 0$. Thus U is an entangling gate. The excluded scalar case would only apply a phase gate to the control and could not entangle the factors; this is the controlled-unitary entangling criterion.

Interpret boundedness above uniformly: there is an $M<\infty$ such that $B^k⪯MI$ for every $k$. Since $B^k$ is a positive-definite symmetric matrix, the spectral theorem implies $(B^k{)}^{-1}⪰M^{-1}I$. ThereforeCombining the Armijo condition with ${\alpha }^k\ge C>0$ yieldsIf $f\ge L$, a telescoping sum givesThe nonnegative series converges, so its terms tend to zero:This proves first-order global convergence in the sense of stationarity from uniformly bounded quasi-Newton matrices. It does not imply that every nonconvex objective function reaches a global minimum, or that the iterates themselves converge. Every finite limit point is a stationary point, by continuity of the gradient.

The continuous functional calculus for a Hermitian element of a C-star algebra identifies its generated unital C-star algebra with continuous functions on its real spectrum, preserves the involution and norm, and sends functions to the corresponding spectral values by spectral mapping. Consequently an element is a square of a Hermitian element of a C-star algebra exactly when it is a Hermitian element of a C-star algebra with nonnegative spectrum: the reverse direction uses the continuous square root on that spectrum.

Nonnegative scalar multiples preserve this property directly. For positive $a,b$ put $C=\Vert a\Vert +\Vert b\Vert$. Functional calculus gives $\Vert \Vert a\Vert 1-a\Vert \le \Vert a\Vert$ and similarly for $b$, so $\Vert C1-(a+b)\Vert \le C$. The sum is a Hermitian element of a C-star algebra, and spectral mapping now places its spectrum in $[0,2C]$. It therefore has a positive square root in a C-star algebra. If $C=0$ both elements are zero. Thus $A_{+}$ is a cone. It is pointed because an element positive with its negative has spectrum contained in $\{0\}$ and hence is zero by the self-adjoint norm formula. It is closed as well: for a converging sequence of Positive elements of a C-star algebra use a common norm bound $C$ and pass to the limit in $\Vert C1-a_n\Vert \le C$.

For the two-by-two matrix the exact criterion isA positive matrix is Hermitian with nonnegative eigenvalues; evaluating its quadratic form at the coordinate vectors gives the diagonal conditions, and its determinant, the eigenvalue product, gives the final inequality. Conversely if $a_{11}>0$, completing the square writes the quadratic form as $a_{11}|z_1+(a_{12}/a_{11})z_2{|}^2+(a_{22}-|a_{12}{|}^2/a_{11})|z_2{|}^2$, which is nonnegative. If $a_{11}=0$, the determinant inequality forces $a_{12}=0$ and the conclusion is immediate. The spectral theorem then gives nonnegative eigenvalues and their Hermitian square root, proving positivity in the question's sense.

Interpret the paper's unspecified $\Omega$ as containing $B_1$, the domain on which the coefficients are used. Write $A(x)=(a_{ij}(x))$, a real symmetric matrix. The strict ellipticity condition is pointwise positive definiteness:The lower bound may depend on $x$. By continuity, strict ellipticity gives a positive lower bound on each compact subset of $B_1$, but does not require one bound throughout the whole open ball.

With the two-constant convention used in the next part, uniform ellipticity meansBoth constants are independent of $x$. Some terminology uses uniform ellipticity for just the lower bound and states coefficient boundedness separately; here the paper supplies both constants. The spectral theorem for the symmetric matrix gives $|A(x)\xi |\le \Lambda |\xi |$. For example, $A(x)=(1-|x{|}^2)I$ satisfies strict ellipticity in $B_1$ but has no uniform positive lower bound as $|x|\uparrow 1$.

For any normalized vector $|u⟩$, the Born rule assigns the probability $⟨u|\rho |u⟩$ to the corresponding rank-one orthogonal projection. This must be nonnegative for every $u$, which is exactly positive semidefiniteness. For any complete orthonormal basis $\{|j⟩\}$, the outcome probabilities must sum to one:Thus a Hermitian matrix represents a physical density matrix only ifThese conditions are also sufficient in finite dimension. The spectral theorem writes $\rho ={\sum }_j{p}_j|u_j⟩⟨u_j|$ with $p_j\ge 0$ and ${\sum }_j{p}_j=1$, describing a quantum state ensemble of pure states with valid mixing probabilities. A Hermitian matrix alone could have negative eigenvalues, hence negative measurement probabilities.

For a Hermitian matrix $A$, the spectral theorem gives $A=U\mathrm{diag}({\lambda }_1,\dots ,{\lambda }_d)U^{†}$, with real eigenvalues and a unitary matrix $U$. HenceThe square root here is the unique positive square root of an operator. Taking the trace, which is unchanged by unitary similarity, provesFor a density matrix, all eigenvalues are nonnegative and sum to one. Its trace norm is thereforeThe absolute values cannot be omitted for a general Hermitian matrix, since positive and negative eigenvalues can cancel in its trace but never in its trace norm.

Proceed by induction on $\dim V$. The result is immediate for dimension zero. In positive dimension, the characteristic polynomial has a root over the complex numbers, so there is a nonzero eigenvector $v$ with eigenvalue $\lambda$. Normalize it to have norm one. Self-adjointness givesso $\lambda$ is real.

The orthogonal complement $v^{\perp }$ is an invariant subspace: if $w\perp v$, thenThe restriction of $T$ to $v^{\perp }$ is again self-adjoint, since the same inner product identity holds on that subspace. By induction it has an orthonormal basis of eigenvectors. Adjoining $v$ givesThe existence of the first eigenvector is the essential use of the complex numbers in this proof of the finite-dimensional spectral theorem.

The finite-dimensional spectral theorem diagonalizes the Hermitian matrix in its orthonormal eigenbasis. The determinant is the product of the eigenvalues:

The matrix is real symmetric, so the spectral theorem guarantees an orthonormal basis of eigenvectors. Its characteristic determinant factors asSolving the three corresponding equations for the null space gives the normalized eigenvectorsTheir pairwise inner products vanish. With these vectors as columns,Since $Q^{T}Q=I$, this also gives $A=Q\mathrm{diag}(6,-3,1)Q^T$.

If $Mv=\lambda v$ for a nonzero eigenvector, then $M^2=M$ implies $({\lambda }^2-\lambda )v=0$, hence $\lambda \in \{0,1\}$. Conversely, the real-symmetric spectral theorem gives $M=Q\Lambda Q^T$ with orthogonal $Q$. If every diagonal entry of $\Lambda$ is zero or one, then ${\Lambda }^2=\Lambda$ and therefore $M^2=M$. Thus the necessary and sufficient condition isSuch a symmetric idempotent matrix is the orthogonal projection onto its eigenvalue-one eigenspace, with its eigenvalue-zero eigenspace as the kernel. Diagonalizability is essential to the sufficiency argument from eigenvalues alone; symmetry supplies it here.

We prove uniform approximation, not just approximation in $L^2$. The analytic facts used are: a continuous square-integrable kernel gives a compact integral operator on $L^2$; the spectral theorem for compact self-adjoint operators decomposes the closure of its range into its finite-dimensional nonzero eigenspaces; and continuous functions are dense in $L^2$ for normalized Haar measure on a compact Lie group. Normalized Haar measure on a compact group is both left- and right-invariant and is preserved by inversion.

Choose a continuous nonnegative function $k$ of integral one, supported in a sufficiently small symmetric neighborhood of the identity, with $k(g^{-1})=k(g)$. Such functions are obtained from a local bump and its inverted bump followed by normalization. Define the convolution operatorIts kernel is continuous on $G\times G$, so $T$ is compact. The symmetry of $k$ makes it self-adjoint. It commutes with the left translations $(L_{g}h)(x)=h(g^{-1}x)$ by a change of variable $y=gz$.

By Cauchy-Schwarz inequality and invariance of Haar measure,The same integral formula and continuity of the kernel show $Th$ is continuous for every $h\in L^2(G)$. Moreover, rewriting $y=x{z}^{-1}$ gives $(Tf)(x)=\int f(x{z}^{-1})k(z)dz$. Uniform continuity on the compact group therefore makes $\Vert Tf-f{\Vert }_{\infty }$ arbitrarily small when the support of $k$ is small. Also $\Vert T{\Vert }_{\infty \to \infty }\le 1$ because $k\ge 0$ and has integral one.

Fix $\epsilon >0$ and take $k$ so $\Vert Tf-f{\Vert }_{\infty }<\epsilon /3$. ThenLet $P_N$ be the orthogonal projection onto increasing finite sums of the nonzero eigenspaces of $T$. Since $Tf$ lies in the closure of the range, the spectral theorem gives $P_{N}Tf\to Tf$ in $L^2$. Applying the smoothing estimate givesThus some $h=T{P}_{N}Tf$ satisfies $\Vert h-f{\Vert }_{\infty }<\epsilon$.

Each nonzero eigenspace is finite dimensional, invariant under $L_g$, and consists of continuous functions: if $Tv=\lambda v$ with $\lambda \ne 0$, then $v=Tv/\lambda$. The finite sum $M$ containing $h$ therefore carries the finite-dimensional unitary representation $\rho (g)=L_g{|}_M$. It is continuous, since translating each of its finitely many continuous basis functions depends continuously on $g$ in the uniform and hence the $L^2$ norm.

Let $\ell$ be evaluation at the identity on $M$, and let the dual representation on $M^{\ast }$ be $\theta (g)\ell =\ell \circ \rho (g^{-1})$. For the linear functional $L_h$ on $M^{\ast }$ defined by $L_h(u)=u(h)$,The rank-one endomorphism $\alpha =\ell \otimes L_h$ of $M^{\ast }$ satisfies $\mathrm{tr}(\alpha \theta (g))=L_h(\theta (g)\ell )$. ThereforeThis is the requested Peter-Weyl theorem, proved via the convolution proof of uniform Peter-Weyl approximation. The extra convolution after the spectral truncation is what upgrades the $L^2$ estimate to a uniform one.

To deduce a faithful finite-dimensional representation, first note that these representations separate points. For $g\ne e$, choose a continuous function taking different values at $g$ and $e$, and approximate it closely enough by a trace coefficient to retain that difference. The representation appearing in that trace must satisfy $\theta (g)\ne I$.

There is an identity neighborhood $U$ containing no nontrivial subgroup. Here is the Lie groups have no small subgroups argument: choose an injective exponential chart on a Lie-algebra ball of radius $r$, and take $U=\exp (B_{\delta })$ with $0<\delta <r/2$. If a subgroup contained a nonidentity $\exp X$ in $U$, choose the first integer $m$ with $m\Vert X\Vert \ge \delta$. Then $\delta \le m\Vert X\Vert <2\delta <r$, so its power $\exp (mX)$ lies outside $U$, a contradiction. For a zero-dimensional group, take $U=\{e\}$.

For every $g\notin U$, choose a representation nontrivial at $g$. The sets on which these representations are not the identity are open and cover the compact set $G\setminus U$. A finite subcover gives finitely many representations, whose direct sum has kernel contained in $U$. A subgroup contained in $U$ is trivial, so this direct sum is faithful. Averaging its Hermitian form makes it unitary. Thus the finite faithful representation from point-separating representations yieldsUsing the no-small-subgroups neighborhood is essential; $G\setminus \{e\}$ alone need not be compact, so a finite-subcover argument on that punctured set would not be valid.

Principal component analysis replaces correlated measurements by orthogonal linear coordinates ordered by their variance. For centered observations collected in an $n\times p$ matrix $Z$, write the sample covariance matrix as $S=Z^{T}Z/(n-1)$. A unit loading vector $a$ gives score vector $Za$ with sample variance $a^{T}Sa$. The Rayleigh quotient is maximized by a unit eigenvector of $S$ for its largest eigenvalue.

The subsequent principal components maximize the same quadratic form subject to orthogonality to the earlier loading vectors. By the spectral theorem, if $S=Q\Lambda Q^T$ with descending eigenvalues, the scores $ZQ$ have diagonal covariance $\Lambda$. Their fractions of explained variance are ${\lambda }_j/{\sum }_i{\lambda }_i$. Repeated eigenvalues identify an eigenspace rather than a unique axis.

Keeping the first $q$ principal components gives the rank-$q$ reconstruction $\hat{Z}=Z{Q}_q{Q}_q^T$. Its squared reconstruction error isFor any rank-$q$ orthogonal projection $P$, retained variance is $\mathrm{tr}(SP)={\sum }_j{\lambda }_j{q}_j^{T}P{q}_j$. The weights $q_j^{T}P{q}_j$ lie in $[0,1]$ and sum to $q$, so this is at most the sum of the largest $q$ eigenvalues. Projecting onto any candidate reconstruction subspace is its best least-squares reconstruction; this proves the minimum-error property and agrees with the singular value decomposition. Thus PCA finds the linear subspace preserving the greatest variance, equivalently minimizing squared reconstruction error. The upper-left sketch shows the first axis aligned with the elongated cloud; the second is perpendicular. A scree plot and substantive interpretability help choose $q$.

These methods depend on measurement scale. A variable measured in large numerical units can dominate covariance-based principal component analysis; standardizing variables gives principal component analysis on a correlation matrix. Scores summarize patterns, but the method neither establishes causation nor guarantees that the largest-variance directions best predict a separate response.

Let $B=A^{\mathsf{T}}A$. Since $\det A>0$, $B$ is a positive-definite matrix. The spectral theorem gives a unique principal square root of a positive semidefinite matrixThen $R^{\mathsf{T}}R=U^{-1}B{U}^{-1}=I$ and $\det R=\det A/\det U=1$, so $R$ is a rotation matrix. Define $V=RU{R}^{\mathsf{T}}$. It is a symmetric matrix, is positive definite, and satisfies $V^2=A{A}^{\mathsf{T}}$. Consequently the polar decomposition in continuum mechanics isHere $U$ and $V$ are the right stretch tensor and left stretch tensor.

For the Cauchy stress tensor, use both material isotropy and material frame indifference. Their respective transformation laws areThe first law and $A=VR$ give $\sigma (A)=\sigma (V)$. Combining the two laws gives $\sigma (QV{Q}^{\mathsf{T}})=Q\sigma (V)Q^{\mathsf{T}}$. In a principal stretch basis, $V=\mathrm{diag}({\lambda }_1,{\lambda }_2,{\lambda }_3)$. Each half-turn about a coordinate axis leaves $V$ unchanged; its conjugation changes the signs of the corresponding off-diagonal stress tensor entries. Those entries must therefore vanish. If two principal stretches coincide, rotations within their eigenspace additionally force the stress tensor to be scalar on that eigenspace. Thus the Cauchy stress tensor and left stretch tensor have common principal axes, including at repeated principal stretches. This proves coaxiality of isotropic elastic stress.

The precise symmetry conclusion is equivariance of isotropic principal stresses. Every permutation of the principal stretches can be realized by a signed permutation rotation matrix, sowhen the indexing is permuted consistently. Equivalently, permuting the arguments permutes the labelled principal stresses in the same way. In particular, ${\sigma }_1$ is symmetric in ${\lambda }_2,{\lambda }_3$, and analogous statements hold for ${\sigma }_2,{\sigma }_3$.

For distinct principal stretches, interpolate the three values ${\sigma }_i$ at the three points ${\lambda }_i$:Uniqueness of this interpolation implies that the scalar coefficients ${\beta }_j$ are symmetric functions of the unordered principal stretches; they may be expressed through the elementary symmetric invariants. Smooth isotropic constitutive laws have the corresponding invariant representation across repeated stretches as well. The wording about symmetric functions must be understood in this collective sense: each labelled principal stress need not be symmetric in all three arguments. For example, the objective isotropic law $\sigma =V^2$ has ${\sigma }_i={\lambda }_i^2$, which disproves that stronger interpretation.

Proceed by induction on $\dim V$. The zero-dimensional case has the empty orthonormal basis. In positive dimension, the fundamental theorem of algebra gives a root of the characteristic polynomial, hence a unit eigenvector $e$ of $\alpha$, say with eigenvalue $\lambda$. Part (ii) makes it an eigenvector of ${\alpha }^{\ast }$ as well. Thus the line spanned by $e$ and its orthogonal complement are invariant under both operators by the introductory adjoint argument.

On $\{e{\}}^{\perp }$, the restriction of ${\alpha }^{\ast }$ is the adjoint of the restriction of $\alpha$, and the restrictions still commute. The restricted linear operator is therefore normal. By induction it has an orthonormal basis of eigenvectors. Adjoining $e$ proves an orthonormal eigenbasis exists for $V$, establishing the finite-dimensional spectral theorem by construction.

For the final deduction, use this orthonormal basis $e_j$ and write $\alpha e_j={\lambda }_j{e}_j$. DefineThe real nonnegative diagonal entries make $\beta$ a Hermitian operator, and the modulus-one diagonal entries make $\gamma$ a unitary operator. Both are diagonal in the same orthonormal basis, so they commute and $\beta \gamma e_j={\lambda }_j{e}_j$ even when ${\lambda }_j=0$. This proves the required factorization without assuming invertibility.

Conversely, if $\alpha =\beta \gamma$ with ${\beta }^{\ast }=\beta$, ${\gamma }^{\ast }\gamma =\gamma {\gamma }^{\ast }=I$, and $\beta \gamma =\gamma \beta$, then ${\alpha }^{\ast }={\gamma }^{\ast }\beta$ andThus $\alpha$ is normal. Normality is equivalent to a commuting Hermitian–unitary factorization, with the Hermitian factor even selectable nonnegative. This is the polar decomposition with a unitary extension on the kernel.

Let $G$ be a finite undirected $d$-regular graph on $N$ vertices, with adjacency matrix $A$ and normalized random walk matrix $P=A/d$. Define edge expansion and normalized conductance byAn expander family has orders tending to infinity, uniformly bounded maximum degree, and a uniform positive lower bound on $h$. For a regular graph the constant vector is an eigenvector of $P$ with eigenvalue one. Write its eigenvalues as $1={\mu }_1\ge {\mu }_2\ge \cdots \ge {\mu }_N\ge -1$, and let $\delta =1-{\mu }_2$. This spectral gap measures the energetic cost of departing from a constant function.

For every mean-zero vector $f$, the spectral theorem and the graph's energy identity giveApply this to $f=1_S-|S|1/N$. Its norm squared is $|S|(1-|S|/N)$ and its energy is $e(S,S^c)/d$. ThereforeThus a uniform spectral gap gives uniform edge expansion when $d$ is fixed. This also bounds exterior vertex expansion: each exterior vertex accounts for at most $d$ boundary edges, so $|N(S)\setminus S|\ge e(S,S^c)/d$.

For the converse, take a mean-zero eigenvector $f$ for ${\mu }_2$ and choose its sign so that its positive support has at most $N/2$ vertices. Put $g=f^{+}$, which is nonzero. Truncation decreases energy in the following precise sense: for any two real numbers $a,b$,Summing over edges yields $⟨g,(I-P)g⟩\le ⟨g,(I-P)f⟩=\delta \Vert g{\Vert }_2^2$. For the threshold sets $S_t=\{v:g(v{)}^2>t\}$, every nonempty set lies in that small positive support. Integrating its boundary count gives the layer-cake identityThe Cauchy-Schwarz inequality bounds the left side bybecause the first sum is at most $d\delta \Vert g{\Vert }_2^2$ and the second at most $2d\Vert g{\Vert }_2^2$. Cancelling proves the Cheeger inequality in both directions:Hence bounded-degree regular families have uniform edge expansion exactly when their second-largest normalized eigenvalue stays uniformly below one.

Absolute eigenvalues give additional information. Put $\rho ={\max }_{i\ge 2}|{\mu }_i|$. Centering the indicators of $S,T$ and applying the operator-norm bound on the mean-zero subspace proves the expander mixing lemma:Here $e(S,T)=1_S^{T}A{1}_T$, so internal edges are counted as oriented incidences. A small $\rho$ makes edge counts resemble uniformly distributed edges. It also gives rapid random walk mixing: starting at a vertex, $P^t$ contracts the mean-zero component of its point mass by at most ${\rho }^t$ in Euclidean norm; Cauchy-Schwarz inequality then gives total variation distance at most $\frac{1}{2}\sqrt{N}{\rho }^t$ from the uniform distribution. A bipartite graph has eigenvalue $-1$ and its non-lazy walk alternates sides, even if it has good edge expansion. The lazy walk $(I+P)/2$ has nonconstant eigenvalues between zero and $1-\delta /2$, resolving this periodicity. It is important to distinguish the gap $1-{\mu }_2$ controlling cuts from the absolute bound controlling non-lazy mixing.

Here is a fully specified deterministic construction of an infinite family. Its degree is large but fixed. SetChoose the lexicographically first ordered list $a_1,\dots ,a_d\in W$ satisfyingThis finite deterministic search terminates. To prove existence, choose the list uniformly and independently. For each nonzero $u$, its signs are independent unbiased signs; the exponential-moment estimate $\cosh t\le e^{t^2/2}$ and Markov inequality give an exceptional probability at most $2e^{-d/200}$. A union bound gives total failure probability at mostThus at least one qualifying list exists. Fix it once and for all.

Let $H$ be the Cayley graph on $W$ whose $j$th neighbor of $x$ is $x+a_j$. It is an undirected $d$-regular port-labeled graph, allowing repeated edges and loops in this intermediate construction. Its characters $x\mapsto (-1{)}^{u\cdot x}$ form an orthogonal eigenbasis, with the displayed averages as normalized eigenvalues. Therefore $\rho (H)\le 1/10$. Each loop counts as one transition port; degrees here mean row sums of the adjacency matrix.

We next define the zig-zag product and prove the bound used for iteration. A port labeling of a $D_0$-regular undirected graph $F$ gives an involution ${\mathrm{Rot}}_F(v,a)=(w,b)$, recording the endpoint and reverse port. If a $d$-regular graph $H_0$ has vertex set $[D_0]$, the product has vertices $(v,a)\in V(F)\times [D_0]$. For each ordered pair of small-graph ports, move from $a$ to $a^{\prime }$ in $H_0$, follow the big edge ${\mathrm{Rot}}_F(v,a^{\prime })=(w,b^{\prime })$, and move from $b^{\prime }$ to $b$ in $H_0$. The endpoint is $(w,b)$; reversing the steps reverses the two small-graph port labels. The product is undirected, has $|V(F)|D_0$ vertices, and has degree $d^2$.

Write $B=I\otimes P_{H_0}$ and let $R$ be the permutation matrix of ${\mathrm{Rot}}_F$. The normalized product operator is $BRB$. For a mean-zero unit vector, decompose $f=u+v$ into its cloud-constant part and its cloud-orthogonal part. Then $Bu=u$, $\Vert Bv\Vert \le \rho (H_0)\Vert v\Vert$, and $\Vert R\Vert =1$. The compression of $R$ to cloud-constant vectors is exactly $P_F$, so $|⟨u,Ru⟩|\le \rho (F)\Vert u{\Vert }^2$. Expanding the quadratic form and applying Cauchy-Schwarz inequality givesThe operator is symmetric, so its mean-zero operator norm is bounded by this same quantity. No unproved product spectral estimate is needed.

Start with the loop-inclusive complete graph $G_0$ on $D$ vertices, whose normalized matrix is $J/D$ and whose nonconstant eigenvalues are all zero. Given a $D$-regular $G_t$, its two-step graph $G_t^2$ has degree $D^2$ and normalized operator $P_{G_t}^2$. Label a two-step edge by its ordered pair of ports; reversal reverses the path and its reverse ports. These $D^2$ labels are the vertex set of the fixed graph $H$. DefineIt has degree $d^2=D$, and its number of vertices is $N_{t+1}=N_t{D}^2$, hence $N_t=D^{2t+1}$. By the proved bound,Starting from zero, induction gives $\rho (G_t)\le 1/2$, since $(1/2{)}^2+21/100=46/100<1/2$. The cut-energy argument therefore gives multiplicity-counted edge expansion at least $D/4$ for every $G_t$.

To obtain ordinary simple graphs, delete loops and merge parallel edges. The maximum degree is at most $D$, and any one unordered vertex pair had multiplicity at most $D$. Thus every cut retains at least $1/D$ of its multiplicity-counted boundary, givingThese simple graphs form an expander family. Every choice is deterministic: the finite base search is fixed independently of $t$, and the recursive edge rules determine all subsequent adjacency lists. Once that base is fixed, adjacency lists can be generated successively using the previous lists, with a constant amount of work per output edge. This is squaring and zig-zag iteration yields bounded-degree expanders. The spectral argument supplies the uniform expansion guarantee and explains why squaring improves the eigenvalues while the product restores a constant degree.