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.

Double-centering Euclidean squared distances recovers their centered Gram matrix

Statement

Let $n \geq 1$ . For every symmetric nonnegative zero-diagonal dissimilarity matrix $D$ , the matrix $B = - \frac{1}{2} H_{n} D^{\circ 2} H_{n}$ used by classical multidimensional scaling is symmetric and has a real orthonormal eigendecomposition, though it may have negative eigenvalues. If $D_{i j} = ∥ z_{i} - z_{j} ∥_{2}$ for points $z_{1}, \dots, z_{n} \in R^{d}$ , where $∥ v ∥_{2} = (\sum_{a = 1}^{d} v_{a}^{2})^{1 / 2}$ , then $B = Z_{c} Z_{c}^{T}$ for the centered row-data matrix $Z_{c} = H_{n} Z$ , so $B$ is positive semidefinite. The coordinates formed from all positive eigenvalues reproduce every pairwise distance exactly; if the requested embedding dimension is at least the number of positive eigenvalues, the truncated procedure is exact. The centered configurations obtained from $Z$ and these coordinates are related by a linear isometry between their spans, so the original configurations agree up to translation and Euclidean isometry of their affine spans.

Statement references

Hastie, Tibshirani, and Friedman, ESL II, §14.8, printed pp. 570–572, and §18.5.2, printed pp. 670–672

Cameron, Linear and Nonlinear Dimensionality Reduction, §3, PDF pp. 4–6

Facts & Assumptions

Given: A finite symmetric nonnegative zero-diagonal matrix $D$ , its classical-MDS matrix $B$ , and, in the Euclidean case, points $z_{i}$ with $D_{i j} = ∥ z_{i} - z_{j} ∥_{2}$ .

[F1]

Classical MDS defines $D^{\circ 2}$ entrywise and $B = - \frac{1}{2} H_{n} D^{\circ 2} H_{n}$ for symmetric nonnegative zero-diagonal $D$ (Classical multidimensional scaling from a finite dissimilarity matrix).

[F2]

The centering matrix is symmetric, annihilates $1_{n}$ , and maps onto the zero-sum subspace (The finite centering matrix is the orthogonal projection onto the zero-sum subspace).

[F3]

The standard inner product on $R^{n}$ is $⟨ a, b ⟩ = \sum_{i < n} a_{i} b_{i}$ (The standard formulas $⟨ x, y ⟩ = \sum_{k < n} x_{k} y_{k}$ on $R^{n}$ and $\sum_{k < n} x_{k} \overline{y_{k}}$ on $C^{n}$ are inner products).

[F4]

In an orthonormal basis, a real matrix is self-adjoint exactly when it is symmetric (In an orthonormal basis, self-adjoint means conjugate-transpose symmetry and normal means commuting with the conjugate transpose).

[F5]

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

[F6]

Two finite point lists with equal Gram matrices have linearly isometric spans (Finite configurations with equal Gram matrices have isometric linear spans).

Proof

1.1F1F2F3F4F5algebra

For any permitted $D$ , $D^{\circ 2}$ is symmetric and $H_{n}$ is symmetric by [F2], so $B^{T} = B$ . The standard coordinate basis is orthonormal for [F3], so [F4] makes $B$ self-adjoint and [F5] gives a real orthonormal eigendecomposition; this justifies the spectral step even when some eigenvalues are negative.

1.2givenF1F2F3algebra

Suppose $D_{i j} = ∥ z_{i} - z_{j} ∥_{2}$ and let $Z$ be the matrix with rows $z_{i}^{T}$ . Put $s_{i} = ∥ z_{i} ∥_{2}^{2}$ . Expanding each squared distance with the coordinate inner product [F3] gives $D^{\circ 2} = s 1_{n}^{T} + 1_{n} s^{T} - 2 Z Z^{T}$ , hence $B = - \frac{1}{2} H_{n} (s 1_{n}^{T} + 1_{n} s^{T} - 2 Z Z^{T}) H_{n} = H_{n} Z Z^{T} H_{n} = Z_{c} Z_{c}^{T}$ because $H_{n} 1_{n} = 0$ and $H_{n}^{T} = H_{n}$ by [F2]. For every $a$ , $a^{T} B a = \sum_{r} ((Z_{c}^{T} a)_{r})^{2} \geq 0$ by the coordinate formula [F3], so $B$ is positive semidefinite; also $B 1_{n} = Z_{c} Z_{c}^{T} 1_{n} = 0$ . When $n = 1$ , $H_{1} = 0$ , so $Z_{c} = 0$ and $B = 0$ .

2.1step 1.2F1F5algebra

In the Euclidean-distance case of step 1.2, $B$ is positive semidefinite. By [F5], choose an orthonormal eigenbasis. For each unit eigenvector $u$ with eigenvalue $λ$ , step 1.2 gives $λ = u^{T} B u \geq 0$ . Thus the zero-eigenvalue terms vanish and $B = U_{+} Λ_{+} U_{+}^{T}$ , where $U_{+}$ contains exactly the positive-eigenvalue eigenvectors and $Λ_{+}$ is diagonal with strictly positive entries. If there are no positive eigenvalues, this is the empty decomposition and $B = 0$ . The classical-MDS coordinates from all positive eigenvalues are $Y = U_{+} Λ_{+}^{1 / 2}$ , so $Y Y^{T} = B$ . By step 1.2, $B 1_{n} = 0$ , and each column $u$ of $U_{+}$ with eigenvalue $λ > 0$ satisfies $λ u^{T} 1_{n} = u^{T} B 1_{n} = 0$ ; hence the rows of $Y$ are centered.

3.1step 2.1F1F2F3algebra

By [F2], row $i$ of $Z_{c}$ is $z_{i} - \overset{ˉ}{z}$ , where $\overset{ˉ}{z} = n^{- 1} \sum_{i} z_{i}$ . For each $i, j$ , the coordinate Gram identity gives $∥ y_{i} - y_{j} ∥_{2}^{2} = B_{i i} + B_{j j} - 2 B_{i j} = ∥ z_{i} - \overset{ˉ}{z} - (z_{j} - \overset{ˉ}{z}) ∥_{2}^{2} = ∥ z_{i} - z_{j} ∥_{2}^{2} = D_{i j}^{2}$ . Both distances are nonnegative, so $∥ y_{i} - y_{j} ∥_{2} = D_{i j}$ . The procedure retaining up to the requested dimension $q$ has the same Gram matrix when $q$ is at least the number of positive eigenvalues, so these equalities then hold for its returned coordinates.

4.1step 1.2step 2.1F6algebra∎

The row configurations of $Z_{c}$ and $Y$ have the same Gram matrix $B$ by step 1.2 and step 2.1. Applying [F6] gives an isometry between their spans. The original rows of $Z$ differ from those of $Z_{c}$ by the common translation $\overset{ˉ}{z}$ , so the original and embedded configurations are congruent after this translation. For a non-Euclidean $D$ , step 1.1 still gives a symmetric spectral problem, but step 1.2 is unavailable and no exact-distance conclusion follows.

Depends on

Used by

Cited to discharge well-definedness by Classical multidimensional scaling from a finite dissimilarity matrix.

Dependency tree · two levels

17 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

The Elements of Statistical Learning, second edition, corrected 12th printing (standard reference, not scraped)
Maria Cameron, Linear and Nonlinear Dimensionality Reduction, lecture notes (standard reference, not scraped)