matrix_has_psd_factorization_restrict_zero_row
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
- 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
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.
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.
uses
sub_zero,CFC.exists_sqrt_of_isSelfAdjoint_of_quasispectrumRestricts,QuasispectrumRestricts.nnreal_of_nonnegopen 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]⟩
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.
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
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.
uses
congrFunobtain ⟨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
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.
uses
dotProduct_add,dotProduct_smul,LinearMap.congr_fun,dotProduct_self_eq_zero.1let φ : 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)
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.
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.finBasisOfFinrankEqset 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
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 φ.
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_congrhave 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
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.
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_assoclet 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
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.
uses
Matrix.posSemidef_conjTranspose_mul_self,Matrix.submatrix_apply,id,Matrix.mul_assoc,Matrix.trace_mul_commrefine ⟨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)
- The file begins with a helper lemma matrix_pos_semidef_real_exists_gram showing that every real positive semidefinite matrix admits a Gram factorization B = Gᵀ G via continuous functional calculus, which is then used in the main theorem.
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_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]