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.

Source header · Attribution source

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 x

Proposition 7.1

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

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.

Source header · Attribution source

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.eigenvalues

Definition 7.2

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

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.Even

Theorem 7.2

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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 ∘ norm

Proposition 7.4

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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 descendingRearrangement

Proposition 7.5

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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] f

Theorem 7.8

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

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 f

Definition 7.9

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.diagonal

Definition 7.17

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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 g

Definition 7.20

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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