6.1 Graph Laplacians and spectral coordinates

A table of observations does not always arrive with a meaningful coordinate for every feature. We may instead know which pairs interact and how strong those interactions are. A graph records that information. To build coordinates from it, we need to specify what a coordinate should accomplish: adjacent vertices should have small coordinate differences, while the complete configuration must not collapse to a point.

This original supplementary note derives that construction for finite, undirected, nonnegatively weighted graphs. Its mathematical preparation is finite sums, real inner products, orthogonal projection and elementary differentiation. We also use finite-dimensional compactness: closed bounded subsets of real Euclidean space are compact, and a continuous real function on a nonempty compact set attains its maximum and minimum. The PCA note already develops SVD and projection-based optimization. We reuse its projection-weight method, and prove the finite real spectral theorem needed here. The MDS note explains a different problem: reconstructing a supplied distance table. Here a path is a finite sequence of distinct vertices with positive-weight edges between consecutive vertices; the length-zero path joins a vertex to itself. Two vertices are connected if a path joins them, and the resulting equivalence classes are the connected components. For transitivity, concatenate two paths to obtain a walk, then delete portions between repeated occurrences of a vertex. Each deletion shortens the walk while preserving endpoints, so after finitely many deletions it is a path.

We will keep three distinctions visible. A symmetric affinity matrix need not be a positive semidefinite kernel. A stationary random-walk law need not be a limiting law. A continuous spectral relaxation need not solve its discrete cut problem exactly.

1. Weighted edges and an energy for vertex functions

Let the vertex set be $V=\{1,\ldots,n\}$, initially with $n\ge1$. Its weight matrix $W=(w_{ij})\in\mathbb R^{n\times n}$ satisfies

$$w_{ij}=w_{ji}\ge0,\qquad w_{ii}=0.$$

Weights may be arbitrary nonnegative real numbers; they need not be probabilities, integers or bounded by one. The support graph has the undirected edge $\{i,j\}$ exactly when $w_{ij}>0$. All statements about components refer to this graph. A pair assigned weight zero does not provide a connection, even if someone includes it in a drawing.

The weighted degree, degree matrix and unnormalized Laplacian are

$$d_i=\sum_{j=1}^n w_{ij},\qquad D=\operatorname{diag}(d_1,\ldots,d_n), \qquad L=D-W.$$

Nonnegativity implies that $d_i=0$ exactly when every weight in row $i$ is zero. Such a vertex is isolated. A vertex function is a real column $f=(f_1,\ldots,f_n)^T$. Its value can represent a proposed coordinate, a temperature or any scalar signal. Matrix multiplication gives

$$(Lf)_i=\sum_jw_{ij}(f_i-f_j).$$

Thus $L\mathbf1=0$, where $\mathbf1$ is the all-one column. Adding a constant to a signal does not alter its edge differences.

Energy identity. For every $f\in\mathbb R^n$,

$$f^TLf =\frac12\sum_{i,j}w_{ij}(f_i-f_j)^2 =\sum_{i<j}w_{ij}(f_i-f_j)^2.$$

Proof. Expand the double sum. Its two square terms give $\frac12\sum\limits_i d_i f_i^2+\frac12\sum\limits_j d_j f_j^2=\sum\limits_i d_i f_i^2$; symmetry is needed to identify the second degree sum. The cross term is $-\sum\limits_{i,j}w_{ij}f_if_j$. Their difference is $f^T(D-W)f$. Each unordered pair appears twice in the double sum, and the diagonal terms vanish, proving the last equality. All sums are finite. ∎

Consequently $L$ is symmetric positive semidefinite. Its energy penalizes differences across strong edges more heavily. No covariance interpretation or assumption that $W$ itself is positive semidefinite was used. For example,

$$W=\begin{pmatrix}0&a\\a&0\end{pmatrix},\qquad a>0,$$

has eigenvalues $a,-a$, while its Laplacian has eigenvalues $0,2a$. This graph affinity is not a positive semidefinite Gram matrix. Conversely the Gram matrix of the two real vectors $1,-1$ is $\begin{pmatrix}1&-1\\-1&1\end{pmatrix}$, which is positive semidefinite because its quadratic form is $(x_1-x_2)^2$, but has negative off-diagonal entries. Thus it does not satisfy our graph hypothesis.

Kernel and components. A function belongs to $\ker L$ exactly when it is constant on each support component. Hence, if there are $c$ components,

$$\dim\ker L=c,\qquad \operatorname{rank}L=n-c.$$

Proof. If $Lf=0$, then $f^TLf=0$. Every summand in the energy is nonnegative, so every positive-weight edge has equal endpoint values. Equality propagates along a path, making $f$ constant on a component. Conversely, a componentwise constant function makes every term in $(Lf)_i=\sum\limits_jw_{ij}(f_i-f_j)$ zero: a positive edge stays in one component and a zero weight contributes nothing. The component indicator columns form an independent spanning set for these functions, because their supports are disjoint and every component is nonempty. An isolated vertex contributes its own indicator just as any other component does. Rank-nullity gives the rank formula. ∎

The sign hypothesis matters. Giving the sole edge of a two-vertex graph weight $-1$ would yield energy $-(f_1-f_2)^2$, which is negative for a nonconstant function. Directed or signed matrices require different statements and are outside this note.

2. The finite real spectral bridge and the second eigenvalue

The PCA construction uses an orthonormal eigenbasis of a real symmetric matrix. Here is the finite-dimensional proof, so the graph argument has no hidden spectral dependency.

Real symmetric spectral theorem. Every real symmetric matrix $S$ admits an orthonormal basis of real eigenvectors.

Proof. In dimension zero the empty basis suffices. In dimension $m\ge1$, the continuous function $x\mapsto x^TSx$ attains a maximum on the compact unit sphere. Choose a maximizing unit column $v$. For every real column $h$ with $h^Tv=0$, the curve

$$x(t)=\frac{v+th}{\sqrt{1+t^2\|h\|^2}}$$

has unit norm for every real $t$. Differentiation at zero is valid, and the derivative of its quadratic form is

$$\left.\frac{d}{dt}\bigl(x(t)^TSx(t)\bigr)\right|_{t=0} =2h^TSv=0.$$

Therefore $Sv$ is orthogonal to every column in $v^\perp$. The orthogonal decomposition into $\operatorname{span}\{v\}$ and $v^\perp$ shows that $Sv=\lambda v$ for a real scalar $\lambda$. If $h\in v^\perp$, symmetry gives $v^TSh=(Sv)^Th=\lambda v^Th=0$. Hence $v^\perp$ is invariant, and the restriction of $S$ to it is again real symmetric. Apply the induction hypothesis in dimension $m-1$ and adjoin $v$. The resulting eigenvectors form the required orthonormal basis. ∎

For a positive semidefinite matrix, every eigenvalue is nonnegative, since $Sq=\lambda q$ with $\|q\|=1$ implies $\lambda=q^TSq\ge0$.

Apply this to $L$. Its known zero-eigenvalue direction lets us choose the first eigenvector before making any other choice:

$$q_1=\frac{\mathbf1}{\sqrt n}.$$

The space $\mathbf1^\perp$ is invariant because $\mathbf1^TLf=(L\mathbf1)^Tf=0$. Apply the theorem to that restriction, order its eigenvalues increasingly, and obtain

$$Lq_j=\lambda_jq_j,\qquad 0=\lambda_1\le\lambda_2\le\cdots\le\lambda_n.$$

This ordering permits several zero eigenvalues. Choosing $q_1$ constant does not imply that the graph is connected.

For $n\ge2$, the second eigenvalue has the precise optimization formula

$$\lambda_2 =\min_{\substack{f^T\mathbf1=0\\\|f\|=1}} f^TLf.$$

Proof. Write a centered unit function as $f=\sum\limits_{j=2}^n a_jq_j$. Then $\sum\limits_{j=2}^n a_j^2=1$ and $f^TLf=\sum\limits_{j=2}^n\lambda_ja_j^2\ge\lambda_2$. Choosing $f=q_2$ attains the bound. Equality occurs exactly when all coefficients corresponding to eigenvalues greater than $\lambda_2$ vanish. Thus the minimizing functions are all unit vectors in the $\lambda_2$ eigenspace inside $\mathbf1^\perp$, not a uniquely oriented column. ∎

In particular, $\lambda_2>0$ exactly when the support graph is connected. If connected, the kernel is only $\operatorname{span}\{\mathbf1\}$, so every eigenvalue in its complement is positive. If disconnected, there is a nonzero centered componentwise constant function, so the minimum is zero. This is an exact connection between an algebraic spectrum and a combinatorial property.

For one vertex, $L=0$ and there is no second eigenvalue or centered unit function. The zero matrix on two or more vertices has many components and $\lambda_2=0$. An empty vertex set may also be allowed as a separate convention: its matrices are empty and its kernel has dimension zero, but it has no second eigenvalue. No optimization over a nonexistent unit vector is intended in these cases.

3. Normalization without dividing by isolated degrees

Weighted degrees may differ greatly. Normalization measures an edge difference relative to the degrees at its endpoints, but it must first address degree zero.

Let

$$S=\{i:d_i>0\},\qquad Z=V\setminus S.$$

There are no edges incident to $Z$. Restrict $W,D,L$ to $S$, writing $W_S,D_S,L_S$ for the corresponding matrices. If $S$ is nonempty, $D_S$ is positive definite and we define

$$N_S=D_S^{-1/2}L_SD_S^{-1/2} =I_S-D_S^{-1/2}W_SD_S^{-1/2}.$$

Our full-space normalized Laplacian $N$ is $N_S$ on $S$ and zero on every isolated coordinate. Equivalently, let $R$ be diagonal with entry $d_i^{-1/2}$ on $S$ and zero on $Z$; then

$$N=RLR.$$

When isolates exist, this is not $I_n-RWR$: that different formula assigns the value one to an isolated diagonal entry. Either convention must be stated before interpreting zero modes. We use the zero extension throughout. If $S$ is empty, $N=0$; no inverse of a degree matrix is formed.

For an active column $x$, put $g=D_S^{-1/2}x$. The energy identity proves

$$x^TN_Sx=\sum_{\substack{i<j\\i,j\in S}}w_{ij} \left(\frac{x_i}{\sqrt{d_i}}-\frac{x_j}{\sqrt{d_j}}\right)^2.$$

It follows that $N_S$ is positive semidefinite. Its kernel consists of columns whose entries are a common constant times $\sqrt{d_i}$ on each active support component. The converse follows either by the coordinate equation or by $N_Sx=D_S^{-1/2}L_Sg=0$ when $g$ is componentwise constant. Thus each active component contributes the column $\sqrt d$ restricted to that component. Under zero extension, each isolated column $e_i$ supplies one more kernel vector. The full normalized and unnormalized kernels have equal dimension, although their vectors on active components are scaled differently.

The spectrum of $N$ lies in $[0,2]$. Indeed, on active coordinates the inequality $(a-b)^2\le2a^2+2b^2$ gives

$$0\le x^TN_Sx \le 2\sum_i d_i\left(\frac{x_i}{\sqrt{d_i}}\right)^2 =2\|x\|^2.$$

Each edge contributes to the degree sums of its two endpoints, so there is no extra factor of two. Apply this bound to a unit eigenvector; every active eigenvalue lies between zero and two. The isolated zero eigenvalues satisfy the same bound. A single positive edge on two vertices has normalized matrix $\begin{pmatrix}1&-1\\-1&1\end{pmatrix}$, whose eigenvalues $0,2$ attain both endpoints.

Normalization is a change of metric, not permission to invert zero degrees. The weighted form $f^TDg$ is an inner product on active coordinates, but on the full space it vanishes on an isolated column and is only semidefinite.

4. A reversible walk need not converge

On the active set only, define

$$P=D_S^{-1}W_S,\qquad P_{ij}=\frac{w_{ij}}{d_i}.$$

Its entries are nonnegative and every row sums to one. It is therefore a row-stochastic transition matrix: $P_{ij}$ is the probability of moving from $i$ to $j$ in one step. For a vertex function $f$, $(Pf)_i$ is its expected value after one step started at $i$. In contrast, a probability column $r_t$ evolves by

$$r_{t+1}=P^Tr_t.$$

This transpose matters. Multiplying a column distribution by $P$ uses a different convention and need not preserve its total mass.

In the rest of this section all matrices and columns are restricted to $S$. Symmetry of $W$ gives the exact identities

$$DP=W=P^TD.$$

Consequently $P$ is self-adjoint for $\langle f,g\rangle_D=f^TDg$: $f^TDPg=f^TWg=(Pf)^TDg$. It need not be symmetric in the ordinary Euclidean inner product. The direct similarity calculation is

$$D^{1/2}PD^{-1/2}=D^{-1/2}WD^{-1/2}=I-N_S.$$

Thus, if $N_Su=\mu u$, then $f=D^{-1/2}u$ satisfies $Pf=(1-\mu)f$. An orthonormal eigenbasis for $N_S$ becomes a $D$-orthonormal eigenbasis for $P$. In particular its eigenvalues are real and lie in $[-1,1]$, without invoking a separate stochastic spectral theorem.

For nonempty $S$ the total degree $\operatorname{vol}(S)=\sum\limits_{i\in S}d_i$ is positive. Define the probability column

$$\pi_i=\frac{d_i}{\operatorname{vol}(S)}.$$

For every active $j$, finite summation gives

$$(\pi^TP)_j =\sum_i\frac{d_i}{\operatorname{vol}(S)}\frac{w_{ij}}{d_i} =\frac{d_j}{\operatorname{vol}(S)}=\pi_j.$$

Therefore $\pi$ is stationary. Moreover $\pi_iP_{ij}=w_{ij}/\operatorname{vol}(S)=\pi_jP_{ji}$, the detailed balance identity. On a disconnected active graph, normalizing the degrees separately on any one component gives a stationary law supported there; convex mixtures of these laws are also stationary. We do not assert uniqueness without further work.

Stationarity is not convergence. With two vertices and one positive edge,

$$P=\begin{pmatrix}0&1\\1&0\end{pmatrix},\qquad \pi=\begin{pmatrix}1/2\\1/2\end{pmatrix}.$$

The law $\pi$ stays fixed, but a walk started at vertex one is at vertex one at every even time and vertex two at every odd time. Its laws never converge. Algebraically the eigenvalue $-1$ retains an alternating component; the corresponding normalized eigenvalue is $2$. The existence of a stationary vector therefore cannot justify a mixing claim. We make no general convergence-rate assertion here.

If all degrees are zero, the active set is empty and there is no active walk or degree-normalized probability law. One could separately choose absorbing transitions at isolated vertices, but that is extra model data, not a value produced by dividing zero by zero.

5. What spectral coordinates actually minimize

A constant coordinate has zero energy, and setting every coordinate to zero would make every vertex coincide. To prevent these collapses, prescribe centered orthonormal coordinate columns.

For an integer $0\le k\le n-1$, choose $U\in\mathbb R^{n\times k}$ such that

$$U^TU=I_k,\qquad U^T\mathbf1=0.$$

The coordinate of vertex $i$ is row $U_{i:}\in\mathbb R^k$. Applying the scalar energy identity to each column and summing proves

$$\operatorname{tr}(U^TLU) =\sum_{i<j}w_{ij}\|U_{i:}-U_{j:}\|^2.$$

This objective is total squared variation across weighted edges. It is not the error in a supplied pairwise-distance table.

Minimum-trace principle. With the eigenvalues ordered as in section2,

$$\min_{\substack{U^TU=I_k\\U^T\mathbf1=0}} \operatorname{tr}(U^TLU) =\sum_{j=2}^{k+1}\lambda_j.$$

For $k=0$ the matrix has no columns and both sides are zero. For $k\ge1$ an attaining choice is $U=[q_2\ \cdots\ q_{k+1}]$.

Proof. Work inside $\mathbf1^\perp$, whose orthonormal eigenbasis is $q_2,\ldots,q_n$. Put

$$a_j=\|U^Tq_j\|^2,\qquad 2\le j\le n.$$

Because $UU^T$ is orthogonal projection onto the column space of $U$, we have $0\le a_j\le1$. Expanding each unit column of $U$ in this basis and summing its squared coefficients gives $\sum\limits_{j=2}^na_j=k$. Also spectral expansion gives $\operatorname{tr}(U^TLU)=\sum\limits_{j=2}^n\lambda_ja_j$.

Let $c=\lambda_{k+1}$. The mass identity just proved gives the exact difference

$$\begin{aligned} \sum_{j=2}^n\lambda_ja_j-\sum_{j=2}^{k+1}\lambda_j &=\sum_{j=2}^{k+1}(c-\lambda_j)(1-a_j)\\ &\quad+\sum_{j=k+2}^n(\lambda_j-c)a_j\ge0. \end{aligned}$$

Every displayed coefficient is nonnegative. Taking the first $k$ eigenvectors inside the centered space attains equality, proving the minimum. This is the projection-weight argument used for PCA, with the eigenvalue order reversed because we minimize variation instead of maximizing variance. ∎

For $k\ge1$, the difference identity also gives the precise equality conditions. Inside $\mathbf1^\perp$, the retained column space must contain every eigenspace with eigenvalue below $c$ and be orthogonal to every eigenspace with eigenvalue above $c$. In the eigenspace for $c$, it may choose any remaining dimensions needed to reach $k$. To justify these statements, $a_j=1$ means that projection preserves the whole norm of $q_j$, so $q_j$ belongs to the column space; $a_j=0$ means it is orthogonal to that space. The zero coefficients at the cutoff leave exactly the stated freedom. The already excluded constant direction is never required to be included, even when $c>0$.

If $k<n-1$ and $\lambda_{k+1}<\lambda_{k+2}$, the retained subspace is fixed. For $k=n-1$, the retained subspace is the entire centered space and is also fixed. Neither case fixes an oriented basis. If two feasible matrices $U,V$ span the same subspace, define $Q=U^TV$. Since projection onto that subspace is both $UU^T$ and $VV^T$,

$$UQ=UU^TV=V,\qquad Q^TQ=V^TUU^TV=V^TV=I_k.$$

The square matrix $Q$ is orthogonal. Therefore row distances are unchanged by $V=UQ$, and $VV^T=UU^T$. However, a repeated eigenvalue straddling the truncation boundary can permit genuinely different retained subspaces. Their row distances need not agree; Question2 computes this explicitly.

For a disconnected graph, some centered component-indicator combinations have zero energy. The theorem still holds and may place components separately without charging for an absent connecting edge. It does not identify a unique clustering. For one vertex only $k=0$ is allowed. The empty graph also admits an empty zero-column configuration as a separate endpoint, with no nonzero-dimensional embedding claim.

Compare the objectives. PCA starts with feature observations and retains directions of greatest variance. Classical MDS starts with distances and seeks a centered Gram realization. Here the supplied edge weights define smoothness, and the coordinates retain directions of least nonconstant graph energy. These constructions can use eigenvectors without solving the same problem. In particular no PCA explained-variance percentage, MDS distance-preservation theorem or inverse-square-root eigenvalue scaling is asserted for the orthonormal graph coordinates above.

6. Normalized cut is an exact indicator quotient and a relaxation

Now assume the support graph is connected and $n\ge2$. Every degree is then positive. For a nonempty proper subset $A\subset V$, put $B=V\setminus A$ and define

$$\operatorname{vol}(A)=\sum_{i\in A}d_i,\qquad \operatorname{cut}(A,B)=\sum_{\substack{i\in A\\j\in B}}w_{ij}.$$

Volume counts an internal edge twice and a crossing edge once:

$$\operatorname{vol}(A) =2\sum_{\substack{i<j\\i,j\in A}}w_{ij}+\operatorname{cut}(A,B).$$

This follows by separating each degree sum into neighbors inside and outside $A$. It is not the number of edges merely incident to $A$. Write $a=\operatorname{vol}(A)>0$, $b=\operatorname{vol}(B)>0$. The normalized-cut value is

$$\operatorname{Ncut}(A,B) =\operatorname{cut}(A,B)\left(\frac1a+\frac1b\right).$$

There is an exact quadratic-form representation. Define the two-level function

$$f_i=\begin{cases}1/a,&i\in A,\\-1/b,&i\in B.\end{cases}$$

Its degree-weighted mean and norm are

$$f^TD\mathbf1=1-1=0,\qquad f^TDf=\frac1a+\frac1b.$$

Only crossing edges contribute to its energy, so

$$f^TLf=\operatorname{cut}(A,B)\left(\frac1a+\frac1b\right)^2.$$

Dividing the energy by the positive squared norm proves

$$\frac{f^TLf}{f^TDf}=\operatorname{Ncut}(A,B).$$

To relax the restriction that $f$ take exactly these two values, let $x=D^{1/2}f$. Then

$$x^TNx=f^TLf,\qquad x^Tx=f^TDf,\qquad x^T\sqrt d=f^TD\mathbf1=0,$$

where $\sqrt d=(\sqrt{d_1},\ldots,\sqrt{d_n})^T$. In a connected graph $N$ has exactly the one-dimensional kernel spanned by $\sqrt d$. Choose its normalized kernel vector first and diagonalize its orthogonal complement, exactly as in section2. If its ordered eigenvalues are $0=\mu_1<\mu_2\le\cdots\le\mu_n$, expansion in that orthonormal eigenbasis proves

$$\mu_2=\min_{\substack{x\ne0\\x^T\sqrt d=0}} \frac{x^TNx}{x^Tx} \le\min_{\varnothing\ne A\subsetneq V}\operatorname{Ncut}(A,V\setminus A).$$

The minimum over cuts exists because there are finitely many nonempty proper subsets. The inequality holds because each indicator-derived vector is an admissible continuous competitor. The relaxed feasible set has many other vectors, so the inequality need not be equality. Question4 gives a strict gap. A sign or sorted-threshold procedure is an additional rounding choice; no exact-cut or approximation guarantee for such a procedure has been proved here.

On a graph with isolates, a side can have zero volume, making this quotient undefined. The active normalized matrix still exists by section3, but that fact does not assign a value to division by zero. Our normalized-cut theorem deliberately uses connected positive-degree support.

7. Common interpretation errors

A zero eigenvalue records a componentwise constant signal, not a unique informative coordinate. With disconnected support there are several zero modes. An isolated vertex cannot be normalized by its degree, and silently replacing its zero block by a one changes the normalized operator.

Euclidean symmetry of $P$ is stronger than the weighted identity $DP=P^TD$. Likewise, detailed balance and a stationary vector do not imply convergence from every start. The two-vertex example keeps all of these distinctions finite and exact.

Finally, coordinate signs are arbitrary, and equal eigenvalues require attention to the retained subspace. Even when the subspace is fixed, its basis may rotate. When a tie crosses a truncation boundary, the subspace itself may vary. Comparing individual plotted axes without checking these choices can misidentify an algebraic ambiguity as a change in the data.

8. Questions and complete solutions

Question 1

On four vertices let $w_{12}=1$, $w_{23}=2$, and all other off-diagonal weights be zero. Compute the degrees, Laplacian, components, kernel and complete unnormalized spectrum. Compute the isolate-safe normalized spectrum and give an orthonormal eigenbasis. Then find the active transition matrix and its degree-stationary law. Explain why neither a uniform active law nor the full matrix $I_4-RWR$ gives the asserted conventions.

Solution. Symmetry supplies the reverse weights. The matrices are

$$W=\begin{pmatrix}0&1&0&0\\1&0&2&0\\0&2&0&0\\0&0&0&0\end{pmatrix},\qquad D=\operatorname{diag}(1,3,2,0),\qquad L=\begin{pmatrix}1&-1&0&0\\-1&3&-2&0\\0&-2&2&0\\0&0&0&0\end{pmatrix}.$$

There are two components, $\{1,2,3\}$ and $\{4\}$. Hence the kernel is spanned by $(1,1,1,0)^T$ and $e_4$. To compute the other eigenvalues rather than infer them from a drawing, let $L_3$ denote the upper three-by-three block. Expansion of its tridiagonal determinant gives

$$\begin{aligned} \det(tI-L_3) &=(t-1)\bigl((t-3)(t-2)-4\bigr)-(t-2)\\ &=t(t^2-6t+6). \end{aligned}$$

The isolated zero block supplies one more factor $t$, so the full spectrum, including multiplicity, is $0,0,3-\sqrt3,3+\sqrt3$.

On the active set the normalized matrix is

$$N_3=\begin{pmatrix} 1&-1/\sqrt3&0\\ -1/\sqrt3&1&-\sqrt{2/3}\\ 0&-\sqrt{2/3}&1 \end{pmatrix}.$$

Direct multiplication gives an orthonormal eigenbasis

$$u_0=\frac{(1,\sqrt3,\sqrt2)^T}{\sqrt6},\qquad u_1=\frac{(\sqrt2,0,-1)^T}{\sqrt3},\qquad u_2=\frac{(1,-\sqrt3,\sqrt2)^T}{\sqrt6},$$

with eigenvalues $0,1,2$ respectively. The numerators have squared norms $6,3,6$ and pairwise zero dot products, which verifies their normalization and independence. Extend these columns by a zero fourth entry and append $e_4$. This is a full orthonormal eigenbasis for our $N$, with spectrum $0,0,1,2$.

Because $R_{44}=0$, the matrix $I_4-RWR$ instead sends $e_4$ to $e_4$; it would replace the isolated eigenvalue zero by one. Its active block is the same, but its isolated convention is different.

The transition matrix on vertices $1,2,3$ and its stationary probability column are

$$P=\begin{pmatrix}0&1&0\\1/3&0&2/3\\0&1&0\end{pmatrix},\qquad \pi=\frac16\begin{pmatrix}1\\3\\2\end{pmatrix}.$$

The row $\pi^TP$ is $(1,3,2)/6$, either by direct multiplication or by the degree identity. In contrast, the uniform row $(1/3,1/3,1/3)$ becomes $(1/9,2/3,2/9)$ and is not stationary. Notice also $P_{12}=1$ but $P_{21}=1/3$: $P$ is not Euclidean symmetric. Its correct symmetry is $D_3P=P^TD_3$. The isolated fourth transition row is not defined by this active construction, so neither a four-vertex degree inverse nor a probability mass assigned by such an inverse is used.

Question 2

For the unweighted complete graph on three vertices, solve the one- and two-coordinate minimum-trace problems. Compare the one-coordinate choices

$$u=\frac{(1,-1,0)^T}{\sqrt2},\qquad v=\frac{(1,1,-2)^T}{\sqrt6}.$$

Compute their three pairwise squared coordinate distances, and determine whether all minimizing coordinates have the same distances. When the entire two-dimensional centered space is retained, prove that any two orthonormal coordinate matrices differ by an orthogonal change of coordinates and compute their pairwise squared row distances.

Solution. Every vertex has degree two, and the adjacency matrix is $J-I$, where $J=\mathbf1\mathbf1^T$. Therefore $L=3I-J$. The constant column has eigenvalue zero; every centered column $f$ satisfies $Jf=0$ and $Lf=3f$. The spectrum is $0,3,3$. Both displayed columns are centered unit columns, so every one-coordinate objective equals three and these are minimizers.

For $u$, the squared distances in pair order $12,13,23$ are

$$(\sqrt2)^2=2,\qquad (1/\sqrt2)^2=1/2,\qquad(-1/\sqrt2)^2=1/2.$$

For $v$ they are

$$0,\qquad (3/\sqrt6)^2=3/2,\qquad (3/\sqrt6)^2=3/2.$$

Thus the distance triples differ. A one-dimensional orthogonal change can only multiply every coordinate by $1$ or $-1$, preserving all distances, so these two minimizers are not related in that way. The repeated eigenvalue permits different one-dimensional subspaces inside the two-dimensional centered eigenspace.

For $k=2$, every feasible column space is the entire $\mathbf1^\perp$, and the minimum is $3+3=6$. Its orthogonal projector is $H=I-J/3$. If $U,V$ are any two feasible matrices, let $Q=U^TV$. Then $UQ=UU^TV=HV=V$, and $Q^TQ=V^THV=I_2$. Hence $Q$ is an actual orthogonal matrix relating the two coordinates. Their Gram matrix is $UU^T=VV^T=H$. For distinct $i,j$ the squared row distance is

$$H_{ii}+H_{jj}-2H_{ij}=\frac23+\frac23-2\left(-\frac13\right)=2.$$

Here retaining the whole repeated eigenspace fixes the subspace and all distances. Truncating through it did not. The statements concern the explicit graph-energy constraints; they do not impose a separately supplied MDS distance table.

Question 3

Two vertices are joined by one edge of weight $a>0$. Derive the active transition matrix, stationary law and normalized eigenvalues. Starting from a point mass, compute the law at every time and decide whether it converges. Explain separately why the non-symmetry of the weighted path transition matrix in Question1 does not contradict reversibility. What, if anything, does the degree formula define for an all-zero graph?

Solution. Here $D=aI_2$ and $W=a\begin{pmatrix}0&1\\1&0\end{pmatrix}$, so

$$P=\begin{pmatrix}0&1\\1&0\end{pmatrix},\qquad \pi=\begin{pmatrix}1/2\\1/2\end{pmatrix},\qquad N=\begin{pmatrix}1&-1\\-1&1\end{pmatrix}.$$

The columns $(1,1)^T/\sqrt2$ and $(1,-1)^T/\sqrt2$ have normalized eigenvalues $0,2$. The corresponding transition eigenvalues are $1,-1$. Since $P^2=I_2$, induction gives $P^{2m}=I_2$ and $P^{2m+1}=P$ for every integer $m\ge0$. Starting from the probability column $r_0=e_1$, and noting $P^T=P$ in this particular example, we obtain $r_{2m}=e_1$ and $r_{2m+1}=e_2$. The first coordinate has subsequences equal to one and zero, so no limit exists. The stationary column still satisfies $P^T\pi=\pi$; averaging these two starting states with equal weights removes the alternating component.

For the path in Question1, $D_3=\operatorname{diag}(1,3,2)$ and direct multiplication gives

$$D_3P=\begin{pmatrix}0&1&0\\1&0&2\\0&2&0\end{pmatrix}=P^TD_3.$$

This is self-adjointness in a different positive inner product, not ordinary matrix symmetry. Detailed balance uses $\pi_iP_{ij}=\pi_jP_{ji}$, so unequal one-step probabilities are balanced by unequal stationary masses. A probability column evolves by $P^T$; the action $Pf$ instead takes conditional expectations of a function. These happen to coincide as matrices for the two-vertex example, but not for the weighted path.

If every weight is zero, all degrees and the total volume are zero and the active set is empty. The zero-extended normalized Laplacian is the zero matrix, but neither $D^{-1}W$ nor $d/\sum\limits_i d_i$ is a defined full-space formula. The zero column would not be a probability law because its entries sum to zero. Assigning absorbing isolated states would be an additional transition convention, not a conclusion of our construction.

Question 4

For the unweighted path $1-2-3-4$, compute the normalized spectrum and verify that

$$f=(1,1/2,-1/2,-1)^T$$

is a generalized eigenfunction with $Lf=(1/2)Df$. Compute all normalized-cut values up to interchange of the two sides. Compare the exact optimum with the spectral relaxation, and evaluate the two-level indicator quotient for the central cut.

Solution. The degree matrix and Laplacian are

$$D=\operatorname{diag}(1,2,2,1),\qquad L=\begin{pmatrix}1&-1&0&0\\-1&2&-1&0\\0&-1&2&-1\\0&0&-1&1\end{pmatrix}.$$

The four columns

$$f_0=(1,1,1,1)^T,\quad f_{1/2}=(1,1/2,-1/2,-1)^T,\quad f_{3/2}=(1,-1/2,-1/2,1)^T,\quad f_2=(1,-1,1,-1)^T$$

satisfy $Lf_\mu=\mu Df_\mu$, as entrywise multiplication verifies. For example $Lf_{1/2}=(1/2,1/2,-1/2,-1/2)^T=(1/2)Df_{1/2}$. Their degree-weighted squared norms are $6,3,3,6$ respectively. Multiplication by $D^{1/2}$ and division by those positive norm square roots gives unit eigenvectors for $N$. Their distinct eigenvalues make them orthogonal: for a symmetric $N$, the two expressions for $x^TNy$ imply $(\mu_y-\mu_x)x^Ty=0$. Thus they give four independent eigenvectors, exhausting dimension four. The normalized spectrum is exactly $0,1/2,3/2,2$.

The proposed $f$ is $f_{1/2}$, with weighted mean $1+1-1-1=0$ and squared weighted norm three. Its Rayleigh quotient is $1/2$, proving the relaxed minimum is attained.

There are seven unordered nontrivial cuts, because exactly one side contains vertex one. Use that side as $A$; the total volume is six. Each crossing path edge has weight one, so direct enumeration gives

The smallest discrete value is $2/3$, attained by $\{1,2\}\mid\{3,4\}$. For this cut the two-level function is $g=(1/3,1/3,-1/3,-1/3)^T$. Only the central edge contributes to its energy, giving $g^TLg=(2/3)^2=4/9$, while $g^TDg=6/9=2/3$. Their ratio is $2/3$, confirming the indicator formula directly.

We have the strict inequality

$$\mu_2=\frac12<\frac23=\min_A\operatorname{Ncut}(A,V\setminus A).$$

The relaxed minimizer takes four different values, while the cut function takes only two. A sign threshold happens to recover the optimal central cut in this example. That observation does not remove the strict objective gap or prove a general guarantee for threshold rounding.