matrix_has_psd_factorization_of_nonneg
Every entrywise nonnegative real matrix with finitely many rows m has a positive semidefinite factorization of size |m|: diagonal factors, A_i the i-th diagonal unit and B_j the diagonal matrix of column j.
Statement
theorem matrix_has_psd_factorization_of_nonneg {m n : Type*} [Fintype m] [DecidableEq m] (M : Matrix m n ℝ) (h : ∀ i j, 0 ≤ M i j) : matrix_has_psd_factorization M (Fintype.card m)
- Source
- Helper for permutahedron_five_xc_psd_ge_six (arXiv:2610.04498 Sec. 4.2): it makes the set in the PSD-rank infimum nonempty.
- Verified
- 24 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- matrix_has_psd_factorizationFor 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…
- Used by 2
- matrix_trace_unitaryGroup_oneThe trace of the identity unitary matrix indexed by a finite type n equals the cardinality of n.
- permutahedron_five_xc_psd_ge_sixThe positive semidefinite rank of the slack matrix of the standard five-element permutahedron is at least 6.
The proof, explained
To show that every entrywise nonnegative real matrix M with row index type m admits a positive semidefinite factorization of size |m|, we fix an identification e : m ≃ Fin |m| and construct diagonal matrix factors. For each row i, the factor A_i is the diagonal matrix with 1 at index e(i) and 0 elsewhere; for each column j, the factor B_j is the diagonal matrix whose entries are column j of M. Both factors are positive semidefinite because their diagonal entries are nonnegative, and the trace of their product picks out exactly M i j.
Candidate families of matrices A_i and B_j of size |m| × |m| are defined, reducing the proof to three subgoals: positive semidefiniteness of each A_i, positive semidefiniteness of each B_j, and the factorization trace identity.
Working in classical logic, we fix an identification e : m ≃ Fin |m| between row indices and the standard finite set {0, ..., |m| - 1}. We propose diagonal witness matrices: for each row i, A_i has diagonal entry 1 at index e(i) and 0 elsewhere; for each column j, B_j is the diagonal matrix whose k-th diagonal entry is M (e.symm k) j. The refine tactic leaves three obligations: that each A_i is positive semidefinite, that each B_j is positive semidefinite, and that tr(A_i * B_j) = M i j.
uses
Fintype.equivFin,Matrix.diagonalclassical let e := Fintype.equivFin m refine ⟨fun i => Matrix.diagonal (fun k => if k = e i then 1 else 0), fun j => Matrix.diagonal (fun k => M (e.symm k) j), ?_, ?_, ?_⟩
For every row index i, the matrix A_i is positive semidefinite.
A diagonal matrix is positive semidefinite provided its diagonal entries are nonnegative (Matrix.PosSemidef.diagonal). For each index k, the diagonal entry is 1 if k = e(i) and 0 otherwise. A case split on k = e(i) followed by numerical evaluation (norm_num) verifies that the entry is nonnegative in both cases.
uses
Matrix.PosSemidef.diagonal· intro i exact Matrix.PosSemidef.diagonal (fun k => by split_ifs <;> norm_num)
For every column index j, the matrix B_j is positive semidefinite.
By Matrix.PosSemidef.diagonal, B_j is positive semidefinite because its k-th diagonal entry is M (e.symm k) j, which is nonnegative by the assumption that every entry of M is nonnegative.
uses
Matrix.PosSemidef.diagonal· intro j exact Matrix.PosSemidef.diagonal (fun k => h _ _)
For all indices i and j, the trace of A_i * B_j equals M i j.
The product of two diagonal matrices is the diagonal matrix of their pointwise product (Matrix.diagonal_mul_diagonal), and the trace of a diagonal matrix is the sum of its diagonal entries (Matrix.trace_diagonal). This expresses tr(A_i * B_j) as the sum over k of (if k = e(i) then 1 else 0) * M (e.symm k) j. The simplifier (simp) evaluates this sum: all terms with k ≠ e(i) are 0, and the single term at k = e(i) simplifies to M i j.
uses
Matrix.diagonal_mul_diagonal,Matrix.trace_diagonal· intro i j rw [Matrix.diagonal_mul_diagonal, Matrix.trace_diagonal] simp
Fintype.equivFin- A canonical bijection between any finite type α and Fin |α|.
Matrix.diagonal- The square diagonal matrix whose diagonal entries are given by a specified function and whose off-diagonal entries are zero.
Matrix.PosSemidef.diagonal- A diagonal matrix whose diagonal entries are all nonnegative is positive semidefinite.
Matrix.diagonal_mul_diagonal- The product of two diagonal matrices is the diagonal matrix formed by their pointwise entrywise product.
Matrix.trace_diagonal- The trace of a diagonal matrix is the sum of its diagonal entries.
- In line 14, simp collapses the sum ∑ k, (if k = e i then 1 else 0) * M (e.symm k) j to the single nonvanishing term at k = e i and simplifies e.symm (e i) to i using lemmas for sums of indicator functions and inverse equivalence cancellation.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
theorem matrix_has_psd_factorization_of_nonneg {m n : Type*} [Fintype m] [DecidableEq m] (M : Matrix m n ℝ) (h : ∀ i j, 0 ≤ M i j) : matrix_has_psd_factorization M (Fintype.card m) := by classical let e := Fintype.equivFin m refine ⟨fun i => Matrix.diagonal (fun k => if k = e i then 1 else 0), fun j => Matrix.diagonal (fun k => M (e.symm k) j), ?_, ?_, ?_⟩ · intro i exact Matrix.PosSemidef.diagonal (fun k => by split_ifs <;> norm_num) · intro j exact Matrix.PosSemidef.diagonal (fun k => h _ _) · intro i j rw [Matrix.diagonal_mul_diagonal, Matrix.trace_diagonal] simp