Chapter 07 — Spectral Functions
Proofs omitted. Hover over highlighted terms to see their Lean types.
Definition 7.1
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Definition 7.1: a proper extended-real-valued function on ι → ℝ is symmetric with respect to a family 𝒜 of orthogonal matrices if it is invariant under the action of every element of 𝒜.
universe u
variable {ι : Type u} [Fintype ι] [DecidableEq ι]
class IsSymmetricFunction (𝒜 : Set (Matrix.orthogonalGroup ι ℝ))
(f : (ι → ℝ) → EReal) : Prop extends IsProperExtendedRealFunction f where
map_smul (A : Matrix.orthogonalGroup ι ℝ) (hA : A ∈ 𝒜) (x : ι → ℝ) :
f (A • x) = f xProposition 7.1
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Proposition 7.1: every real symmetric matrix admits an orthogonal diagonalization whose diagonal entries are the eigenvalues of the matrix.
open Matrix
variable {n : ℕ}
theorem symmetric_matrix_exists_orthogonal_diagonalization
(X : Matrix (Fin n) (Fin n) ℝ) (hX : X.IsSymm) :
∃ U : Matrix.orthogonalGroup (Fin n) ℝ,
X = (U : Matrix (Fin n) (Fin n) ℝ) * diagonal (hX.isHermitian_of_real.eigenvalues) *
(U : Matrix (Fin n) (Fin n) ℝ)ᵀTheorem 7.1
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Theorem 7.1: Fan's inequality for real symmetric matrices states that the trace pairing Tr(XY) is bounded above by the Euclidean pairing of the ordered eigenvalue vectors λ(X) and λ(Y).
open Matrix
open scoped Matrix
variable {n : ℕ}
local notation "Mₙ" => Matrix (Fin n) (Fin n) ℝ
local notation "𝕊" => selfAdjoint.submodule ℝ (Mₙ)
theorem fan_inequality_trace_le_dotProduct_eigenvalues (X Y : 𝕊) :
let hX := X.property.isHermitian
let hY := Y.property.isHermitian
trace ((X : Mₙ) * (Y : Mₙ)) ≤ dotProduct hX.eigenvalues hY.eigenvaluesDefinition 7.2
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Definition 7.2 is recall-only in the Chapter 7 symmetry API. The core/canonical owner abstraction is mathlib's Function.Even; the textbook identity f x = f (-x) is a thin bridge/view reformulation of that owner, not a second definition.
recall Function.EvenTheorem 7.2
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Theorem 7.2: for a permutation symmetric function f on ℝ^n, the Fenchel conjugate of the spectral function f ∘ λ on 𝕊^n, viewed on 𝕊^n through the Frobenius Riesz map toDualMap ℝ 𝕊, is the vector-side Fenchel conjugate f* composed with the ordered eigenvalue map λ.
open Matrix
open InnerProductSpace
open scoped BigOperators
variable {n : ℕ}
local notation "Mₙ" => Matrix (Fin n) (Fin n) ℝ
local notation "𝕊" => symmetricMatrices n
theorem spectral_conjugate_formula
(f : (Fin n → ℝ) → EReal) (hf : IsPermutationSymmetricFunction f) :
(fun Y : 𝕊 ↦ conjugate_function (f ∘ symmetric_eigenvalue_function) ↑(toDualMap ℝ 𝕊 Y)) =
fun Y : 𝕊 ↦ conjugate_function f (dotProductEquiv ℝ (Fin n) (symmetric_eigenvalue_function Y))Definition 7.3
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Definition 7.3: an extended-real-valued function on ι → ℝ is absolutely symmetric when it depends only on the coordinatewise absolute values of its input, equivalently when f x = f (|x|) for every x. For ι = Fin n, this is the textbook notion on ℝⁿ.
namespace Function
variable {ι : Type*}
def IsAbsolutelySymmetric (f : (ι → ℝ) → EReal) : Prop :=
∀ x, f x = f (|x|)Theorem 7.3
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Theorem 7.3: if f : ℝ^n → (-∞, ∞] is permutation symmetric, proper, closed, and convex, and if a real symmetric matrix X satisfies X = U * diag (symmetricMatrixEigenvalues X hX) * Uᵀ, then the proximal set of the ambient spectral lift of f at X is the image of the Euclidean vector proximal set at the ordered eigenvalue vector of X under the map x ↦ U * diag x * Uᵀ. The vector-side proximal problem is stated on EuclideanSpace ℝ (Fin n) and evaluates f through .ofLp, matching the Frobenius geometry of diagonal matrices.
open Matrix
open scoped Matrix Matrix.Norms.Frobenius
variable {n : ℕ}
local notation "Mₙ" => Matrix (Fin n) (Fin n) ℝ
local notation "𝕊" => symmetricMatrices n
local notation "symmetricEigenvalues" => symmetric_eigenvalue_function
theorem prox_symmetricSpectralLift_eq_image_orthogonalDiagonalMap
(f : (Fin n → ℝ) → EReal) (hf_perm : IsPermutationSymmetricFunction f)
(hf_closed : LowerSemicontinuous f) (hf_convex : is_convex_function f)
(X : Mₙ) (hX : X.IsSymm) (U : Matrix.orthogonalGroup (Fin n) ℝ)
(hdiag : X = orthogonalDiagonalMap U (symmetricMatrixEigenvalues X hX)) :
prox[symmetricSpectralLift f] X =
orthogonalDiagonalMapEuclidean U ''
prox[fun y : EuclideanSpace ℝ (Fin n) ↦ f y.ofLp]
(WithLp.toLp (p := (2 : ENNReal)) (symmetricMatrixEigenvalues X hX))Definition 7.4
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Definition 7.4: an extended-real-valued function on a normed additive space is norm-dependent when it factors through the ambient norm via a proper one-variable profile, canonically extended by ⊤ on the negative ray. For E = EuclideanSpace ℝ (Fin n), this is the textbook notion on ℝ^n.
universe u
namespace Function
variable {E : Type u} [NormedAddCommGroup E]
class IsNormDependent (f : E → EReal) : Prop where
profile_exists :
∃ g : ℝ → EReal,
IsProperExtendedRealFunction g ∧
(∀ t : ℝ, t < 0 → g t = ⊤) ∧
f = g ∘ normProposition 7.4
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Proposition 7.4: let T ⊆ 𝕊^n be associated to C ⊆ ℝ^n in the sense of Definition 7.14. If C is closed and convex, then the projection set of X onto T is obtained by conjugating the Euclidean projection set of the ordered eigenvalue vector λ(X) onto the canonical Euclidean realization of C by the same orthogonal diagonalizer U. This is the chapter's set-valued form of equation (7.6).
open Matrix
variable {n : ℕ}
local notation "Mₙ" => Matrix (Fin n) (Fin n) ℝ
local notation "Eₙ" => EuclideanSpace ℝ (Fin n)
local notation "𝕊" => symmetricMatrices n
local notation "symmetricEigenvalues" => symmetric_eigenvalue_function
theorem projection_mapping_eq_image_projection_mapping_eigenvalues_of_associatedSet
{T : Set 𝕊} {C : Set (Fin n → ℝ)} (hTC : IsAssociatedSymmetricSpectralSet T C)
(hC_closed : IsClosed C) (hC_convex : Convex ℝ C)
(X : 𝕊) (U : Matrix.orthogonalGroup (Fin n) ℝ)
(hdiag : X = orthogonalDiagonalMapToSymmetric U (symmetricEigenvalues X)) :
P[T] X =
orthogonalDiagonalMapEuclideanToSymmetric U ''
P[WithLp.toLp (p := (2 : ENNReal)) '' C]
(WithLp.toLp (p := (2 : ENNReal)) (symmetricEigenvalues X))Theorem 7.4
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Theorem 7.4 (1): von Neumann's trace inequality for real m × n matrices says that the Frobenius pairing Tr(Xᵀ Y) is bounded above by the Euclidean pairing of the ordered singular value vectors σ(X) and σ(Y).
open Matrix
open scoped Matrix
variable {m n : ℕ}
theorem von_neumann_trace_inequality (X Y : Matrix (Fin m) (Fin n) ℝ) :
Matrix.trace (Xᵀ * Y) ≤
dotProduct (singular_value_function X) (singular_value_function Y)Definition 7.5
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Definition 7.5: for x ∈ ℝ^n, the textbook notation x↓ is the decreasing rearrangement of x, namely the vector obtained by reordering the coordinates of x in nonincreasing order.
variable {n : ℕ}
recall descendingRearrangementProposition 7.5
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Proposition 7.5: if C ⊆ ℝ^(min(m,n)) is nonempty, closed, and convex and its indicator function is absolutely permutation symmetric, then the projection set of a real m × n matrix X onto the rectangular spectral set T = {Y | σ(Y) ∈ C} is obtained by applying the same orthogonal singular-vector factors from a singular value decomposition X = U * rectangularDiagonal (σ(X)) * Vᵀ to the projection set of the singular-value vector σ(X) onto C. This is the chapter's set-valued rendering of the textbook identity P_T(X) = U dg(P_C(σ(X))) Vᵀ.
open InnerProductSpace
open scoped Matrix Matrix.Norms.Frobenius
variable {m n : ℕ}
local notation "𝕄" => Matrix (Fin m) (Fin n) ℝ
local notation "Mₘ" => Matrix (Fin m) (Fin m) ℝ
local notation "Mₙ" => Matrix (Fin n) (Fin n) ℝ
local notation "𝕍" => Fin (min m n) → ℝ
theorem projection_mapping_rectangularSpectralSet_eq_image_projection_mapping_singular_values
(C : Set (Fin (min m n) → ℝ))
(hC_abs : Function.IsAbsolutelyPermutationSymmetric (extendedIndicator C))
(hC_nonempty : C.Nonempty) (hC_closed : IsClosed C) (hC_convex : Convex ℝ C)
(X : 𝕄) (U : Matrix.orthogonalGroup (Fin m) ℝ) (V : Matrix.orthogonalGroup (Fin n) ℝ)
(hsvd : X = orthogonalRectangularDiagonalMap U V (singular_value_function X)) :
P[rectangularSpectralSet C] X =
orthogonalRectangularDiagonalMap U V '' P[C] (singular_value_function X)Theorem 7.5
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Theorem 7.5: for an absolutely permutation-symmetric extended-real-valued function f on ℝ^(min(m,n)), the Fenchel conjugate of the spectral lift f ∘ σ on ℝ^(m × n), viewed on the matrix space through the Frobenius Riesz map toDualMap ℝ 𝕄, is the vector-side Fenchel conjugate f* composed with the singular-value map σ.
open InnerProductSpace
open scoped Matrix Function
variable {m n : ℕ}
local notation "𝕄" => Matrix (Fin m) (Fin n) ℝ
theorem matrix_spectral_conjugate_formula
(f : (Fin (min m n) → ℝ) → EReal) (hf : Function.IsAbsolutelyPermutationSymmetric f) :
(fun Y : 𝕄 ↦ conjugate_function (f ∘ singular_value_function) ↑(toDualMap ℝ 𝕄 Y)) =
fun Y : 𝕄 ↦
conjugate_function f
(dotProductEquiv ℝ (Fin (min m n)) (singular_value_function Y))Definition 7.6
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Definition 7.6: permutationMatrices n is the set of all n × n real permutation matrices, denoted in the text by Λ_n; equivalently, it is the range of the canonical map sending a permutation of Fin n to its permutation matrix.
variable {n : ℕ}
def permutationMatrices (n : ℕ) : Set (Matrix (Fin n) (Fin n) ℝ) :=
Set.range fun σ : Equiv.Perm (Fin n) ↦ σ.permMatrix ℝ
-- Proof sketch: unfold `permutationMatrices`; the right-hand side is exactly the defining
-- range used in the declaration.Theorem 7.6
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Theorem 7.6: if f : ℝ^(min m n) → (-∞, ∞] is absolutely permutation symmetric and proper, then its symmetric spectral lift f ∘ σ to real m × n matrices via the singular-value map σ = singular_value_function is closed and convex if and only if f is closed and convex. Here closedness is expressed by LowerSemicontinuous and convexity by is_convex_function.
open Function Matrix
open InnerProductSpace
open scoped Function
variable {m n : ℕ}
local notation "𝕄" => Matrix (Fin m) (Fin n) ℝ
theorem absolutely_symmetric_spectral_function_closed_convex_iff
(f : (Fin (min m n) → ℝ) → EReal) (hf : IsAbsolutelyPermutationSymmetric f) :
(LowerSemicontinuous (f ∘ singular_value_function) ∧
is_convex_function (f ∘ singular_value_function)) ↔
(LowerSemicontinuous f ∧ is_convex_function f)Definition 7.7
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Definition 7.7: generalizedPermutationMatrices n is the set of all real n × n generalized permutation matrices, denoted in the text by Λ^G_n.
variable {n : ℕ}
def generalizedPermutationMatrices (n : ℕ) : Set (Matrix (Fin n) (Fin n) ℝ) :=
{A | Matrix.IsGeneralizedPermutation A}
-- Proof sketch: unfold `generalizedPermutationMatrices`; the right-hand side is exactly the
-- defining set of matrices satisfying `Matrix.IsGeneralizedPermutation`.Theorem 7.7
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Theorem 7.7: if f : ℝ^(min(m,n)) → (-∞, ∞] is absolutely permutation symmetric, closed, and convex, and if X = U * rectangularDiagonal (singular_value_function X) * Vᵀ, then the proximal set of the matrix spectral lift f ∘ singular_value_function at X is the orthogonal image of the Euclidean vector proximal set of f at σ(X) = singular_value_function X. The vector-side proximal problem is stated on EuclideanSpace ℝ (Fin (min m n)), matching the Frobenius geometry of rectangular diagonal matrices.
open Matrix
open scoped Matrix Matrix.Norms.Frobenius
variable {m n : ℕ}
local notation "𝕄" => Matrix (Fin m) (Fin n) ℝ
local notation "Mₘ" => Matrix (Fin m) (Fin m) ℝ
local notation "Mₙ" => Matrix (Fin n) (Fin n) ℝ
theorem prox_matrixSpectralLift_eq_image_orthogonalRectangularDiagonalMap
(f : (Fin (min m n) → ℝ) → EReal) (hf_symm : Function.IsAbsolutelyPermutationSymmetric f)
(hf_closed : LowerSemicontinuous f) (hf_convex : is_convex_function f)
(X : 𝕄) (U : Matrix.orthogonalGroup (Fin m) ℝ)
(V : Matrix.orthogonalGroup (Fin n) ℝ)
(hsvd : X = orthogonalRectangularDiagonalMap U V (singular_value_function X)) :
prox[f ∘ singular_value_function] X =
orthogonalRectangularDiagonalMapEuclidean U V ''
prox[fun y : EuclideanSpace ℝ (Fin (min m n)) ↦ f y.ofLp]
(WithLp.toLp (p := (2 : ENNReal)) (singular_value_function X))Definition 7.8
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Definition 7.8: a proper extended-real-valued function on ℝ^n is permutation symmetric when it is invariant under every permutation matrix.
variable {n : ℕ}
-- Proof sketch: permutation matrices are orthogonal because their transpose is the permutation
-- matrix of the inverse permutation, so the product with the transpose is the identity matrix.
notation "Λ[" n "]" => permutationOrthogonalFamily n
postfix:max "↓" => descendingRearrangement
abbrev IsPermutationSymmetricFunction (f : (Fin n → ℝ) → EReal) : Prop :=
IsSymmetricFunction Λ[n] fTheorem 7.8
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Theorem 7.8 (1): for a permutation-symmetric extended-real-valued function on ℝ^n, the spectral lift f ∘ λ on 𝕊^n is lower semicontinuous if and only if f is lower semicontinuous. Here λ denotes symmetricEigenvalues.
open Function Matrix
open scoped Matrix
variable {n : ℕ}
local notation "𝕊" => symmetricMatrices n
local notation "Mₙ" => Matrix (Fin n) (Fin n) ℝ
local notation "symmetricEigenvalues" => symmetric_eigenvalue_function
theorem symmetric_spectral_function_lowerSemicontinuous_iff
(f : (Fin n → ℝ) → EReal) (hf : IsPermutationSymmetricFunction f) :
LowerSemicontinuous (f ∘ symmetricEigenvalues) ↔ LowerSemicontinuous fDefinition 7.9
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Definition 7.9: a proper extended-real-valued function on ℝ^n is absolutely permutation symmetric when it depends only on the decreasing rearrangement |x|↓ of the absolute coordinate values, equivalently on the signed-permutation orbit of x.
namespace Function
variable {n : ℕ}
scoped postfix:max "↓" => Function.descendingRearrangement
open scoped Function
-- Proof sketch: unfold `descendingRearrangement`; evaluation at coordinate `i` is definitionally
-- the `i`-th entry of the decreasingly sorted coordinate list.
class IsAbsolutelyPermutationSymmetric (f : (Fin n → ℝ) → EReal) : Prop
where
ne_bot : ∀ x, f x ≠ ⊥
effective_domain_nonempty : {x | f x < ⊤}.Nonempty
map_eq_abs_descendingRearrangement (x : Fin n → ℝ) : f x = f (|x|↓)
-- Proof sketch: unfold `Function.IsAbsolutelyPermutationSymmetric`; the only extra datum beyond
-- properness is exactly the normal-form identity `f x = f (|x|↓)` for every `x`.Theorem 7.9
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Theorem 7.9: if f is symmetric with respect to 𝒜, then its Fenchel conjugate, viewed on ℝ^n through dotProductEquiv, is invariant under every orthogonal matrix in 𝒜.
variable {n : ℕ}
theorem conjugate_function_eq_conjugate_function_orthogonal_mulVec
(𝒜 : Set (Matrix.orthogonalGroup (Fin n) ℝ)) (f : (Fin n → ℝ) → EReal)
(hf : IsSymmetricFunction 𝒜 f) :
∀ A : Matrix.orthogonalGroup (Fin n) ℝ, A ∈ 𝒜 →
∀ y : Fin n → ℝ,
conjugate_function f (dotProductEquiv ℝ (Fin n) (A • y)) =
conjugate_function f (dotProductEquiv ℝ (Fin n) y)Definition 7.10
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Definition 7.10: the eigenvalue function λ : 𝕊^n → ℝ^n sends a real symmetric matrix to its eigenvalues listed in weakly decreasing order.
open Matrix
variable {n : ℕ}
local notation "𝕊" => selfAdjoint.submodule ℝ (Matrix (Fin n) (Fin n) ℝ)
noncomputable def symmetric_eigenvalue_function (X : 𝕊) : Fin n → ℝ :=
fun i ↦ (X.property.isHermitian).eigenvalues₀ (Fin.cast (Fintype.card_fin n).symm i)
-- Proof sketch: unfold `symmetric_eigenvalue_function`; its `i`-th coordinate is definitionally
-- the `i`-th entry of the ordered Hermitian spectrum of `X`, transported along the canonical
-- equality `Fintype.card (Fin n) = n`.Definition 7.11
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Definition 7.11: a proper extended-real-valued function on real symmetric n × n matrices is spectral when it factors through the ordered eigenvalue map of a proper function on ℝ^n; any such factor is an associated function.
notation "𝕊[" n "]" => {A : Matrix (Fin n) (Fin n) ℝ // Matrix.IsSymm A}
namespace Function
class IsSpectralFunction {n : ℕ} (g : 𝕊[n] → EReal) : Prop
extends IsProperExtendedRealFunction g where
associatedFunction_exists :
∃ f : (Fin n → ℝ) → EReal, IsProperExtendedRealFunction f ∧
∀ X : 𝕊[n], g X = f (symmetricEigenvalues X)
-- Proof sketch: unpack `Function.IsSpectralFunction`; it consists exactly of properness of `g`
-- together with the existence of a proper function on `ℝ^n` whose composition with
-- `symmetricEigenvalues` recovers `g`.Definition 7.12
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Definition 7.12: the spectahedron γ[n] is the set of positive semidefinite real n × n matrices with trace equal to 1.
variable {n : ℕ}
def spectahedron (n : ℕ) : Set (Matrix (Fin n) (Fin n) ℝ) :=
Matrix.PosSemidef ∩ {X | Matrix.trace X = 1}Definition 7.13
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Definition 7.13: the Schatten 1-norm on the symmetric matrix space 𝕊^n is the sum of the absolute values of the ordered eigenvalues of the matrix.
open scoped BigOperators Matrix
open Matrix
variable {n : ℕ}
local notation "𝕊" => symmetricMatrices n
noncomputable def symmetric_schatten_one_norm (X : 𝕊) : ℝ :=
let hX := X.property.isHermitian
∑ i, |hX.eigenvalues i|
-- Proof sketch: unfold `symmetric_schatten_one_norm`; its defining `let` names the Hermitian
-- structure carried by `X`, after which the statement is the displayed finite sum of absolute
-- eigenvalues.Definition 7.14
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Definition 7.14: a set T ⊆ 𝕊^n is symmetric spectral when its indicator function is the indicator of a permutation symmetric set in ℝ^n composed with the ordered eigenvalue map; such a set C is an associated set.
variable {n : ℕ}
local notation "𝕊" => symmetricMatrices n
def IsSymmetricSpectralSet (T : Set 𝕊) : Prop :=
∃ C : Set (Fin n → ℝ), IsAssociatedSymmetricSpectralSet T C
-- Proof sketch: unfold `IsSymmetricSpectralSet`; the statement is exactly the existential
-- packaging of the associated-set relation introduced just above.Definition 7.15
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Definition 7.15: the singular values function sends a real m × n matrix to the vector in ℝ^(min m n) whose entries are the singular values of the matrix in weakly decreasing order.
open Matrix
variable {m n : ℕ}
noncomputable def singular_value_function (X : Matrix (Fin m) (Fin n) ℝ) : Fin (min m n) → ℝ :=
fun i ↦ X.toEuclideanLin.singularValues i
-- Proof sketch: unfold `singular_value_function`; evaluation at `i` is definitionally the `i`-th
-- entry of the ordered singular-value sequence of the Euclidean linear map associated to `X`.Definition 7.16
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Definition 7.16: the textbook diagonal-matrix construction dg(v) is the canonical mathlib owner Matrix.diagonal, which sends a vector v to the square matrix whose diagonal entries are given by v and whose off-diagonal entries are zero.
recall Matrix.diagonalDefinition 7.17
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Definition 7.17: a real m × n matrix is generalized diagonal if every entry outside the main diagonal vanishes.
namespace Matrix
def IsGeneralizedDiag {m n : ℕ} (X : Matrix (Fin m) (Fin n) ℝ) : Prop :=
∀ i : Fin m, ∀ j : Fin n, (i : ℕ) ≠ (j : ℕ) → X i j = 0
-- Proof sketch: when the matrix is square, `Matrix.IsDiag` is defined by the same off-diagonal
-- vanishing condition. For `Fin n` indices, `i ≠ j` is equivalent to `(i : ℕ) ≠ (j : ℕ)`.Definition 7.18
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Definition 7.18: a proper extended-real-valued function on ℝ^(m × n) is spectral when it factors through the singular-value function via some proper extended-real-valued function on ℝ^(min m n); any such factor is an associated function.
namespace Matrix
variable {m n : ℕ}
class IsSpectralFunction (g : Matrix (Fin m) (Fin n) ℝ → EReal) : Prop
extends IsProperExtendedRealFunction g where
associatedFunction_exists :
∃ f : (Fin (min m n) → ℝ) → EReal,
IsProperExtendedRealFunction f ∧ g = f ∘ singular_value_function
-- Proof sketch: unpack the class definition; it records exactly the properness of `g` together
-- with the existence of a proper associated function on singular-value coordinates whose
-- composition with `singular_value_function` recovers `g`.Definition 7.19
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Definition 7.19: a proper extended-real-valued function on ℝ^(m × n) is symmetric spectral when it is the composition of the singular-value map with some absolutely permutation symmetric proper function on ℝ^(min m n).
open scoped Function
namespace Matrix
variable {m n : ℕ}
class IsSymmetricSpectralFunction (g : Matrix (Fin m) (Fin n) ℝ → EReal) : Prop where
has_absolutely_permutation_symmetric_singular_value_factorization :
HasAbsolutelyPermutationSymmetricSingularValueFactorization gDefinition 7.20
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Definition 7.20: the Schatten p-norm of a real m × n matrix is the ℓ^p norm of its finite singular-value vector.
open Matrix WithLp
open scoped BigOperators Matrix Matrix.Norms.Frobenius
variable {m n : ℕ}
noncomputable def matrix_schatten_norm (p : ENNReal) [Fact (1 ≤ p)]
(X : Matrix (Fin m) (Fin n) ℝ) : ℝ :=
‖toLp p (fun i : Fin (min m n) ↦ X.toEuclideanLin.singularValues i)‖Definition 7.21
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Definition 7.21: the Ky Fan k-norm of a real matrix is the sum of its first k singular values, equivalently the symmetric spectral function associated to the sum of the k largest absolute coordinates of a vector.
open scoped BigOperators Matrix.Norms.L2Operator
open Matrix
variable {r m n : ℕ}
noncomputable def ky_fan_matrix_norm (k : ℕ) (X : Matrix (Fin m) (Fin n) ℝ) : ℝ :=
Finset.sum (Finset.range k) fun i ↦ X.toEuclideanLin.singularValues i
-- Proof sketch: unfold `ky_fan_matrix_norm`; it is defined as the finite sum of the first `k`
-- singular values of `X.toEuclideanLin`.Definition 7.22
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Definition 7.22: a set T ⊆ ℝ^(m × n) is symmetric spectral when its indicator function is the indicator of an absolutely permutation symmetric set in singular-value coordinates composed with the singular-value map; such a set C is an associated set.
namespace Matrix
variable {m n : ℕ}
def IsSymmetricSpectralSet (T : Set (Matrix (Fin m) (Fin n) ℝ)) : Prop :=
∃ C : Set (Fin (min m n) → ℝ), IsAssociatedSymmetricSpectralSet T C
-- Proof sketch: unfold `IsSymmetricSpectralSet`; the statement is exactly the existential
-- packaging of the associated-set relation introduced just above.Definition 7.23
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Definition 7.23: a proper extended-real-valued function on 𝕊^n is a symmetric spectral function when it is the composition of the ordered eigenvalue map with some proper permutation symmetric function on ℝ^n.
open Matrix
variable {n : ℕ}
local notation "𝕊" => symmetricMatrices n
class IsSymmetricSpectralFunction (g : 𝕊 → EReal) : Prop where
has_permutation_symmetric_eigenvalue_factorization :
HasPermutationSymmetricEigenvalueFactorization g