Pipeline-generated

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

✓ 5 results · all verified · 5 also independently AI-judged

Every result on this page is machine-checked by a proof checker and read in full and owner-audited; the judge is an additional, independent cross-model AI review of the proofs; all 5 also cleared it.

Spectral clustering and graph cuts

1 · Prerequisites

2 · Logical flowchart

3 · Definitions, theorems and proofs

DefinitionDefinition: Literature-sourcedProof: Not applicablejudge pass (gpt-6-luna)Open item page →

Finite weighted graph Laplacian

Definition

Let $n \geq 1$ , $V = {1, \dots, n}$ , and let $W = (w_{i j}) \in R^{n \times n}$ satisfy $w_{i j} = w_{j i} \geq 0$ and $w_{i i} = 0$ . Define $d_{i} = \sum_{j = 1}^{n} w_{i j}$ , $D = diag (d_{1}, \dots, d_{n})$ , and $L = D - W$ . The support graph has vertex set $V$ and edge ${i, j}$ exactly when $w_{i j} > 0$ ; isolated vertices are singleton connected components. Put $V_{+} = {i \in V : d_{i} > 0}$ , let $D_{+}$ and $L_{+}$ be the principal submatrices indexed by $V_{+}$ , and, only when $V_{+} \neq \emptyset$ , define $L_{s y m, +} = D_{+}^{- 1 / 2} L_{+} D_{+}^{- 1 / 2}$ on $R^{V_{+}}$ .

Definition references

Ulrike von Luxburg, A Tutorial on Spectral Clustering, Statistics and Computing 17(4), 2007

Jean Gallier, Notes on Elementary Spectral Graph Theory: Applications to Graph Clustering Using Normalized Cuts, 2013

LemmaStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (gpt-6-luna)Open item page →

Finite-dimensional trace minimization under orthonormal constraints

Statement

Let $A \in R^{n \times n}$ be symmetric, let $λ_{1} \leq \dots \leq λ_{n}$ be its real eigenvalues repeated with multiplicity, and define $tr (B) = \sum_{i} B_{i i}$ for square $B$ . For $1 \leq k \leq n$ , $\min_{Q \in R^{n \times k}, Q^{T} Q = I_{k}} tr (Q^{T} A Q) = \sum_{i = 1}^{k} λ_{i} .$ The minimum is attained by taking the columns of $Q$ to be orthonormal eigenvectors for the $k$ smallest eigenvalues, counted with multiplicity; when an eigenvalue at the cutoff is repeated, the minimizer need not be unique.

Statement references

Ulrike von Luxburg, A Tutorial on Spectral Clustering, Statistics and Computing 17(4), 2007

Jean Gallier, Notes on Elementary Spectral Graph Theory: Applications to Graph Clustering Using Normalized Cuts, 2013

Facts & Assumptions

Given: A real symmetric matrix $A \in R^{n \times n}$ and an integer $1 \leq k \leq n$ .

[F1]

Real spectral theorem: a self-adjoint endomorphism of a finite-dimensional real inner product space has an orthonormal eigenbasis: a self-adjoint endomorphism of a finite-dimensional real inner-product space has an orthonormal eigenbasis.

[F2]

The smallest and largest eigenvalues of a self-adjoint endomorphism are the minimum and maximum Rayleigh quotients: for a self-adjoint endomorphism with eigenvalues ordered decreasingly, the minimum nonzero-vector Rayleigh quotient is the smallest eigenvalue.

Proof

1.1givenF2algebra

If $k = 1$ , every feasible $Q$ is a unit column $q$ , so $tr (Q^{T} A Q) = q^{T} A q = R_{A} (q)$ . By [F2], its minimum is the smallest eigenvalue, which is $λ_{1}$ in the increasing order of the Statement.

1.2givenF1algebrachoose

Suppose $k \geq 2$ . By [F1], choose an orthonormal eigenbasis $u_{1}, \dots, u_{n}$ with eigenvalues $λ_{1} \leq \dots \leq λ_{n}$ , and let $U$ be the matrix with these columns. For any feasible $Q$ , put $C = U^{T} Q$ ; then $C^{T} C = I_{k}$ and $Q^{T} A Q = C^{T} diag (λ_{1}, \dots, λ_{n}) C$ . Writing $c_{i j}$ for the entries of $C$ and $p_{i} = \sum_{j = 1}^{k} c_{i j}^{2}$ , direct expansion of the diagonal sum gives $tr (Q^{T} A Q) = \sum_{i = 1}^{n} λ_{i} p_{i}$ .

2.1givenstep 1.2algebra

The matrix $P = C C^{T}$ is symmetric and idempotent because $C^{T} C = I_{k}$ . Hence it is the orthogonal projection onto the column space of $C$ , and $p_{i} = e_{i}^{T} P e_{i} = ∥ P e_{i} ∥_{2}^{2}$ lies in $[0, 1]$ . Also $\sum_{i} p_{i} = \sum_{i, j} c_{i j}^{2} = \sum_{j} (C^{T} C)_{j j} = k$ .

3.1step 1.1step 1.2step 2.1algebraconstruct∎

Using $\sum_{i} p_{i} = k$ , subtract the bottom- $k$ eigenvalue sum to obtain $\sum_{i} λ_{i} p_{i} - \sum_{i = 1}^{k} λ_{i} = \sum_{i = 1}^{k} (λ_{k} - λ_{i}) (1 - p_{i}) + \sum_{i = k + 1}^{n} (λ_{i} - λ_{k}) p_{i} \geq 0.$ Every term on the right is nonnegative. Taking $Q = (u_{1}, \dots, u_{k})$ gives equality, so the stated minimum is attained. This proves the claim for $k \geq 2$ as well as the $k = 1$ case of step 1.1.

LemmaStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (gpt-6-luna)Open item page →

Projected coordinate vectors give a deterministic orthonormal basis

Statement

Let $m \geq 1$ , let $E$ be a subspace of $R^{m}$ with its standard inner product, and let $P_{E}$ be the orthogonal projection onto $E$ . Let $e_{1}, \dots, e_{m}$ be the standard coordinate vectors. Start a list with an optional unit vector $q_{0} \in E$ . For each $i = 1, \dots, m$ in order, set $v_{i} = P_{E} e_{i}$ , subtract from $v_{i}$ its orthogonal projections onto the vectors already in the list, discard the residual if it is zero, and otherwise append the residual divided by its Euclidean norm. The resulting list is an orthonormal basis of $E$ , beginning with $q_{0}$ when it is supplied.

Statement references

Ulrike von Luxburg, A Tutorial on Spectral Clustering, Statistics and Computing 17(4), 2007

Jean Gallier, Notes on Elementary Spectral Graph Theory: Applications to Graph Clustering Using Normalized Cuts, 2013

Facts & Assumptions

Given: A subspace $E \subseteq R^{m}$ with the standard inner product, its orthogonal projection $P_{E}$ , the standard coordinate vectors $e_{1}, \dots, e_{m}$ , and an optional unit vector $q_{0} \in E$ .

[F1]

The orthogonal projection $P_{W} v$ is the $W$ -component in $V = W \oplus W^{⊥}$ : every vector has a unique decomposition as a component in $E$ plus a component in $E^{⊥}$ , and $P_{E} v$ is the $E$ -component.

Proof

1.1givenF1algebra

Write $x = \sum_{i = 1}^{m} x_{i} e_{i}$ . The unique decompositions of two vectors add, and scalar multiples of a decomposition remain decompositions, so uniqueness makes $P_{E}$ linear. If $x \in E$ , its decomposition is $x + 0$ , hence $P_{E} x = x$ . Therefore $x = P_{E} x = \sum_{i} x_{i} P_{E} e_{i}$ , and the projected coordinate vectors span $E$ .

2.1givenF1step 1.1algebraconstruct∎

Start with $q_{0}$ if supplied, then process $v_{i} = P_{E} e_{i}$ in order. Each residual $r_{i} = v_{i} - \sum_{j} ⟨ v_{i}, b_{j} ⟩ b_{j}$ lies in $E$ and is orthogonal to every previously accepted orthonormal vector $b_{j}$ . If $r_{i} = 0$ , then $v_{i}$ is already in their span; if $r_{i} \neq 0$ , appending $r_{i} / ∥ r_{i} ∥_{2}$ preserves orthonormality and the span of all processed vectors. By induction, after the finite scan the accepted list is orthonormal and spans the initial vector together with all $P_{E} e_{i}$ . Step 1.1 shows this span is $E$ , and the initial unit vector is first when present.

DefinitionDefinition: Literature-sourcedProof: Not applicablejudge pass (gpt-6-luna)Open item page →

RatioCut and normalized cut for a finite weighted graph

Definition

Let $n \geq 1$ , $V = {1, \dots, n}$ , and let $W = (w_{i j}) \in R^{n \times n}$ be symmetric, entrywise nonnegative, and zero-diagonal. Define $d_{i} = \sum_{j} w_{i j}$ , $D = diag (d_{1}, \dots, d_{n})$ , $L = D - W$ , and $V_{+} = {i : d_{i} > 0}$ . For $A \subseteq V$ , put $A^{c} = V ∖ A$ , $cut (A, A^{c}) = \sum_{i \in A, j \in A^{c}} w_{i j}$ , and $vol (A) = \sum_{i \in A} d_{i}$ . For a partition $A = (A_{1}, \dots, A_{k})$ of $V$ into pairwise disjoint nonempty sets, define $RatioCut (A) = \sum_{r = 1}^{k} \frac{cut (A_{r}, A_{r}^{c})}{∣ A_{r} ∣} .$ For a partition of $V_{+}$ into pairwise disjoint nonempty sets, each of positive volume, define $Ncut (A) = \sum_{r = 1}^{k} \frac{cut (A_{r}, A_{r}^{c})}{vol (A_{r})} .$ For these partitions, the RatioCut indicator column is $h_{r} = 1_{A_{r}} / \sqrt{∣ A_{r} ∣}$ , and the Ncut indicator column is $h_{r} = 1_{A_{r}} / \sqrt{vol (A_{r})}$ , extended by zero on isolated vertices.

Definition references

Finite weighted graph Laplacian

Ulrike von Luxburg, A Tutorial on Spectral Clustering, Statistics and Computing 17(4), 2007

Jean Gallier, Notes on Elementary Spectral Graph Theory: Applications to Graph Clustering Using Normalized Cuts, 2013

LemmaStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (gpt-6-luna)Open item page →

Quadratic form and kernel of a weighted graph Laplacian

Statement

Let $V = {1, \dots, n}$ with $n \geq 1$ , let $W$ be symmetric, nonnegative, and zero-diagonal, let $D = diag (\sum_{j} w_{i j})$ , let $L = D - W$ , and let the support graph have edge ${i, j}$ exactly when $w_{i j} > 0$ . For every $f \in R^{n}$ , $f^{T} L f = \frac{1}{2} \sum_{i, j = 1}^{n} w_{i j} (f_{i} - f_{j})^{2} .$ Consequently $L$ is positive semidefinite and $\ker L = {f \in R^{n} : f is constant on each connected component of the support graph},$ including isolated singleton components.

Statement references

Ulrike von Luxburg, A Tutorial on Spectral Clustering, Statistics and Computing 17(4), 2007

Jean Gallier, Notes on Elementary Spectral Graph Theory: Applications to Graph Clustering Using Normalized Cuts, 2013

Facts & Assumptions

Given: A finite symmetric nonnegative zero-diagonal weight matrix $W$ , its degree matrix $D$ , Laplacian $L = D - W$ , support graph, and an arbitrary vector $f \in R^{n}$ .

[F1]

Finite weighted graph Laplacian: $d_{i} = \sum_{j} w_{i j}$ , $D = diag (d_{i})$ , $L = D - W$ , and the support graph has edge ${i, j}$ exactly when $w_{i j} > 0$ .

Proof

1.1givenF1algebra

By [F1], $f^{T} L f = \sum_{i} d_{i} f_{i}^{2} - \sum_{i, j} w_{i j} f_{i} f_{j}$ . Replacing $d_{i}$ by $\sum_{j} w_{i j}$ , using $w_{i j} = w_{j i}$ to identify the two square sums, and collecting terms gives $f^{T} L f = \frac{1}{2} \sum_{i, j} w_{i j} (f_{i}^{2} - 2 f_{i} f_{j} + f_{j}^{2}) = \frac{1}{2} \sum_{i, j} w_{i j} (f_{i} - f_{j})^{2}$ .

2.1givenF1step 1.1algebra

The displayed sum is nonnegative for every $f$ , and $L$ is symmetric because both $D$ and $W$ are symmetric. Therefore $L$ is positive semidefinite.

2.2givenF1step 1.1algebra

If $L f = 0$ , then $f^{T} L f = 0$ . By step 1.1 this is a finite sum of nonnegative terms, so every term with $w_{i j} > 0$ vanishes and $f_{i} = f_{j}$ on every support edge. Equality propagates along each finite path, hence $f$ is constant on every connected component, including an isolated singleton.

3.1givenF1step 2.2algebra∎

Conversely, suppose $f$ is constant on each support component. For each vertex $i$ , every $j$ with $w_{i j} > 0$ lies in the same component, so $f_{i} = f_{j}$ . Hence $(L f)_{i} = d_{i} f_{i} - \sum_{j} w_{i j} f_{j} = \sum_{j} w_{i j} (f_{i} - f_{j}) = 0$ for every $i$ , and $L f = 0$ . The two inclusions give the stated kernel equality.

LemmaStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (gpt-6-luna)Open item page →

RatioCut and Ncut as indicator-matrix traces

Statement

Let $W, D, L, V, V_{+}$ be as in the finite weighted graph definition. For a square matrix $B$ , set $tr (B) = \sum_{i} B_{i i}$ . If $A_{1}, \dots, A_{k}$ partition $V$ , define $H_{R} \in R^{n \times k}$ by $(H_{R})_{i r} = ∣ A_{r} ∣^{- 1 / 2}$ for $i \in A_{r}$ and $0$ otherwise. Then $H_{R}^{T} H_{R} = I_{k}$ and $RatioCut (A_{1}, \dots, A_{k}) = tr (H_{R}^{T} L H_{R})$ . If $A_{1}, \dots, A_{k}$ partition $V_{+}$ , define $H_{N} \in R^{n \times k}$ by $(H_{N})_{i r} = vol (A_{r})^{- 1 / 2}$ for $i \in A_{r}$ and $0$ otherwise. Then $H_{N}^{T} D H_{N} = I_{k}$ and $Ncut (A_{1}, \dots, A_{k}) = tr (H_{N}^{T} L H_{N})$ .

Statement references

Ulrike von Luxburg, A Tutorial on Spectral Clustering, Statistics and Computing 17(4), 2007

Jean Gallier, Notes on Elementary Spectral Graph Theory: Applications to Graph Clustering Using Normalized Cuts, 2013

Facts & Assumptions

Given: A finite weighted graph with symmetric nonnegative zero-diagonal $W$ , degree matrix $D$ , Laplacian $L = D - W$ , and either a partition of all vertices or a partition of its positive-degree vertices.

[F1]

Finite weighted graph Laplacian: $d_{i} = \sum_{j} w_{i j}$ , $D = diag (d_{i})$ , and $L = D - W$ .

[F2]

RatioCut and normalized cut for a finite weighted graph: $cut (A, A^{c}) = \sum_{i \in A, j \notin A} w_{i j}$ , $vol (A) = \sum_{i \in A} d_{i}$ , RatioCut divides each cut by $∣ A ∣$ , Ncut divides it by $vol (A)$ , and the indicator columns are normalized by $∣ A ∣^{- 1 / 2}$ or $vol (A)^{- 1 / 2}$ respectively.

[F3]

Quadratic form and kernel of a weighted graph Laplacian: $h^{T} L h = \frac{1}{2} \sum_{i, j} w_{i j} (h_{i} - h_{j})^{2}$ for every real vector $h$ .

Proof

1.1givenF2algebra

The supports of distinct RatioCut indicator columns are disjoint, and each column has $∣ A_{r} ∣$ entries equal to $∣ A_{r} ∣^{- 1 / 2}$ . Thus each column has squared norm $1$ and distinct columns have inner product $0$ , so $H_{R}^{T} H_{R} = I_{k}$ .

1.2givenF1F2algebra

The supports of distinct Ncut indicator columns are disjoint, and $h_{r}^{T} D h_{r} = vol (A_{r})^{- 1} \sum_{i \in A_{r}} d_{i} = 1$ . Distinct columns have $D$ -inner product $0$ , so $H_{N}^{T} D H_{N} = I_{k}$ .

1.3givenF2F3algebra

By [F3], the energy of a RatioCut indicator column is $\frac{1}{2} \sum_{i, j} w_{i j} (h_{i} - h_{j})^{2}$ . Terms with both indices inside or both outside $A_{r}$ vanish. Each ordered crossing pair has squared difference $∣ A_{r} ∣^{- 1}$ ; symmetry makes the two directed crossing sums equal, so the factor $1 / 2$ leaves $h_{r}^{T} L h_{r} = cut (A_{r}, A_{r}^{c}) / ∣ A_{r} ∣$ .

1.4givenF2F3algebra

For a Ncut indicator column the same finite energy sum has zero terms except across $A_{r}$ and its complement, and each crossing squared difference is $vol (A_{r})^{- 1}$ . Pairing the two equal directed sums gives $h_{r}^{T} L h_{r} = cut (A_{r}, A_{r}^{c}) / vol (A_{r})$ .

2.1F2step 1.1step 1.2step 1.3step 1.4algebra∎

By the stated trace definition, $tr (H_{R}^{T} L H_{R}) = \sum_{r} h_{r}^{T} L h_{r}$ and $tr (H_{N}^{T} L H_{N}) = \sum_{r} h_{r}^{T} L h_{r}$ . Summing steps 1.3 and 1.4 gives the RatioCut and Ncut identities, while steps 1.1 and 1.2 give their respective indicator constraints.

TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (gpt-6-luna)Open item page →

Weighted RatioCut and Ncut spectral relaxations

Statement

Let $n \geq 1$ , $V = {1, \dots, n}$ , and let $W = (w_{i j}) \in R^{n \times n}$ be symmetric, entrywise nonnegative, and zero-diagonal. Put $d_{i} = \sum_{j} w_{i j}$ , $D = diag (d_{1}, \dots, d_{n})$ , $L = D - W$ , and $V_{+} = {i : d_{i} > 0}$ . If $V_{+} \neq \emptyset$ , let $D_{+}$ and $L_{+}$ be the principal submatrices indexed by $V_{+}$ and set $L_{s y m, +} = D_{+}^{- 1 / 2} L_{+} D_{+}^{- 1 / 2}$ . The matrices $L$ and, when defined, $L_{s y m, +}$ are positive semidefinite. For square $B$ , define $tr (B) = \sum_{i} B_{i i}$ . For $1 \leq k \leq n$ , let $R_{k}$ be the minimum of $\sum_{r} cut (A_{r}, A_{r}^{c}) / ∣ A_{r} ∣$ over partitions of $V$ into $k$ nonempty sets. Then $\min_{H \in R^{n \times k}, H^{T} H = I_{k}} tr (H^{T} L H) = \sum_{i = 1}^{k} λ_{i} (L),$ where the eigenvalues, repeated with multiplicity, are ordered increasingly, and a minimizer consists of orthonormal eigenvectors for the $k$ smallest eigenvalues. This relaxed minimum is a lower bound for $R_{k}$ . When $1 \leq k \leq ∣ V_{+} ∣$ , let $N_{k}$ be the minimum of $\sum_{r} cut (A_{r}, A_{r}^{c}) / vol (A_{r})$ over partitions of $V_{+}$ into $k$ nonempty sets. Then $\min_{H \in R^{∣ V_{+} ∣ \times k}, H^{T} D_{+} H = I_{k}} tr (H^{T} L_{+} H) = \sum_{i = 1}^{k} λ_{i} (L_{s y m, +}),$ attained at $H = D_{+}^{- 1 / 2} Q$ for bottom- $k$ orthonormal eigenvectors $Q$ of $L_{s y m, +}$ . The corresponding columns $u = D_{+}^{- 1 / 2} q$ satisfy $L_{+} u = λ D_{+} u$ , and the relaxed minimum is a lower bound for $N_{k}$ . These lower bounds make no approximation guarantee for a subsequent rounding. Isolated vertices are excluded from the Ncut objective and may be reported separately as singleton outputs.

Statement references

Ulrike von Luxburg, A Tutorial on Spectral Clustering, Statistics and Computing 17(4), 2007

Jean Gallier, Notes on Elementary Spectral Graph Theory: Applications to Graph Clustering Using Normalized Cuts, 2013

Facts & Assumptions

Given: A finite weighted graph with $W = W^{T} \geq 0$ , zero diagonal, $D = diag (d_{i})$ , $L = D - W$ , positive-degree set $V_{+}$ , and an integer $k$ in the admissible range for the partition objective under consideration.

[F1]

Finite weighted graph Laplacian: $d_{i} = \sum_{j} w_{i j}$ , $L = D - W$ , $V_{+} = {i : d_{i} > 0}$ , and $L_{s y m, +} = D_{+}^{- 1 / 2} L_{+} D_{+}^{- 1 / 2}$ on $V_{+}$ when it is nonempty.

[F2]

RatioCut and normalized cut for a finite weighted graph: RatioCut partitions all of $V$ and sums $cut (A_{r}, A_{r}^{c}) / ∣ A_{r} ∣$ ; Ncut partitions only $V_{+}$ and sums $cut (A_{r}, A_{r}^{c}) / vol (A_{r})$ .

[F3]

Quadratic form and kernel of a weighted graph Laplacian: $L$ is positive semidefinite and $f^{T} L f = \frac{1}{2} \sum_{i, j} w_{i j} (f_{i} - f_{j})^{2}$ .

[F4]

RatioCut and Ncut as indicator-matrix traces: RatioCut partitions yield $H_{R}^{T} H_{R} = I_{k}$ and $RatioCut = tr (H_{R}^{T} L H_{R})$ ; positive-volume Ncut partitions yield $H_{N}^{T} D H_{N} = I_{k}$ and $Ncut = tr (H_{N}^{T} L H_{N})$ .

[F5]

Finite-dimensional trace minimization under orthonormal constraints: for a real symmetric matrix $A$ , the minimum of $tr (Q^{T} A Q)$ over $Q^{T} Q = I_{k}$ is the sum of its $k$ smallest eigenvalues, attained by bottom- $k$ orthonormal eigenvectors.

Proof

1.1givenF1F3algebraconstruct

By [F1] and [F3], $L$ is symmetric positive semidefinite. If $x \in R^{∣ V_{+} ∣}$ , extend it by zero on isolates to $\tilde{x} \in R^{n}$ ; then $x^{T} L_{+} x = {\tilde{x}}^{T} L \tilde{x} \geq 0$ , so $L_{+}$ is positive semidefinite. Since $D_{+}^{- 1 / 2}$ is a real diagonal matrix, $y^{T} L_{s y m, +} y = (D_{+}^{- 1 / 2} y)^{T} L_{+} (D_{+}^{- 1 / 2} y) \geq 0$ . Thus both Laplacians in the Statement are positive semidefinite.

1.2givenF2F4algebra

For every partition of $V$ into $k$ nonempty sets, [F4] supplies a feasible $H_{R}$ for the real constraint $H^{T} H = I_{k}$ with trace equal to that partition's RatioCut. The relaxed feasible set therefore contains every discrete indicator matrix, so the infimum over the relaxed feasible set is at most the minimum over the finite nonempty family of partitions.

1.3givenF1F2F4algebra

Let $A_{1}, \dots, A_{k}$ partition $V_{+}$ . By [F4], their normalized indicators, restricted to $V_{+}$ , satisfy $H^{T} D_{+} H = I_{k}$ and have trace objective equal to Ncut. Indeed, if $i$ is isolated then $d_{i} = 0$ and $\sum_{j} w_{i j} = 0$ with $w_{i j} \geq 0$ forces every $w_{i j} = 0$ , so row and column $i$ of $L$ vanish; extending $H$ by zero on isolates leaves the active trace unchanged. Thus the active real feasible set contains every discrete Ncut indicator, and the infimum over the active real feasible set is at most $N_{k}$ .

2.1givenF1F5step 1.2algebra

The matrix $L$ is real symmetric by [F1]. Applying [F5] with $A = L$ gives $\min_{H^{T} H = I_{k}} tr (H^{T} L H) = \sum_{i = 1}^{k} λ_{i} (L)$ , attained by orthonormal eigenvectors for the $k$ smallest eigenvalues. Together with step 1.2 this is the claimed RatioCut lower bound.

2.2givenF1F5step 1.3algebraconstruct

The diagonal entries of $D_{+}$ are strictly positive, so $Q = D_{+}^{1 / 2} H$ is a bijection from $H^{T} D_{+} H = I_{k}$ to $Q^{T} Q = I_{k}$ . It also gives $tr (H^{T} L_{+} H) = tr (Q^{T} D_{+}^{- 1 / 2} L_{+} D_{+}^{- 1 / 2} Q) = tr (Q^{T} L_{s y m, +} Q)$ . Applying [F5] to $L_{s y m, +}$ gives the stated Ncut relaxed minimum and optimizer $H = D_{+}^{- 1 / 2} Q$ ; with step 1.3 this is the claimed lower bound.

3.1F1step 2.2algebra

If $L_{s y m, +} q = λ q$ and $u = D_{+}^{- 1 / 2} q$ , multiplying by $D_{+}^{1 / 2}$ gives $L_{+} u = λ D_{+} u$ . Conversely, if $L_{+} u = λ D_{+} u$ , then $q = D_{+}^{1 / 2} u$ satisfies $L_{s y m, +} q = λ q$ . Thus the symmetric normalized problem is equivalent to the generalized eigenproblem stated.

4.1F1F2step 1.2step 1.3step 2.1step 2.2algebra∎

Every Ncut part is a nonempty subset of $V_{+}$ , so its volume is positive; an isolate has zero volume but is excluded from $N_{k}$ and can only be reinserted as a separately reported singleton. Steps 1.2, 1.3, 2.1, and 2.2 compare feasible sets and compute the lower bounds; they do not bound the RatioCut or Ncut value after an arbitrary rounding.

AlgorithmAlgorithm: Literature-sourcedProof: Not applicablejudge pass (gpt-6-luna)Open item page →

Deterministic weighted spectral clustering with explicit isolate and eigenspace conventions

Definition

Inputs. Integers $n, p \geq 1$ , data $x_{1}, \dots, x_{n} \in R^{p}$ , a fixed deterministic graph-construction procedure $G : (R^{p})^{n} \to R^{n \times n}$ , mode $ratio$ or $normalized$ , and cluster count $k \geq 1$ . In normalized mode also supply a Boolean row-normalization option, defaulting to false.

Compute $W = G (x_{1}, \dots, x_{n})$ . Reject the input unless $W$ is symmetric, entrywise nonnegative, and zero-diagonal. Set $d_{i} = \sum_{j} w_{i j}$ , $D = diag (d_{i})$ , $L = D - W$ , and $V_{+} = {i : d_{i} > 0}$ .
In ratio mode require $k \leq n$ , use all vertices in increasing index order, and set $M = L$ . In normalized mode, if $V_{+} = \emptyset$ , return every vertex as a separately reported singleton with status $no-positive-degree-vertices$ . Otherwise require $k \leq ∣ V_{+} ∣$ , use only $V_{+}$ in increasing index order, and set $M = D_{+}^{- 1 / 2} L_{+} D_{+}^{- 1 / 2}$ .
Compute the exact real eigenspaces of $M$ and order its eigenvalues increasingly with multiplicity. For each eigenspace $E_{λ}$ , use the deterministic projected-coordinate basis rule: for $λ = 0$ , first use $n^{- 1 / 2} 1$ in ratio mode or $D_{+}^{1 / 2} 1 / \sqrt{\sum_{i \in V_{+}} d_{i}}$ in normalized mode; then process the standard coordinate vectors in vertex order, project each onto $E_{λ}$ , orthogonalize against accepted vectors, skip zero residuals, and normalize each nonzero residual. Take the first $k$ eigenvectors as columns of $U$ .
In normalized mode, if row normalization is true, replace each row $u_{i}$ by $u_{i} / ∥ u_{i} ∥_{2}$ , where $∥ v ∥_{2} = \sqrt{\sum_{j = 1}^{k} v_{j}^{2}}$ . The prescribed first zero-mode vector has positive entries on every active vertex, so every active row norm is positive.
Treat the rows of $U$ as points in $R^{k}$ with Euclidean distance $∥ a - b ∥_{2}$ . Initialize the first Lloyd center at the row whose vertex index is smallest among the vertices selected in Step 2. For each subsequent center, choose an unused row maximizing its minimum distance to previously chosen centers, breaking ties by smallest vertex index. Assign each row initially to a nearest center, breaking ties by smallest center index. At each later assignment retain its current label when it is among the nearest centers; otherwise choose the smallest nearest-center index. Replace each nonempty center by the mean of its assigned rows, leave empty-cluster centers unchanged, and repeat until both labels and centers stop changing.
Return the nonempty label sets. In normalized mode append every isolate as a separately reported singleton. Graph rule, edge weights, bandwidth, kNN symmetrization, and cluster count are modeling inputs; this procedure makes no rounding, approximation, graph-consistency, or manifold-recovery guarantee.