AFTD Auto-Formalizing Theoretical Domains

matrix_has_psd_factorization_submatrix

theoremverified

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

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.

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

    line 4

      obtain ⟨A, B, hA, hB, hM⟩ := h
  2. The 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.

    line 5

      exact ⟨fun i => A (f i), fun j => B (g j), fun i => hA _, fun j => hB _, fun i j => hM _ _⟩

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