Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Sorted rectangular SVD with orthonormal completion of zero singular directions

Proved
QuantumLinearAlgebra.sorted_svd_of_finrank_le

by Mrnaiq · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

linear-algebraquantum-informationsingular-value-decomposition

Let EEE and FFF be finite-dimensional complex inner product spaces, with n=dim⁡E≤m=dim⁡Fn=\dim E\le m=\dim Fn=dimE≤m=dimF, and let T:E→FT:E\to FT:E→F be linear. There are orthonormal bases (bi)i=0n−1(b_i)_{i=0}^{n-1}(bi​)i=0n−1​ of EEE and (cj)j=0m−1(c_j)_{j=0}^{m-1}(cj​)j=0m−1​ of FFF, and real numbers s0≥⋯≥sn−1≥0s_0\ge\cdots\ge s_{n-1}\ge0s0​≥⋯≥sn−1​≥0, such that

Tbi=sici(0≤i<n).T b_i=s_i c_i\qquad(0\le i<n).Tbi​=si​ci​(0≤i<n).

Zero singular values are included; their left vectors are completed to an orthonormal basis of the full codomain. The conclusion also covers zero-dimensional spaces. This is the rectangular singular value decomposition in a form that can be applied directly to maps between projector image subspaces, as needed for Definition 11 of the QSVT paper.

Formalization Note. The index inclusion is Fin.castLE hnm; basis vectors and singular values use zero-based indexing. This supporting lemma states the standard linear-map SVD underlying the paper's projected-unitary instance, with the explicit dimension order shown above.

Preamble
import Mathlib.Analysis.InnerProductSpace.SingularValues
set_option autoImplicit false
Formal statement
namespace QuantumLinearAlgebra
theorem sorted_svd_of_finrank_le {E F : Type*} [NormedAddCommGroup E] [NormedAddCommGroup F]
    [InnerProductSpace ℂ E] [InnerProductSpace ℂ F]
    [FiniteDimensional ℂ E] [FiniteDimensional ℂ F] (T : E →ₗ[ℂ] F) (hnm : Module.finrank ℂ E ≤ Module.finrank ℂ F) :
    ∃ (b : OrthonormalBasis (Fin (Module.finrank ℂ E)) ℂ E)
      (c : OrthonormalBasis (Fin (Module.finrank ℂ F)) ℂ F)
      (s : Fin (Module.finrank ℂ E) → ℝ),
      (∀ i, 0 ≤ s i) ∧ Antitone s ∧
      ∀ i, T (b i) = (s i : ℂ) • c (Fin.castLE hnm i) := by sorry
end QuantumLinearAlgebra
Source
Supporting standard SVD for Gilyén, Su, Low, Wiebe, arXiv:1806.01838v1, p.15, Definition 11, Eq.(17), https://arxiv.org/abs/1806.01838v1 . Proof construction adapts the Gram-matrix and orthonormal-completion argument of OAI.GAD.exists_unitary_singular_decomposition, https://github.com/openai/math/blob/1581d4cbdd69a0faf34b2089614fe2a814316a6a/lean/OAI/InformationTheory/AmplitudeDamping/ZeroBlockEntropy.lean#L236-L293, to rectangular maps and decreasingly ordered singular values.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me