Gram matrix rigidity #
Two families of vectors in inner product spaces over ๐ = โ, โ with equal
pairwise inner products are related by a linear isometry. In finite dimension
this upgrades to a linear isometry equivalence of the ambient space, and the
hypothesis can be packaged as equality of Matrix.gram matrices.
The engine is a general fact about a pair of linear maps, an isometric refinement of the first isomorphism theorem:
LinearMap.ker_eq_ker_of_inner_eq: linear mapsS,T(out of a common module, into two inner product spaces) with equal pullback inner productsโชS x, S yโซ = โชT x, T yโซhave equal kernels, sinceS x = 0iffโชS x, S xโซ = 0.LinearMap.rangeEquivOfInnerEq: consequentlyS x โฆ T xdescends to a linear isometry equivalencerange S โโแตข range T: both ranges are canonically isomorphic to the coimageM โงธ ker S = M โงธ ker Tby the first isomorphism theorem, and the hypothesis says exactly that the two induced inner products on the coimage agree.
Everything else is specialization. Applying it to the two linear-combination
maps Finsupp.linearCombination ๐ ฯ and Finsupp.linearCombination ๐ ฯ of
families ฯ, ฯ with equal pairwise inner products (their pullback inner
products then agree by sesquilinearity, inner_linearCombination_eq_of_inner_eq)
turns "equal Gram data" into an isometry of spans:
linearIsometryEquivSpanOfInnerEq: a linear isometry equivalencespan ๐ (range ฯ) โโแตข span ๐ (range ฯ)sending eachฯ itoฯ i. No finiteness is assumed, and the ambient spaces may differ.exists_linearIsometryEquiv_map_eq_of_inner_eq: in a finite-dimensional ambient space this extends (byLinearIsometry.extend) to a linear isometry equivalence of the whole space.TauCeti.Matrix.gram_eq_gram_iff_exists_linearIsometryEquiv_map_eq: the same statement packaged as a characterization ofMatrix.gramequality.
References #
- R. A. Horn and C. R. Johnson, Matrix Analysis, 2nd ed., Cambridge University Press, 2013 โ Gram matrices and factorization up to a unitary factor.
- T.-Y. Chien and S. Waldron, A Characterization of Projective Unitary Equivalence of Finite Frames and Applications, SIAM J. Discrete Math. 30 (2016), no. 2, 976โ994, arXiv:1312.5393 โ the frame-theoretic form: finite frames are unitarily equivalent iff their Gram matrices coincide.
The isometric first isomorphism theorem #
Linear maps with equal pullback inner products have equal kernels:
S x = 0 iff โชS x, S xโซ = 0 iff โชT x, T xโซ = 0 iff T x = 0.
Isometric first isomorphism theorem. Two linear maps S, T out of a common
module with equal pullback inner products, โชS x, S yโซ = โชT x, T yโซ, have canonically
isometric ranges, by S x โฆ T x. This is well defined because both ranges are
first-isomorphism-theorem images of the common coimage M โงธ ker S = M โงธ ker T
(ker_eq_ker_of_inner_eq), and isometric because the hypothesis is precisely the
statement that the two inner products induced on the coimage agree.
Equations
- TauCeti.LinearMap.rangeEquivOfInnerEq S T h = (S.quotKerEquivRange.symm.trans ((S.ker.quotEquivOfEq T.ker โฏ).trans T.quotKerEquivRange)).isometryOfInner โฏ
Instances For
The equivalence built from equal Gram data sends ฯ i to ฯ i; this is the property that
characterises it, the construction itself going through linear combinations.
Families with equal pairwise inner products #
Provenance #
- Original repository: Davis--Kahan/DKPS formalization (Kitware, Inc.).
- Original module:
ForMathlib.Analysis.InnerProductSpace.GramMatrix, moved toForTauCetiin the Wave-1 staging migration; introduced at Davis--Kahan commit56f7495. - Extraction class: moved. The Wave-1 migration renamed the namespace
ForMathlibtoTauCeti; declaration names and proofs are unchanged. - Original authors / copyright: Jon Crall, Claude Fable 5; Copyright (c) 2026 Kitware, Inc.; Apache 2.0.
- Spectra influence: none โ this module imports only Mathlib and sibling
ForTauCetistaging modules.
For families ฯ, ฯ with equal pairwise inner products, the maps of linear combinations
โ cแตข โข ฯ i and โ cแตข โข ฯ i have equal pairwise inner products.
Families with equal pairwise inner products have linear-combination maps with equal kernels:
โ cแตข โข ฯ i = 0 โ โ cแตข โข ฯ i = 0.
A linear isometry equivalence span ๐ (range ฯ) โโแตข span ๐ (range ฯ) sending each
ฯ i to ฯ i, when the families ฯ, ฯ (in possibly different inner product spaces over ๐)
have equal pairwise inner products. It is the isometric first isomorphism theorem
LinearMap.rangeEquivOfInnerEq applied to the two linear-combination maps, whose ranges
are the spans. No finiteness is required, and the ambient spaces need not coincide.
Such an isometry is determined on the spanning family ฯ (LinearMap.eqOn_span), hence unique;
this uniqueness is not separately formalized here.
Equations
- One or more equations did not get rendered due to their size.
Instances For
linearIsometryEquivSpanOfInnerEq computes on linear combinations:
it sends โ cแตข โข ฯ i to โ cแตข โข ฯ i.
linearIsometryEquivSpanOfInnerEq sends each generator ฯ i to ฯ i: the
c = Finsupp.single i 1 case of
linearIsometryEquivSpanOfInnerEq_apply_linearCombination.
If two families ฯ ฯ : ฮน โ E in a finite-dimensional inner product space have equal
pairwise inner products, then there is a linear isometry equivalence W of E with
W (ฯ i) = ฯ i for every i. The span-to-span equivalence
linearIsometryEquivSpanOfInnerEq is extended to E by LinearIsometry.extend and
bundled as an equivalence by finite dimensionality.
Rigid-motion rigidity. Two families in a finite-dimensional real inner product space
with equal pairwise distances differ by a rigid motion: there is a linear isometry
equivalence W and a translation b with ฯ i = W (ฯ i) + b for every i.
This is the affine companion of exists_linearIsometryEquiv_map_eq_of_inner_eq, which needs
equal inner products. Recentring at a base index turns equal distances into equal inner
products by polarisation, and the linear statement then supplies W.
It is the classical fact underlying multidimensional scaling: a configuration is determined by its pairwise distances only up to a rigid motion, so a distance-based embedding can be compared with a target configuration only after alignment.
Approximate rigid-motion rigidity. If the pairwise distances of a sequence of finite configurations converge to those of a target, then eventually each configuration is carried arbitrarily close to the target by some rigid motion.
This is the asymptotic form of exists_rigidMotion_of_dist_eq, and it is what a distance-based
consistency statement needs: multidimensional scaling determines a configuration only up to a
rigid motion, so convergence of the estimates can be asserted only after alignment.
The proof is a compactness argument and uses no spectral hypothesis. Recentring at a base index leaves all distances unchanged and bounds the configurations; a bounded sequence in a finite-dimensional space has a convergent subsequence; the limit has exactly the target's pairwise distances; and the exact statement then supplies a rigid motion, which by continuity serves the whole tail.
Uniform approximate rigid-motion rigidity. For a fixed finite index type, a fixed
tolerance ฮต and a fixed bound D on the diameter of the target, one ฮด > 0 serves every
pair of configurations: if the target has diameter at most D and the pairwise distances agree
to within ฮด, then some rigid motion carries the estimate to within ฮต of the target.
eventually_exists_rigidMotion_dist_lt is the sequential form of the same fact; the uniform
form is what a random target needs, where a modulus that depends on the sample is of no use.
The diameter bound cannot be dropped: the hypothesis and conclusion both scale linearly under a
simultaneous rescaling of the two configurations, so ฮด must be allowed to depend on the size
of the target.
The proof is again pure compactness and uses no spectral hypothesis: a counterexample
sequence, recentred at a base index, is bounded in the finite-dimensional space of
configurations, so both the estimates and the targets subconverge; the two limits have equal
pairwise distances; exists_rigidMotion_of_dist_eq aligns them exactly; and that one rigid
motion then serves a whole tail of the counterexample sequence.
Alignment error and the aligned configuration #
Multidimensional scaling recovers a configuration only up to a rigid motion, so the quantity a
distance-based consistency statement can control is not the uniform distance to the target but
the least uniform distance achievable after moving the estimate by a rigid motion. That is
alignmentError, and alignedConfig is an estimate that very nearly attains it.
The uniform tolerances achievable by carrying ฯ onto ฯ with a rigid motion.
Equations
Instances For
The alignment error of a configuration ฯ against a target ฯ: the least uniform
distance to ฯ achievable by moving ฯ with a rigid motion. It vanishes exactly when the two
configurations are congruent, and by exists_delta_forall_exists_rigidMotion it is small
whenever the pairwise distances are close and the target is not too large.
Equations
- TauCeti.alignmentError ฯ ฯ = sInf (TauCeti.rigidTolerances ฯ ฯ)
Instances For
The set of rigidity tolerances is nonempty.
The set of rigidity tolerances is bounded below, so its infimum exists.
The alignment error is nonnegative.
Any rigid motion achieving a uniform tolerance bounds the alignment error.
The alignment error is approached: for every positive slack some rigid motion achieves it.
The aligned configuration: ฯ moved by a rigid motion that comes within slack t of
the alignment error, and ฯ itself in the degenerate case where no such motion exists (which
exists_rigidMotion_norm_le_alignmentError_add rules out for 0 < t).
This is the object a consistency statement can compare with the target without quantifying the alignment inside the probability: the motion is chosen sample by sample, so the statement "the aligned estimate converges to the target" needs no external alignment sequence.
Equations
- TauCeti.alignedConfig ฯ ฯ t = if h : โ (W : F โโแตข[โ] F) (b : F), โ (i : ฮน), โW (ฯ i) + b - ฯ iโ โค TauCeti.alignmentError ฯ ฯ + t then fun (i : ฮน) => h.choose (ฯ i) + โฏ.choose else ฯ
Instances For
The defining property of alignedConfig.
The dist form of norm_alignedConfig_sub_le.
Uniform approximate rigidity, alignment-error form. One ฮด serves every pair: pairwise
distances within ฮด of a target of diameter at most D force the alignment error below ฮต.
This is the shape a convergence-in-probability argument consumes, because ฮด does not depend
on the sample.
Gram rigidity, Matrix.gram form. Two families of vectors in a
finite-dimensional inner product space have equal Gram matrices if and only if
a linear isometry equivalence of the ambient space maps one family to the other.
The linear map EuclideanSpace ๐ (Fin d) โโ[๐] E sending the j-th standard
basis vector to v j (extended linearly): x โฆ โ j, x j โข v j.
Equations
- TauCeti.familyMap v = Fintype.linearCombination ๐ v โโ โ(WithLp.linearEquiv 2 ๐ (Fin d โ ๐))
Instances For
The family map, unfolded to its expansion in the family.
The coordinate map of an orthonormal family preserves inner products.
The bundled coordinate isometry EuclideanSpace ๐ (Fin d) โโแตข[๐] E of an
orthonormal family v, sending eโฑผ โฆ vโฑผ.
Equations
- TauCeti.familyIsometry hv = (TauCeti.familyMap v).isometryOfInner โฏ
Instances For
The bundled isometry acts as the family map.
It sends the k-th standard basis vector to v k.