LemmaStatement: 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.

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.

Depends on

Used by

Weighted RatioCut and Ncut spectral relaxations Theorem

Dependency tree · one level

3 results within one dependency step 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)