AFTD Auto-Formalizing Theoretical Domains

matrix_has_psd_factorization_restrict_zero_row

theoremverifiedformalization

Facet 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 the submatrix of M on the columns where row i₀ vanishes (all rows kept) has a PSD factorization of size r − 1. For a slack matrix and i₀ a facet, this is the facet case of the face inequality xc_PSD(P) ≥ xc_PSD(F) + dim P − dim F.

Statement

theorem matrix_has_psd_factorization_restrict_zero_row {m n : Type*} (M : Matrix m n ℝ) (r : ℕ)
    (h : matrix_has_psd_factorization M r) (i₀ : m) (j₀ : n) (hj₀ : M i₀ j₀ ≠ 0) :
    matrix_has_psd_factorization (M.submatrix id (Subtype.val : {j // M i₀ j = 0} → n)) (r - 1)
Formalizes
arXiv:2610.04498 Lemma 2.2 (facet case, in slack-matrix form)
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

The proof first establishes that any real PSD matrix admits a Gram factorization B = Gᵀ G via continuous functional calculus. Given a PSD factorization M i j = tr(A i B j) of size r and a non-zero row i₀ with A₀ = A i₀ ≠ 0, we select a non-zero column u of A₀ and define the hyperplane H = ker(x ↦ u ⬝ᵥ x) of dimension r - 1. For any column j where M i₀ j = 0, the trace identity tr(A₀ B j) = 0 forces the rows of the Gram factor G of B j to satisfy A₀ G_{k'} = 0, placing every row in H. Expanding each row of G in a basis matrix U for H yields B j = U (Y j)ᵀ (Y j) Uᵀ, and compressing the factors via U provides a PSD factorization of size r - 1 for the restricted submatrix.

  1. Every real positive semidefinite matrix B has a Gram factorization B = Gᵀ G for some matrix G.

    Because B is positive semidefinite, it is Hermitian (symmetric) and its spectrum is non-negative. Continuous functional calculus provides a self-adjoint square root X such that X * X = B. Since Xᵀ = X, taking G = X gives B = Xᵀ X = Gᵀ G.

    lines 3–8

    uses sub_zero, CFC.exists_sqrt_of_isSelfAdjoint_of_quasispectrumRestricts, QuasispectrumRestricts.nnreal_of_nonneg

      open scoped MatrixOrder in
      obtain ⟨X, hX, -, hXB⟩ :=
        sub_zero B ▸ CFC.exists_sqrt_of_isSelfAdjoint_of_quasispectrumRestricts hB.isHermitian
          (QuasispectrumRestricts.nnreal_of_nonneg hB.nonneg)
      have hXX : X.conjTranspose = X := hX
      exact ⟨X, by rw [hXX, hXB, sub_zero]⟩
  2. The PSD matrix A₀ = A i₀ associated with row i₀ is non-zero.

    We unpack the assumed PSD factorization M_{i,j} = tr(A_i B_j) and set A₀ = A i₀. If A₀ were zero, then M i₀ j₀ = tr(0 · B j₀) = 0, which contradicts the hypothesis hj₀ that M i₀ j₀ ≠ 0.

    lines 13–17

      classical
      obtain ⟨A, B, hA, hB, hM⟩ := h
      set A₀ := A i₀ with hA₀def
      have hA₀ : A₀ ≠ 0 := by
        intro h0; apply hj₀; rw [hM, ← hA₀def, h0]; simp
  3. There exists a column index k such that the k-th column of A₀, denoted u, is non-zero.

    Since A₀ is non-zero, not all of its columns can vanish. We pick an index k where the column u = (A₀)_{*, k} is non-zero.

    lines 18–24

    uses congrFun

      obtain ⟨k, hk⟩ : ∃ k, (fun l => A₀ l k) ≠ 0 := by
        by_contra hcon
        push Not at hcon
        apply hA₀
        ext l k'
        exact congrFun (hcon k') l
      set u : Fin r → ℝ := fun l => A₀ l k with hudef
  4. The linear form φ(x) = u ⬝ᵥ x on ℝ^r is non-zero.

    Taking the dot product with u defines a linear functional φ. If φ were zero, then φ(u) = u ⬝ᵥ u = 0, which implies u = 0, contradicting that u is non-zero.

    lines 25–34

    uses dotProduct_add, dotProduct_smul, LinearMap.congr_fun, dotProduct_self_eq_zero.1

      let φ : Module.Dual ℝ (Fin r → ℝ) :=
        { toFun := fun x => u ⬝ᵥ x
          map_add' := fun x y => dotProduct_add u x y
          map_smul' := fun c x => by simp [dotProduct_smul] }
      have hφ : φ ≠ 0 := by
        intro h0
        have h1 : u ⬝ᵥ u = 0 := by
          have := LinearMap.congr_fun h0 u
          simpa [φ] using this
        exact hk (dotProduct_self_eq_zero.1 h1)
  5. The hyperplane H = ker φ has dimension r - 1, and its basis forms an r × (r - 1) matrix U.

    Because φ is a non-zero linear form on ℝ^r, its kernel H has codimension 1, hence dimension r - 1. We choose a basis bH of H and arrange these vectors as the columns of an r × (r - 1) matrix U.

    lines 35–42

    uses Module.Dual.finrank_ker_add_one_of_ne_zero, Module.finrank_fintype_fun_eq_card, Fintype.card_fin, Nat.eq_sub_of_add_eq, Module.finBasisOfFinrankEq

      set H := LinearMap.ker φ
      have hfin : Module.finrank ℝ H = r - 1 := by
        have := Module.Dual.finrank_ker_add_one_of_ne_zero hφ
        rw [Module.finrank_fintype_fun_eq_card, Fintype.card_fin] at this
        exact Nat.eq_sub_of_add_eq this
      let bH : Module.Basis (Fin (r - 1)) ℝ H := Module.finBasisOfFinrankEq ℝ H hfin
      let U : Matrix (Fin r) (Fin (r - 1)) ℝ := fun l c => (bH c : Fin r → ℝ) l
      -- rows of a Gram factor of each B j in the zero set lie in H
  6. For each column j with M i₀ j = 0, every row of a Gram factor G of B j lies in H.

    Using matrix_pos_semidef_real_exists_gram, factor B j = Gᵀ G. The condition M i₀ j = 0 translates to tr(A₀ Gᵀ G) = tr(G A₀ Gᵀ) = 0. Since A₀ is positive semidefinite, G A₀ Gᵀ is also positive semidefinite, so its diagonal entries are non-negative. A sum of non-negative numbers vanishing implies each diagonal entry is zero: (G A₀ Gᵀ)_{k', k'} = (G_{k'})ᵀ A₀ (G_{k'}) = 0. By positive semidefiniteness of A₀, this implies A₀ (G_{k'}) = 0. Taking the k-th entry gives u ⬝ᵥ G_{k'} = 0, so every row G_{k'} belongs to H = ker φ.

    lines 43–79

    uses matrix_pos_semidef_real_exists_gram, congrFun, Matrix.conjTranspose_apply, Matrix.mul_assoc, Matrix.trace_mul_cycle, Matrix.conjTranspose_conjTranspose, Finset.sum_eq_zero_iff_of_nonneg, Finset.mem_univ, Matrix.mul_apply, Matrix.mulVec, dotProduct, Finset.mul_sum, mul_comm, mul_left_comm, Finset.sum_congr

      have hrow : ∀ j : {j // M i₀ j = 0}, ∃ Y : Matrix (Fin r) (Fin (r - 1)) ℝ,
          B j.1 = U * (Y.conjTranspose * Y) * U.conjTranspose := by
        intro j
        obtain ⟨G, hG⟩ := matrix_pos_semidef_real_exists_gram (B j.1) (hB j.1)
        have hsym : ∀ a b, A₀ a b = A₀ b a := by
          intro a b
          have := congrFun (congrFun (hA i₀).1 a) b
          simp [Matrix.conjTranspose_apply] at this
          first | exact this | exact this.symm
        have hmem : ∀ k', G k' ∈ H := by
          have h0 : (A₀ * (G.conjTranspose * G)).trace = 0 := by
            rw [← hG, ← hM]; exact j.2
          rw [← Matrix.mul_assoc, Matrix.trace_mul_cycle] at h0
          have hnn : ∀ k', 0 ≤ (G * A₀ * G.conjTranspose) k' k' := by
            intro k'
            have := (hA i₀).conjTranspose_mul_mul_same G.conjTranspose
            rw [Matrix.conjTranspose_conjTranspose] at this
            exact this.diag_nonneg
          have hz : ∀ k', (G * A₀ * G.conjTranspose) k' k' = 0 := by
            intro k'
            have := (Finset.sum_eq_zero_iff_of_nonneg (fun k'' _ => hnn k'')).1 h0 k' (Finset.mem_univ _)
            exact this
          intro k'
          have hq : star (G k') ⬝ᵥ Matrix.mulVec A₀ (G k') = 0 := by
            rw [← hz k']
            simp [Matrix.mul_apply, Matrix.mulVec, dotProduct, Finset.mul_sum,
              mul_comm, mul_left_comm]
            exact Finset.sum_congr rfl (fun _ _ => Finset.sum_congr rfl (fun _ _ => by rw [hsym]))
          have hv := ((hA i₀).dotProduct_mulVec_zero_iff (G k')).1 hq
          show u ⬝ᵥ G k' = 0
          have hsymm : ∀ l, A₀ l k = A₀ k l := by
            intro l
            have := congrFun (congrFun (hA i₀).1 k) l
            simp [Matrix.conjTranspose_apply] at this
            first | exact this | exact this.symm
          have := congrFun hv k
          simpa [hudef, hsymm, Matrix.mulVec, dotProduct] using this
  7. For each column j with M i₀ j = 0, B j factors through U as U (Y j)ᵀ (Y j) Uᵀ for some matrix Y j.

    Because each row of G lies in H, we can expand each row in the basis bH, yielding a matrix Y such that G = Y Uᵀ. Then B j = Gᵀ G = (Y Uᵀ)ᵀ (Y Uᵀ) = U (Yᵀ Y) Uᵀ. Using the axiom of choice (choose), we obtain such a matrix Y j for every j where row i₀ vanishes.

    lines 80–92

    uses congrArg, Submodule.coe_sum, Submodule.coe_smul, Finset.sum_apply, Pi.smul_apply, smul_eq_mul, Matrix.mul_apply, Finset.sum_congr, Matrix.conjTranspose_mul, Matrix.conjTranspose_conjTranspose, Matrix.mul_assoc

        let Y : Matrix (Fin r) (Fin (r - 1)) ℝ := fun k' c => bH.repr ⟨G k', hmem k'⟩ c
        have hGY : G = Y * U.conjTranspose := by
          ext k' l
          have := bH.sum_repr ⟨G k', hmem k'⟩
          have h2 := congrArg (fun x : H => (x : Fin r → ℝ) l) this
          simp only [Submodule.coe_sum, Submodule.coe_smul, Finset.sum_apply, Pi.smul_apply,
            smul_eq_mul] at h2
          rw [← h2, Matrix.mul_apply]
          exact Finset.sum_congr rfl (fun _ _ => rfl)
        refine ⟨Y, ?_⟩
        rw [hG, hGY, Matrix.conjTranspose_mul, Matrix.conjTranspose_conjTranspose]
        simp only [Matrix.mul_assoc]
      choose Y hY using hrow
  8. The restricted submatrix has a PSD factorization of size r - 1 given by Uᵀ (A i) U and (Y j)ᵀ (Y j).

    We define the new factors of size r - 1: A' i = Uᵀ (A i) U and B' j = (Y j)ᵀ (Y j). Both are positive semidefinite: A' i by congruence with U, and B' j as a Gram matrix. For every row i and column j in the zero set of row i₀, tr(A' i B' j) = tr(Uᵀ (A i) U (Y j)ᵀ (Y j)) = tr(A i U (Y j)ᵀ (Y j) Uᵀ) by trace cyclicity, which equals tr(A i B j) = M i j.

    lines 93–101

    uses Matrix.posSemidef_conjTranspose_mul_self, Matrix.submatrix_apply, id, Matrix.mul_assoc, Matrix.trace_mul_comm

      refine ⟨fun i => U.conjTranspose * A i * U, fun j => (Y j).conjTranspose * Y j,
        fun i => (hA i).conjTranspose_mul_mul_same U, fun j => Matrix.posSemidef_conjTranspose_mul_self _, ?_⟩
      intro i j
      simp only [Matrix.submatrix_apply, id]
      rw [hM, hY j]
      rw [show A i * (U * ((Y j).conjTranspose * Y j) * U.conjTranspose) = (A i * U * ((Y j).conjTranspose * Y j)) * U.conjTranspose by
        simp only [Matrix.mul_assoc]]
      rw [Matrix.trace_mul_comm]
      simp only [Matrix.mul_assoc]
sub_zero
subtracting zero leaves an element unchanged: a - 0 = a
CFC.exists_sqrt_of_isSelfAdjoint_of_quasispectrumRestricts
a self-adjoint element with non-negative spectrum has a self-adjoint square root via continuous functional calculus
QuasispectrumRestricts.nnreal_of_nonneg
a non-negative element has its quasispectrum restricted to non-negative real numbers
congrFun
equal functions take equal values on equal inputs
dotProduct_add
the dot product distributes over vector addition: u ⬝ᵥ (v + w) = u ⬝ᵥ v + u ⬝ᵥ w
dotProduct_smul
scalar multiplication pulls out of the second argument of the dot product: u ⬝ᵥ (c • x) = c (u ⬝ᵥ x)
LinearMap.congr_fun
equal linear maps agree on every input vector
dotProduct_self_eq_zero.1
for a real vector u, u ⬝ᵥ u = 0 implies u = 0
Module.Dual.finrank_ker_add_one_of_ne_zero
the kernel of a non-zero linear form on a finite-dimensional space has codimension 1, so dim(ker φ) + 1 = dim(V)
Module.finrank_fintype_fun_eq_card
the dimension of the space of functions from a finite type η to a field is the cardinality |η|
Fintype.card_fin
the cardinality of Fin n is n
Nat.eq_sub_of_add_eq
if c + b = a in ℕ, then c = a - b
Module.finBasisOfFinrankEq
a finite-dimensional vector space of dimension n has a basis indexed by Fin n
matrix_pos_semidef_real_exists_gram
every real positive semidefinite matrix B can be factored as B = Gᵀ G for some matrix G
Matrix.conjTranspose_apply
the conjugate transpose of a matrix has entries (M*)_{j,i} = (M_{i,j})*
Matrix.trace_mul_cycle
the trace is invariant under cyclic permutation of three matrices: tr(A B C) = tr(C A B)
Matrix.mul_assoc
matrix multiplication is associative: (A B) C = A (B C)
Matrix.conjTranspose_conjTranspose
taking conjugate transpose twice returns the original matrix: (M*)* = M
Finset.sum_eq_zero_iff_of_nonneg
a sum of non-negative numbers is zero if and only if each term is zero
Finset.mem_univ
every element of a finite type belongs to its universal finset
Matrix.mul_apply
the (i, k)-entry of a matrix product M N is ∑ⱼ M_{i,j} N_{j,k}
Matrix.mulVec
the matrix-vector product (M x)ᵢ is ∑ⱼ M_{i,j} xⱼ
dotProduct
the dot product of two vectors is the sum of the products of their coordinates
Finset.mul_sum
multiplication distributes over a finite sum: a ∑ᵢ fᵢ = ∑ᵢ a fᵢ
mul_comm
multiplication of real numbers is commutative: a b = b a
mul_left_comm
multiplication satisfies the left-commutative law: a (b c) = b (a c)
Finset.sum_congr
sums of pointwise equal terms over equal index sets are equal
congrArg
applying a function to equal arguments produces equal values
Submodule.coe_sum
the canonical coercion from a submodule preserves finite sums
Submodule.coe_smul
the canonical coercion from a submodule preserves scalar multiplication
Finset.sum_apply
evaluating a sum of functions at a point equals the sum of their values at that point
Pi.smul_apply
evaluating a scalar multiple of a function at a point scales the value at that point
smul_eq_mul
scalar multiplication on the real field agrees with standard multiplication
Matrix.conjTranspose_mul
the conjugate transpose of a product reverses order: (M N)* = N* M*
Matrix.posSemidef_conjTranspose_mul_self
for any matrix A, the Gram matrix A* A is positive semidefinite
Matrix.submatrix_apply
the submatrix entries are given by evaluating the original matrix at the chosen row and column indices
id
the identity function returns its input unchanged
Matrix.trace_mul_comm
the trace of a product of two matrices is commutative: tr(A B) = tr(B A)

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_pos_semidef_real_exists_gram {r : ℕ} (B : Matrix (Fin r) (Fin r) ℝ)    (hB : B.PosSemidef) : ∃ G : Matrix (Fin r) (Fin r) ℝ, B = G.conjTranspose * G := by  open scoped MatrixOrder in  obtain ⟨X, hX, -, hXB⟩ :=    sub_zero B ▸ CFC.exists_sqrt_of_isSelfAdjoint_of_quasispectrumRestricts hB.isHermitian      (QuasispectrumRestricts.nnreal_of_nonneg hB.nonneg)  have hXX : X.conjTranspose = X := hX  exact ⟨X, by rw [hXX, hXB, sub_zero]⟩theorem matrix_has_psd_factorization_restrict_zero_row {m n : Type*} (M : Matrix m n ℝ) (r : ℕ)    (h : matrix_has_psd_factorization M r) (i₀ : m) (j₀ : n) (hj₀ : M i₀ j₀ ≠ 0) :    matrix_has_psd_factorization (M.submatrix id (Subtype.val : {j // M i₀ j = 0} → n)) (r - 1) := by  classical  obtain ⟨A, B, hA, hB, hM⟩ := h  set A₀ := A i₀ with hA₀def  have hA₀ : A₀ ≠ 0 := by    intro h0; apply hj₀; rw [hM, ← hA₀def, h0]; simp  obtain ⟨k, hk⟩ : ∃ k, (fun l => A₀ l k) ≠ 0 := by    by_contra hcon    push Not at hcon    apply hA₀    ext l k'    exact congrFun (hcon k') l  set u : Fin r → ℝ := fun l => A₀ l k with hudef  let φ : Module.Dual ℝ (Fin r → ℝ) :=    { toFun := fun x => u ⬝ᵥ x      map_add' := fun x y => dotProduct_add u x y      map_smul' := fun c x => by simp [dotProduct_smul] }  have hφ : φ ≠ 0 := by    intro h0    have h1 : u ⬝ᵥ u = 0 := by      have := LinearMap.congr_fun h0 u      simpa [φ] using this    exact hk (dotProduct_self_eq_zero.1 h1)  set H := LinearMap.ker φ  have hfin : Module.finrank ℝ H = r - 1 := by    have := Module.Dual.finrank_ker_add_one_of_ne_zero hφ    rw [Module.finrank_fintype_fun_eq_card, Fintype.card_fin] at this    exact Nat.eq_sub_of_add_eq this  let bH : Module.Basis (Fin (r - 1)) ℝ H := Module.finBasisOfFinrankEq ℝ H hfin  let U : Matrix (Fin r) (Fin (r - 1)) ℝ := fun l c => (bH c : Fin r → ℝ) l  -- rows of a Gram factor of each B j in the zero set lie in H  have hrow : ∀ j : {j // M i₀ j = 0}, ∃ Y : Matrix (Fin r) (Fin (r - 1)) ℝ,      B j.1 = U * (Y.conjTranspose * Y) * U.conjTranspose := by    intro j    obtain ⟨G, hG⟩ := matrix_pos_semidef_real_exists_gram (B j.1) (hB j.1)    have hsym : ∀ a b, A₀ a b = A₀ b a := by      intro a b      have := congrFun (congrFun (hA i₀).1 a) b      simp [Matrix.conjTranspose_apply] at this      first | exact this | exact this.symm    have hmem : ∀ k', G k' ∈ H := by      have h0 : (A₀ * (G.conjTranspose * G)).trace = 0 := by        rw [← hG, ← hM]; exact j.2      rw [← Matrix.mul_assoc, Matrix.trace_mul_cycle] at h0      have hnn : ∀ k', 0 ≤ (G * A₀ * G.conjTranspose) k' k' := by        intro k'        have := (hA i₀).conjTranspose_mul_mul_same G.conjTranspose        rw [Matrix.conjTranspose_conjTranspose] at this        exact this.diag_nonneg      have hz : ∀ k', (G * A₀ * G.conjTranspose) k' k' = 0 := by        intro k'        have := (Finset.sum_eq_zero_iff_of_nonneg (fun k'' _ => hnn k'')).1 h0 k' (Finset.mem_univ _)        exact this      intro k'      have hq : star (G k') ⬝ᵥ Matrix.mulVec A₀ (G k') = 0 := by        rw [← hz k']        simp [Matrix.mul_apply, Matrix.mulVec, dotProduct, Finset.mul_sum,          mul_comm, mul_left_comm]        exact Finset.sum_congr rfl (fun _ _ => Finset.sum_congr rfl (fun _ _ => by rw [hsym]))      have hv := ((hA i₀).dotProduct_mulVec_zero_iff (G k')).1 hq      show u ⬝ᵥ G k' = 0      have hsymm : ∀ l, A₀ l k = A₀ k l := by        intro l        have := congrFun (congrFun (hA i₀).1 k) l        simp [Matrix.conjTranspose_apply] at this        first | exact this | exact this.symm      have := congrFun hv k      simpa [hudef, hsymm, Matrix.mulVec, dotProduct] using this    let Y : Matrix (Fin r) (Fin (r - 1)) ℝ := fun k' c => bH.repr ⟨G k', hmem k'⟩ c    have hGY : G = Y * U.conjTranspose := by      ext k' l      have := bH.sum_repr ⟨G k', hmem k'⟩      have h2 := congrArg (fun x : H => (x : Fin r → ℝ) l) this      simp only [Submodule.coe_sum, Submodule.coe_smul, Finset.sum_apply, Pi.smul_apply,        smul_eq_mul] at h2      rw [← h2, Matrix.mul_apply]      exact Finset.sum_congr rfl (fun _ _ => rfl)    refine ⟨Y, ?_⟩    rw [hG, hGY, Matrix.conjTranspose_mul, Matrix.conjTranspose_conjTranspose]    simp only [Matrix.mul_assoc]  choose Y hY using hrow  refine ⟨fun i => U.conjTranspose * A i * U, fun j => (Y j).conjTranspose * Y j,    fun i => (hA i).conjTranspose_mul_mul_same U, fun j => Matrix.posSemidef_conjTranspose_mul_self _, ?_⟩  intro i j  simp only [Matrix.submatrix_apply, id]  rw [hM, hY j]  rw [show A i * (U * ((Y j).conjTranspose * Y j) * U.conjTranspose) = (A i * U * ((Y j).conjTranspose * Y j)) * U.conjTranspose by    simp only [Matrix.mul_assoc]]  rw [Matrix.trace_mul_comm]  simp only [Matrix.mul_assoc]
See it in the graphDiscuss this resultChallenge it