TheoremStatement: Literature-sourcedProof: AI-adaptedPipeline-generatedprecheck passjudge pass (gpt-6-luna)

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.

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.

Depends on

Used by

Deterministic weighted spectral clustering with explicit isolate and eigenspace conventions Algorithm

Dependency tree · two levels

7 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Ulrike von Luxburg, A Tutorial on Spectral Clustering, Statistics and Computing 17(4), 2007 (standard reference, not scraped)
Jean Gallier, Notes on Elementary Spectral Graph Theory: Applications to Graph Clustering Using Normalized Cuts, 2013 (standard reference, not scraped)