exists_sorting_equiv
theoremverifiedformalizationimported Lean
There exists a bijection σ : Fin (card d) ≃ d such that singularValues M (σ i) = singularValuesSorted M i for all i.
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in open Finset BigOperators Matrix in variable {d : Type*} [Fintype d] [DecidableEq d] in set_option backward.isDefEq.respectTransparency false in lemma exists_sorting_equiv (M : Matrix d d ℂ) : ∃ σ : Fin (Fintype.card d) ≃ d, ∀ i, singularValues M (σ i) = singularValuesSorted M i
- Formalizes
- QuantumInfo, `exists_sorting_equiv`
- Lean proof
- By Alex Meiburg, from github.com/leanprover-community/physlib at
e411c6e89692(Copyright (c) 2026 Alex Meiburg. All rights reserved, Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.34.1.exists_sorting_equiv← exists_sorting_equiv (QuantumInfo/ForMathlib/Majorization.lean:470): verbatim
- Verified
- 17 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- singularValuesThe singular values of a square complex matrix
A, defined as the square roots of the eigenvalues ofA†A. These are indexed byd… - singularValuesSortedThe sorted singular values of a square complex matrix, in decreasing order, indexed by
Fin (Fintype.card d). We define them by sorting…
- singularValuesThe singular values of a square complex matrix
Lean source view module on GitHub
set_option autoImplicit true in set_option relaxedAutoImplicit true in open Finset BigOperators Matrix in variable {d : Type*} [Fintype d] [DecidableEq d] in set_option backward.isDefEq.respectTransparency false in /-- There exists a bijection `σ : Fin (card d) ≃ d` such that `singularValues M (σ i) = singularValuesSorted M i` for all `i`. -/ lemma exists_sorting_equiv (M : Matrix d d ℂ) : ∃ σ : Fin (Fintype.card d) ≃ d, ∀ i, singularValues M (σ i) = singularValuesSorted M i := by -- Apply the lemma `exists_subset_prod_eq_sorted_prod` to obtain the bijection `σ`. have h_bij : ∃ σ : Fin (Fintype.card d) ≃ d, ∀ i, singularValues M (σ i) = singularValuesSorted M i := by have h_perm : Multiset.ofList (List.ofFn (singularValuesSorted M)) = Multiset.ofList (List.ofFn (singularValues M ∘ (Fintype.equivFin d).symm)) := by have h_multiset : Multiset.ofList (List.ofFn (singularValues M ∘ (Fintype.equivFin d).symm)) = Finset.univ.val.map (singularValues M) := by have h_multiset : Finset.univ.val = Multiset.map (fun i => (Fintype.equivFin d).symm i) (Finset.univ.val) := by exact Eq.symm (Multiset.map_univ_val_equiv (Fintype.equivFin d |> Equiv.symm)) rw [h_multiset, Multiset.map_map] aesop have h_multiset_sorted : Multiset.ofList (List.ofFn (singularValuesSorted M)) = Multiset.map (singularValues M) Finset.univ.val := by have h_multiset_sorted_eq : List.ofFn (singularValuesSorted M) = Multiset.sort (Multiset.map (singularValues M) Finset.univ.val) (· ≥ ·) := by refine' List.ext_get _ _ <;> simp [List.ofFn_eq_map] at *; aesop (simp_config := { singlePass := true }) exact h_multiset_sorted_eq ▸ by simp rw [h_multiset, h_multiset_sorted] have h_perm : List.Perm (List.ofFn (singularValuesSorted M)) (List.ofFn (singularValues M ∘ (Fintype.equivFin d).symm)) := by exact Multiset.coe_eq_coe.mp h_perm have h_perm : ∃ σ : Fin (Fintype.card d) ≃ Fin (Fintype.card d), ∀ i, singularValuesSorted M i = singularValues M (Fintype.equivFin d |>.symm (σ i)) := by have h_perm : ∀ {l1 l2 : List ℝ}, l1.Perm l2 → ∃ σ : Fin l1.length ≃ Fin l2.length, ∀ i, l1.get i = l2.get (σ i) := by intros l1 l2 h_perm; induction' h_perm with l1 l2 h_perm ih <;> simp_all · obtain ⟨σ, hσ⟩ := ‹∃ σ : Fin l2.length ≃ Fin h_perm.length, ∀ i : Fin l2.length, l2[i] = h_perm[σ i]›; use Equiv.ofBijective (fun i => Fin.cases 0 (fun i => Fin.succ (σ i)) i) ⟨fun i j hij => ?_, fun i => ?_⟩ simp_all [Fin.forall_fin_succ] · rcases i with ⟨_ | i, hi⟩ <;> rcases j with ⟨_ | j, hj⟩ <;> simp_all [Fin.ext_iff] simpa [Fin.ext_iff] using σ.injective (Fin.ext hij) · refine i.cases ?_ ?_ · simp [Fin.exists_fin_succ] · simp only [Fin.exists_fin_succ, Fin.cases_zero, Fin.cases_succ, Fin.succ_inj] exact fun i => Or.inr ⟨σ.symm i, by simp⟩ · refine' ⟨Equiv.swap ⟨0, by simp⟩ ⟨1, by simp⟩, _⟩; simp [Fin.forall_fin_succ]; aesop · rename_i h₁ h₂ h₃ h₄ obtain ⟨σ₁, hσ₁⟩ := h₃ obtain ⟨σ₂, hσ₂⟩ := h₄ use σ₁.trans σ₂ simp [hσ₁, hσ₂] obtain ⟨σ, hσ⟩ := h_perm ‹_› refine ⟨Equiv.ofBijective (fun i => ⟨σ ⟨i, ?_⟩, ?_⟩) ⟨?_, ?_⟩, ?_⟩ · simp · exact lt_of_lt_of_le (Fin.is_lt _) (by simp) · norm_num [Function.Injective, Function.Surjective] exact fun i j hij => Fin.ext <| by simpa [Fin.ext_iff] using σ.injective <| Fin.ext hij · intro b obtain ⟨a, ha⟩ : ∃ a : Fin (List.ofFn (singularValuesSorted M)).length, σ a = ⟨b, by simp⟩ := by exact σ.surjective _ use ⟨a, lt_of_lt_of_le a.2 (by simp)⟩ exact Fin.ext (by simp [ha]) · intro i specialize hσ ⟨i, by simp⟩ simp_all exact ⟨Equiv.trans h_perm.choose (Fintype.equivFin d |> Equiv.symm), fun i => h_perm.choose_spec i ▸ rfl⟩ exact ⟨h_bij.choose, fun i => by simpa only [Equiv.symm_apply_eq] using h_bij.choose_spec i⟩