AFTD Auto-Formalizing Theoretical Domains

matrix_has_psd_factorization_of_nonneg

theoremverified

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

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.

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

    lines 4–7

    uses Fintype.equivFin, Matrix.diagonal

      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), ?_, ?_, ?_⟩
  2. 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.

    lines 8–9

    uses Matrix.PosSemidef.diagonal

      · intro i
        exact Matrix.PosSemidef.diagonal (fun k => by split_ifs <;> norm_num)
  3. 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.

    lines 10–11

    uses Matrix.PosSemidef.diagonal

      · intro j
        exact Matrix.PosSemidef.diagonal (fun k => h _ _)
  4. 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.

    lines 12–14

    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.

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

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
See it in the graphDiscuss this resultChallenge it