matrix_has_psd_factorization
For types m and n, a real matrix M : Matrix m n ℝ has a positive semidefinite (PSD) factorization of size r (for a natural number r) if there exist families of r × r positive semidefinite matrices A : m → Matrix (Fin r) (Fin r) ℝ and B : n → Matrix (Fin r) (Fin r) ℝ such that each A i and B j is positive semidefinite and M i j = Matrix.trace (A i * B j) for all i and j.
Statement
def matrix_has_psd_factorization {m n : Type*} (M : Matrix m n ℝ) (r : ℕ) : Prop
- Defined in
- scout/2610-04498-rank-sensitive-vertex-bounds-for-semidefinite-lifts.md:351
- Verified
- 22 Oct 2026
- Axioms
- none listed
- Used by 14
- matrix_has_psd_factorization_hadamard_selfFor finite types m and n and any real matrix R : Matrix m n ℝ, the Hadamard square Matrix.hadamard R R has a positive semidefinite…
- polygon_psd_vertex_countFor a natural number r, polygon_psd_vertex_count r is the set of natural numbers n such that there exists an n × n real matrix S that is…
- polygon_v2For a natural number r, polygon_v2 r is V₂(r), defined as the supremum of the set of vertex counts of convex polygons in the plane…
- matrix_psd_rank_hadamard_self_le_rankFor finite types m and n and any real matrix M : Matrix m n ℝ, the positive semidefinite rank of the Hadamard square M ∘ M is at most the…
- permutahedron_five_xc_psd_ge_sixThe positive semidefinite rank of the slack matrix of the standard five-element permutahedron is at least 6.
- hexagon_slack_not_psd_factorization_le_threeThe slack matrix of the regular hexagon, the 6×6 circulant matrix with first row (0,0,1,2,2,1) (entry (i,j) = c(j−i mod 6)), has no…
- matrix_has_psd_factorization_submatrixIf a real matrix M has a positive semidefinite factorization of size r, then so does every submatrix M.submatrix f g (rows reindexed by f,…
- polygon_v2_four_eq_eight_iff_no_largerAssuming an 8-gon with size-4 positive semidefinite slack factorization exists and the set of realizable vertex counts is bounded above,…
- matrix_psd_rankFor types m and n, the positive semidefinite rank (psd rank) of a real matrix M : Matrix m n ℝ is the infimum of the set of natural…
- permutahedron_five_not_psd_factorization_six_of_rank_ge_sevenIf the positive semidefinite rank of the slack matrix of the standard five-element permutahedron is at least 7, then the slack matrix has…
- polygon_v2_four_ge_eightIf there exists a convex octagon in the plane admitting a real positive semidefinite slack factorization of size 4, and the set of…
- polygon_psd_vertex_count_ge_threeFor any natural numbers r and n, if n is the vertex count of a convex polygon admitting a size-r positive semidefinite slack…
- matrix_has_psd_factorization_of_nonnegEvery entrywise nonnegative real matrix with finitely many rows m has a positive semidefinite factorization of size |m|: diagonal factors,…
- matrix_has_psd_factorization_restrict_zero_rowFacet restriction lowers the PSD factorization size: if M has a PSD factorization of size r and row i₀ of M is not identically zero, then…
Read back from the Lean
A matrix M : Matrix m n ℝ has a PSD (positive semidefinite) factorization of size r : ℕ if there exist families of r × r real matrices A : m → Matrix (Fin r) (Fin r) ℝ and B : n → Matrix (Fin r) (Fin r) ℝ such that:
1. for every i : m, A i is positive semidefinite;
2. for every j : n, B j is positive semidefinite; and
3. for all i : m and j : n, the entry M i j equals the trace of the product matrix A i * B j.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- A real matrix has a positive semidefinite factorization of size r if its entries can be written as traces of products of r × r positive semidefinite matrices. -/ def matrix_has_psd_factorization {m n : Type*} (M : Matrix m n ℝ) (r : ℕ) : Prop := ∃ (A : m → Matrix (Fin r) (Fin r) ℝ) (B : n → Matrix (Fin r) (Fin r) ℝ), (∀ i, (A i).PosSemidef) ∧ (∀ j, (B j).PosSemidef) ∧ ∀ i j, M i j = Matrix.trace (A i * B j)