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.

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.

Depends on

The orthogonal projection $P_Wv$ is the $W$-component in $V=W\oplus W^\perp$

Used by

Deterministic weighted spectral clustering with explicit isolate and eigenspace conventions Algorithm

Dependency tree · two levels

2 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)