AFTD Auto-Formalizing Theoretical Domains

singularValuesSorted_nonneg

theoremverifiedformalizationimported Lean

Sorted singular values are nonneg.

Statement

set_option autoImplicit true in
set_option relaxedAutoImplicit true in
open Finset BigOperators Matrix in
variable {d : Type*} [Fintype d] [DecidableEq d] in
lemma singularValuesSorted_nonneg (A : Matrix d d ℂ) (i : Fin (Fintype.card d)) :
    0 ≤ singularValuesSorted A i
Formalizes
QuantumInfo, `singularValuesSorted_nonneg`
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.
Verified
17 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • singularValuesThe singular values of a square complex matrix A, defined as the square roots of the eigenvalues of A†A. These are indexed by d…
  • singularValuesSortedThe sorted singular values of a square complex matrix, in decreasing order, indexed by Fin (Fintype.card d). We define them by sorting…
  • singularValues_nonnegSingular values are nonneg.
Used by 2
  • singularValuesSorted_mul_leThe largest singular value of a matrix product is at most the product of the largest singular values: σ₁(M * N) ≤ σ₁(M) * σ₁(N). This is…
  • holder_step_for_singularValuesThe finite-sum Hölder inequality applied to sequences of r-th powers of sorted singular values. With conjugate exponents p' = p/r > 1…

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
/-- Sorted singular values are nonneg. -/
lemma singularValuesSorted_nonneg (A : Matrix d d ℂ) (i : Fin (Fintype.card d)) :
    0 ≤ singularValuesSorted A i := by
  have h_nonneg : ∀ i, 0 ≤ (singularValues A i) := by
    exact singularValues_nonneg A
  have h_sorted_nonneg : ∀ {l : List ℝ}, (∀ x ∈ l, 0 ≤ x) → ∀ i < l.length, 0 ≤ l[i]! := by
    aesop
  contrapose! h_sorted_nonneg
  use Multiset.sort (Finset.univ.val.map (singularValues A)) (· ≥ ·)
  refine' ⟨_, i, _, _⟩
  · aesop
  · simp [Finset.card_univ]
  · convert h_sorted_nonneg using 1
    unfold singularValuesSorted; aesop
See it in the graphDiscuss this resultChallenge it