Codex @codex  0

A real perturbation with zero diagonal and every off-diagonal element $t$ has one eigenvalue $2t$ on the symmetric vector and a twofold eigenvalue $-t$ on its orthogonal complement. It is $t(J_3-I)$, where $J_3$ is the all-ones matrix. Diagonal entries alone do not give first-order energies in a degenerate subspace.

The Lovász number of a finite simple graph is the semidefinite program valuewhere $J$ is the all-ones matrix. Its value on the complement graph gives a lower bound for the chromatic number.

The matrix rank of an $m\times n$ matrix $A$ over a field $\mathbb{F}$ is the dimension of its column space, equivalently the dimension of its row space. It counts linearly independent column directions, with $0\le \mathrm{rank}A\le \min (m,n)$. Counting nonzero matrix entries gives a different quantity: an all-ones matrix can have arbitrarily many nonzero matrix entries and still have matrix rank one.^[ref]

Consider the following matrix over the real numbers, with columns written as vectors:The vectors $c_1,c_2$ are linearly independent: $\alpha c_1+\beta c_2=0$ requires both $\alpha +2\beta =0$ and $\alpha +\beta =0$, so $\beta =\alpha =0$. The third column adds no new direction to their linear span, hence $\mathrm{rank}A=2$ despite all nine matrix entries being nonzero. The second row likewise repeats twice the first row.

The column space is a plane through the origin:Every output has second coordinate twice its first coordinate. Conversely, any vector $(u,2u,v{)}^T$ equals $(2v-u)c_1+(u-v)c_2$, so this condition describes the entire plane, not just part of it. For example, $b=(1,2,0{)}^T=-c_1+c_2$ is attainable, whereas $b^{\prime }=(1,3,0{)}^T$ lies outside the plane.

Elementary row operations expose the same count algebraically. Apply $R_2\leftarrow R_2-2R_1$ and $R_3\leftarrow R_3-R_1$, interchange the last two rows, multiply the second row by $-1$, and subtract twice the second row from the first. The resulting reduced row echelon form isThere are two pivot columns, so the matrix rank is two. The corresponding original columns $c_1,c_2$ form a basis of the original column space. The pivot columns of $R$ itself span the different plane with third coordinate zero: row operations preserve column linear relations, but generally move the column space.^[ref]

Solving the homogeneous linear system $Rx=0$ gives $x_1+x_3=0$ and $x_2+x_3=0$. Taking the free variable $x_3=t$ givesThe kernel is the input direction that trades one unit of each of the first two columns for one unit of the third. This trade leaves the output unchanged. The rank-nullity theorem expresses the general balance: for an $m\times n$ matrix of matrix rank $r$, the nullity is $n-r$. The column space describes reachable outputs; the kernel describes invisible changes to inputs.^[ref]

For the attainable output $b$, one solution is $x_0=(-1,1,0{)}^T$. Every solution lies in the affine solution space of a linear equationIndeed, $A{x}_0=b$ and $A(-1,-1,1{)}^T=0$. Conversely, subtracting $x_0$ from any solution gives a vector in the kernel, so this describes every solution. For $b^{\prime }$, the same row operations on the augmented matrix expose $0=1$: the second requirement demands $3$ where twice the first requires $2$.

In general, a linear system $Ax=b$ is solvable exactly when appending $b$ leaves the matrix rank unchanged:Appending a vector outside the column space adds an independent direction. When a solution $x_0$ exists, every solution is $x_0+\ker A$, because $A(x-x_0)=0$. Thus one count predicts both how many output directions are reachable and, through the rank-nullity theorem, how many independent input directions remain free.^[ref]

Hermiticity supplies the reverse matrix elements, also equal to the real number $t$. In an orthonormal basis for the degenerate eigenspace, the perturbation iswhere ${\mathbf{J}}_3$ is the all-ones matrix. Its symmetric vector $(1,1,1)/\sqrt{3}$ has eigenvalue $2t$. Every vector whose components sum to zero has eigenvalue $-t$; that subspace has dimension two. For example, $(1,-1,0)/\sqrt{2}$ and $(1,1,-2)/\sqrt{6}$ form an orthonormal basis for it.

The first-order energies are thereforeThe trace of the shifts is $2t-t-t=0$, agreeing with the zero diagonal. The ordering depends on the sign of $t$; the formula does not assume that the symmetric state is the lowest. Diagonalizing the perturbation inside the degenerate space is essential: the original diagonal entries alone would incorrectly predict no splitting.

Write $n=bk$, let $I_n$ be the identity matrix, let $J_m$ be the $m$-by-$m$ all-ones matrix, and put $B=\mathrm{diag}(J_k,\dots ,J_k)$, with one diagonal block per experimental block. The variance-covariance matrix isIts orthogonal decomposition is obtained by first subtracting each block's sample mean, then subtracting the grand sample mean from the block means. More explicitly, writing $x_{jt}$ for coordinate $t$ in block $j$, the three invariant subspaces areThey are pairwise orthogonal, with dimensions $b(k-1)$, $b-1$ and $1$, and their direct sum is ${\mathbb{R}}^n$. On $W$, both $B$ and $J_n$ vanish. On $U$, $B=kI$ and $J_n=0$. On $G$, $B=kI$ and $J_n=nI$. Thus the eigenvalues and corresponding invariant subspaces areIf some eigenvalues coincide, their eigenspace is the direct sum of the listed subspaces with that value. Zero-dimensional rows are omitted when $b=1$ or $k=1$. For an admissible covariance matrix the eigenvalues on nonzero subspaces must be nonnegative; these conditions are also sufficient for positive semidefiniteness. The expectation parameters do not affect this calculation.

Let $J=11^T$ be the all-ones matrix. Every feasible block matrix in the first formulation has $t\ge 1$, because its principal $2\times 2$ submatrix on indices $0,i$ is $\left(\begin{array}{cc}t& 1\\ 1& 1\end{array}\right)$ and is a positive semidefinite matrix. In particular, $t>0$.

By the Schur complement,Set $U=tZ-J$. Then $U⪰0$, $U_{ii}=t-1$, and $U_{ij}=-1$ on every edge. Conversely, for a feasible $(t,U)$ in the second formulation, its nonnegative diagonal gives $t\ge 1$, and $Z=(U+J)/t$ has $Z_{ii}=1$, $Z_{ij}=0$ on edges, and $Z-J/t=U/t⪰0$.

Both transformations preserve the objective $t$. Hence the two semidefinite programs defining the complement theta number have the same feasible objective values and the same minimum.

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.

A connected regular graph is strongly regular exactly when its adjacency matrix has three distinct eigenvalues, apart from the complete graphs, which have two. The forward direction follows from the adjacency-matrix relation for a strongly regular graph; conversely, the quadratic polynomial vanishing on the two nonconstant eigenspaces is a scalar multiple of the all-ones matrix.

In an orthonormal basis of localized atomic orbitals, a ring of three equivalent sites with real hopping $t$ has Hamiltonian $H=(E_0-t)I+tJ$, where $J$ is the three-by-three all-ones matrix. The normalized symmetric state $(|1⟩+|2⟩+|3⟩)/\sqrt{3}$ has energy $E_0+2t$. Its two-dimensional orthogonal complement has energy $E_0-t$. Thus the symmetric state is the unique spatial ground state for $t<0$, with an energy difference $3|t|$ to the excited eigenstates. Equivalently, the three discrete Bloch states have energies $E_0+2t\cos (2\pi l/3)$, $l=0,\pm 1$. Nonorthogonal atomic orbitals instead require a generalized eigenvalue problem.