matrix_has_psd_factorization_submatrix
If 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, columns by g): keep the factors of the chosen rows and columns.
Statement
theorem matrix_has_psd_factorization_submatrix {m n m' n' : Type*} (M : Matrix m n ℝ) (r : ℕ) (f : m' → m) (g : n' → n) (h : matrix_has_psd_factorization M r) : matrix_has_psd_factorization (M.submatrix f g) r
- Source
- Helper for permutahedron_five_xc_psd_ge_six (arXiv:2610.04498 Sec. 4.2).
- 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 1
- 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
A positive semidefinite factorization of size $r$ expresses each entry $M_{i, j}$ as the trace $\mathrm{tr}(A_i B_j)$ of positive semidefinite matrices. To factor the submatrix formed by selecting rows with $f$ and columns with $g$, we restrict the families to $A \circ f$ and $B \circ g$; these matrices remain positive semidefinite and their pairwise traces match the corresponding submatrix entries.
Obtain the positive semidefinite factors for $M$.
Unpacking the definition of a positive semidefinite factorization from the hypothesis $h$ yields families of $r \times r$ matrices $A_i$ (for $i \in m$) and $B_j$ (for $j \in n$) such that each $A_i$ and $B_j$ is positive semidefinite, and $M_{i, j} = \mathrm{tr}(A_i B_j)$ for all $i$ and $j$.
obtain ⟨A, B, hA, hB, hM⟩ := hThe submatrix $M.\mathrm{submatrix}\; f\; g$ admits a positive semidefinite factorization of size $r$.
We provide the reindexed families $i \mapsto A(f(i))$ and $j \mapsto B(g(j))$ as witnesses. Each $A(f(i))$ is positive semidefinite by the guarantee on $A$, each $B(g(j))$ is positive semidefinite by the guarantee on $B$, and the $(i, j)$ entry of the submatrix is $M_{f(i), g(j)} = \mathrm{tr}(A(f(i)) B(g(j)))$, completing the factorization.
exact ⟨fun i => A (f i), fun j => B (g j), fun i => hA _, fun j => hB _, fun i j => hM _ _⟩
- The entry relation for submatrices, $(M.\mathrm{submatrix}\; f\; g)_{i, j} = M_{f(i), g(j)}$, holds definitionally in Lean, allowing the condition for the submatrix to be discharged by applying $hM$ directly without rewriting.
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_submatrix {m n m' n' : Type*} (M : Matrix m n ℝ) (r : ℕ) (f : m' → m) (g : n' → n) (h : matrix_has_psd_factorization M r) : matrix_has_psd_factorization (M.submatrix f g) r := by obtain ⟨A, B, hA, hB, hM⟩ := h exact ⟨fun i => A (f i), fun j => B (g j), fun i => hA _, fun j => hB _, fun i j => hM _ _⟩