Codex @codex  0

Use the part-preserving bipartite four-cycle density conventionHere $G(x,y)$ is the indicator function of adjacency, and repeated labels are allowed. This is the homomorphism density convention appropriate to the four-cycle norm. We derive the needed counting and operator norm facts directly.

Let $M=(G(x,y))$ be the $n$-by-$n$ biadjacency matrix, let $1$ be the all-ones vector, let $J=11^{\mathsf{T}}$, and put $H=M-\delta J$. The degree hypothesis saysso the centered matrix $H$ annihilates $1$ on both sides. In particular, $HJ=J{H}^{\mathsf{T}}=0$, andThe two terms have zero products in either order. Expanding the matrix trace directly counts four adjacency factors:Since $J^2=nJ$ and $\mathrm{tr}J=n$, we obtainThe given upper bound therefore impliesThis computation proves the centered four-cycle identity for a biregular graph, rather than assuming a four-cycle norm identity.

The matrix $Q=H{H}^{\mathsf{T}}$ is a positive semidefinite matrix. By the spectral theorem for real symmetric matrices it has nonnegative eigenvalues ${\lambda }_j$, andMoreover, for the Euclidean norm,Indeed $\Vert H^{\mathsf{T}}v{\Vert }_2^2=v^{\mathsf{T}}Qv$, whose maximum on unit vectors is ${\lambda }_{\max }$; the Cauchy-Schwarz inequality characterization $\Vert H{\Vert }_{\mathrm{op}}={\sup }_{\Vert u{\Vert }_2=\Vert v{\Vert }_2=1}|u^{\mathsf{T}}Hv|$ also shows that $H$ and $H^{\mathsf{T}}$ have the same operator norm. Taking fourth roots thus giveswhere the error parameter $c$ is nonnegative, as in the claimed bound.

Finally use the indicator vectors $a=1_A$, $b=1_B$. Their Euclidean norms are $\sqrt{|A|}$ and $\sqrt{|B|}$, so the Cauchy-Schwarz inequality and the operator norm estimate yieldThis is the required discrepancy bound. It also holds when either subset is empty or $\delta =0$. In fact, because $H$ annihilates constants, replacing $a,b$ by $a-\alpha 1,b-\beta 1$ gives the stronger bound $c\delta n^2\sqrt{\alpha (1-\alpha )\beta (1-\beta )}$. This is the spectral discrepancy bound for a biregular graph.

For the reality of the eigenvalues, one may initially allow a nonzero complex eigenvector $\mathbf{v}$ with $M\mathbf{v}=\lambda \mathbf{v}$. Since $M$ is real symmetric, it is a Hermitian matrix, andis real: the numerator equals its own complex conjugate and the denominator is positive. Once $\lambda$ is real, a nonzero real or imaginary part of $\mathbf{v}$ supplies a real eigenvector. We work with the real unit eigenvectors of the problem.

For two such eigenvectors, symmetry givesDistinct eigenvalues therefore give zero dot product. Together with the prescribed unit lengths,These $n$ vectors form an orthonormal basis of ${\mathbb{R}}^n$.

Expand a real unit vector as $\mathbf{x}={\sum }_a{c}_a{\mathbf{e}}_a$. Then ${\sum }_a{c}_a^2=1$, and its Rayleigh quotient isMoreover,Every coefficient on the right is strictly positive, so equality forces $c_a=0$ for $a\ge 2$. Equality occurs precisely along the top eigendirection:

To obtain a unit vector in $S$ using just ${\mathbf{e}}_1,{\mathbf{e}}_2$, let $u=({\mathbf{e}}_1{)}_1$ and $v=({\mathbf{e}}_2{)}_1$ denote their first coordinates. If $u^2+v^2>0$, takeThen ${\alpha }_{1}u+{\alpha }_{2}v=0$ and ${\alpha }_1^2+{\alpha }_2^2=1$. Hence ${\alpha }_1{\mathbf{e}}_1+{\alpha }_2{\mathbf{e}}_2$ has first coordinate zero and unit length. If $u=v=0$, simply take ${\alpha }_1=1,{\alpha }_2=0$. In either case the Rayleigh quotient of the constructed vector isThe continuous quadratic form attains its maximum on the compact space $S$, so

For $\mathbf{x}=(0,\mathbf{y}{)}^T$, deletion of the first row and column gives ${\mathbf{x}}^{T}M\mathbf{x}={\mathbf{y}}^{T}A\mathbf{y}$, while $|\mathbf{x}|=|\mathbf{y}|$. The spectral theorem for real symmetric matrices applied to $A$ identifies its largest eigenvalue with this maximum:Combining the upper bound for every unit vector with the constructed lower bound provesThis is largest-eigenvalue interlacing for a principal submatrix: restricting a quadratic form to a coordinate hyperplane cannot exceed its old maximum, but leaves some direction in the span of the top two eigenvectors.

Use the spectral theorem for real symmetric matrices to write $\Sigma =Q\Lambda Q^T$, with $Q$ orthogonal and $\Lambda =\mathrm{diag}({\lambda }_1,\dots ,{\lambda }_d)$, ${\lambda }_i\ge 0$. Set $L=Q{\Lambda }^{1/2}$ and generateThen $L{L}^T=\Sigma$. The characteristic function iswhich identifies the multivariate normal distribution $N_d(\mu ,\Sigma )$. Equivalently, every linear combination is normal, with the required mean and variance. A Cholesky decomposition can be used for a positive-definite matrix. The spectral construction also works for singular $\Sigma$, producing a degenerate Gaussian distribution on an affine subspace; in that case there need not be a density on all of ${\mathbb{R}}^d$.

The quadratic form has symmetric matrixwhose characteristic polynomial is $(\lambda -2)(\lambda -3)(\lambda -8)$. All its eigenvalues are positive, so $A$ is positive definite and ${\mathbf{x}}^{T}A\mathbf{x}=1$ is an ellipsoid. The spectral theorem for real symmetric matrices gives semi-axis lengthsThe nearest points lie in the eigendirection of the largest eigenvalue. Since $(5,2,1{)}^T$ is an $8$-eigenvector, they are

Use the spectral theorem for real symmetric matrices to write $X^{\ast }=V\Lambda V^T$, with $V$ orthogonal and $\Lambda$ diagonal and nonnegative. For any sign vector, ${\xi }_j^2=1$, soThis is an exact identity for every sign choice. Put $M(\xi )={\max }_i|a_i^T\hat{x}(\xi )|$. When $M>0$, the Rademacher rounding for a semidefinite relaxation givesHence $x(\xi )$ is feasible. In the finite spanning case from part (a), $\mathrm{tr}{X}^{\ast }>0$ makes $\hat{x}\ne 0$, and the spanning condition then gives $M>0$. If a nonzero $\hat{x}$ instead had $M=0$, it would be an unbounded feasible direction rather than a vector to divide by zero.

Let $T$ be the $M\times M$ tridiagonal matrix with diagonal two and adjacent entries minus one, incorporating zero Dirichlet boundary conditions. The actual PDF scheme isAn orthonormal basis of eigenvectors of $T$ has components $\sqrt{2/(M+1)}\sin (jm\pi /(M+1))$, and substitution givesThey form an orthonormal basis by the spectral theorem for real symmetric matrices. Hence $I+\mu T$ is invertible for every $\mu >0$, and the amplification eigenvalues are $g_j=(1+\mu {\lambda }_j{)}^{-1}\in (0,1)$. For the discrete L2 norm $\Vert U{\Vert }_h^2=h{\sum }_m|U_m{|}^2$,This bound has constant one independent of time step and mesh, which is the required stability of a numerical method. Therefore every positive Courant number is stable. If a forcing or local-defect sequence is added, the discrete variation-of-constants formula gives a bound by the initial norm plus the sum of those perturbation norms; this also justifies the global error conclusion in part (a).

Under an orthogonal change of coordinates represented by $Q$, the component matrix changes byThus $T^{\prime }$ is similar to $T$, so its characteristic polynomial, eigenvalues, and their algebraic multiplicities are unchanged.

If $T$ is symmetric, the spectral theorem for real symmetric matrices makes it diagonalizable, so algebraic and geometric multiplicities agree. Consequently the dimensions of its eigenspaces are also independent of the coordinate frame.

For the stated tensor, choose a unit eigenvector $n$ belonging to the simple eigenvalue $\mu$. Its perpendicular plane is the eigenspace of $\lambda$, soHence

Let $A$ be the adjacency matrix of a graph. Since $G$ is a regular graph of degree $d$, every row of $A$ sums to $d$. Therefore, for $\mathbf{e}=(1,\dots ,1{)}^T$,so $d$ is a graph eigenvalue.

If $Av=dv$, then the quadratic form of the graph Laplacian $L=dI-A$ givesEvery summand is nonnegative, so $v_i=v_j$ along every edge. The graph is connected, hence all coordinates of $v$ are equal and $v$ is a scalar multiple of $\mathbf{e}$. Thus the $d$-eigenspace is one-dimensional. Since $A$ is a symmetric matrix, the spectral theorem for real symmetric matrices makes it diagonalizable, so the algebraic multiplicity is also one. This proves the constant eigenvector of a regular graph result.

Suppose the strongly regular graph has $n$ vertices, degree $d$, $r$ common neighbours for every adjacent pair and $s$ common neighbours for every nonadjacent pair. By the walk count from powers of an adjacency matrix, $(A^2{)}_{ij}$ counts common neighbours of $i$ and $j$, while $(A^2{)}_{ii}=d$. Hence the adjacency-matrix relation for a strongly regular graph iswhere $J$ is the all-ones matrix.

The spectral theorem for real symmetric matrices gives an orthonormal eigenbasis for $A$. Part (a) says that the constant direction is the one-dimensional $d$-eigenspace; every other eigenvector $v$ belongs to ${\mathbf{e}}^{\perp }$, so $Jv=0$. If $Av=\theta v$, the displayed identity givesThere are at most two possible roots $\theta$ in addition to $d$. Thus $G$ has at most three distinct eigenvalues.

Because every column of $X$ has sample mean zero, every column $u_i$ of $U=XV$ also has sample mean zero. The spectral theorem for real symmetric matrices givesHence for $i\ne j$ the sample covariance is $n^{-1}{u}_i^T{u}_j=0$, while the sample variance of $u_i$ isThus the $u_i$ are pairwise uncorrelated sample principal components, ordered by decreasing sample variance.

By the spectral theorem for real symmetric matrices, write $A=O^{t}DO$ with $O$ orthogonal and $D=\mathrm{diag}({\xi }_1,\dots ,{\xi }_n)$. Part a and the tensor-product property of the Fourier transform giveThusApplying the pullback rule from part c to the orthogonal change of variables, for which $|\det O|=1$, replaces $D$ by $A$ and $D^{-1}$ by $A^{-1}$. Since determinant and signature are invariant under orthogonal conjugation,

Expanding the determinant gives $\det (\lambda I-M)=(\lambda -1)[(\lambda -1{)}^2-25]$. Solving each eigenvalue equation yieldsTheir pairwise inner products are $16-25+9=0$, $12-12=0$ and $12-12=0$. Their squared Euclidean norms are $50,50,25$, respectively, so division by $\sqrt{50},\sqrt{50},5$ gives an orthonormal basis. This also follows from the spectral theorem for real symmetric matrices: symmetry makes eigenvectors for distinct eigenvalues orthogonal.

For either sign, the dot product with $v_1$ isThe remaining pair also satisfiesHence the three eigenvectors are mutually orthogonal. This also follows from the spectral theorem for real symmetric matrices, since $M=M^T$ and its eigenvalues are distinct, but the displayed products verify the actual chosen vectors directly.

The chosen eigenvectors have dot productThey are therefore orthogonal, and their unit lengths make them an orthonormal eigenbasis. This agrees with the spectral theorem for real symmetric matrices, since $A$ is real symmetric and its two eigenvalues are distinct.

Choose two perpendicular unit directions in the $-2$ eigenspace:Their pairwise dot products vanish and their Euclidean norms are one. They form an orthonormal basis of eigenvectors, with eigenvalues $4,-2,-2$, as guaranteed for a real symmetric matrix by the spectral theorem for real symmetric matrices.

The pairwise dot products of the normalized vectors areTheir squared norms are respectively $(1+2+1)/4$, $(1+1)/2$, and $(1+2+1)/4$, all one. Hence they form an orthonormal basis. This also follows from the spectral theorem for real symmetric matrices, because $D$ is symmetric and its three eigenvalues are distinct.

By the spectral theorem for real symmetric matrices, choose the normalized eigenvectors to form an orthonormal basis. With $P_n={\mathbf{e}}_n{\mathbf{e}}_n^{\mathsf{T}}$, orthonormality gives $P_n{P}_m={\delta }_{nm}{P}_n$ and ${\sum }_n{P}_n=I$. For every vector $\mathbf{x}$, expand $\mathbf{x}={\sum }_n({\mathbf{e}}_n^{\mathsf{T}}\mathbf{x}){\mathbf{e}}_n$ and apply $A$:Since this equality holds for every $\mathbf{x}$, the spectral decomposition isEach $P_n$ is the rank-one orthogonal projection onto its eigenvector direction. In a degenerate eigenspace, normalized eigenvectors must be chosen mutually orthogonal; normalization alone does not guarantee this resolution of the identity.

Yes. The matrix is a real symmetric matrix, so the spectral theorem for real symmetric matrices provides an orthonormal basis of real eigenvectors and hence a real diagonal form. Explicitly its characteristic polynomial is ${\lambda }^2-7\lambda -4$, with distinct real eigenvalues

The spectral theorem for real symmetric matrices supplies an orthonormal basis of real eigenvectors. Put these in the columns of $Q$, so $Q^{T}Q=I$ and $Q^{T}AQ=\mathrm{diag}({\lambda }_1,\dots ,{\lambda }_n)$. In the question's coordinate convention choose $O=Q^T$ and $y=Ox$. Since $x=O^{T}y$,Reorder the eigenvalues with $m$ positive, $\ell -m$ negative and $n-\ell$ zero. For nonzero eigenvalues set $z_i=\sqrt{|{\lambda }_i|}{y}_i$, and retain the remaining coordinates as $z_i=y_i$. This is an invertible real transformation $z=DOx$, where $D$ is the diagonal rescaling; the combined matrix $L=DO$ gives $z=Lx$. It giveswith the zero coordinates absent. The general allowed range is $0\le m\le \ell \le n$. The printed restriction $m\ge 1$ is not valid for every real symmetric matrix: a negative-definite or zero form has no positive square. The invariance of these counts is Sylvester's law of inertia.

For the specified form, a particularly simple change isSubtracting the first two squared coordinates verifies the identity directly, and $\det L=1$ proves invertibility. Thus $m=1$, $\ell =2$ and there is one zero direction. The final rescaling need not remain orthogonal.

Choose $e_1$ real, as permitted by the spectral theorem for real symmetric matrices. Matrix powers commute, soThe proposed partner $e_2=M{e}_1$ is nonzero becauseAlso the real scalar $e_1^{T}M{e}_1$ equals its own transpose $e_1^T{M}^T{e}_1=-e_1^{T}M{e}_1$, so it vanishes. Therefore $e_1$ and $e_2$ are orthogonal eigenvectors with the same eigenvalue. This is the basic pairing in the paired eigenspaces of the square of a real skew-symmetric matrix.