matrix_psd_rank_hadamard_self_le_rank
For finite types m and n and any real matrix M : Matrix m n ℝ, the positive semidefinite rank of the Hadamard square M ∘ M is at most the ordinary rank of M.
Statement
theorem matrix_psd_rank_hadamard_self_le_rank {m n : Type*} [Fintype m] [Fintype n] (M : Matrix m n ℝ) : matrix_psd_rank (Matrix.hadamard M M) ≤ Matrix.rank M
- Source
- scout/2610-04498-rank-sensitive-vertex-bounds-for-semidefinite-lifts.md:368
- Verified
- 23 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- matrix_psd_rankFor types m and n, the positive semidefinite rank (psd rank) of a real matrix M : Matrix m n ℝ is the infimum of the set of natural…
- 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
- matrix_support_psd_rank_bound_le_rankFor finite types m and n, let b : Set (m × n) → ℝ be a function on support patterns such that b (matrix_support M) ≤ (matrix_psd_rank M :…
- matrix_psd_rank_le_rank_of_hadamard_eqFor finite types m and n, if M is an entrywise nonnegative real matrix (∀ i j, 0 ≤ M i j) and R is a real matrix such that M =…
Read back from the Lean
For all finite types m and n, and every real matrix M of size m × n, the PSD rank of the Hadamard product M ∘ M (the entrywise product of M with itself) is less than or equal to the rank of M.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The positive semidefinite (PSD) rank of a matrix is the minimal dimension r of a PSD factorization M_ij = tr(A_i B_j). To show that the Hadamard square M ∘ M has PSD rank at most rank M, the proof factors M = U V with inner dimension r = rank M using a basis of the column space of M. Setting A_i = u_i u_iᵀ and B_j = v_j v_jᵀ gives rank-one PSD matrices whose trace product tr(A_i B_j) = (u_i · v_j)² = M_ij² reproduces the Hadamard square.
It suffices to construct a positive semidefinite (PSD) factorization of M ∘ M of size r = rank M.
The positive semidefinite rank is defined as the infimum of the sizes r of PSD factorizations of M ∘ M. By `Nat.sInf_le`, showing that rank M admits such a factorization directly bounds the infimum by rank M.
uses
Nat.sInf_leclassical apply Nat.sInf_le change matrix_has_psd_factorization (Matrix.hadamard M M) (Matrix.rank M) dsimp [matrix_has_psd_factorization]
Choose a basis for the column space of M and define factors U of size m × r and V of size r × n.
Let r = rank M. By `Module.finBasisOfFinrankEq`, the range of the linear map M (its column space) has a basis b indexed by Fin r. Each column j of M lies in this space because multiplying M by the j-th standard unit vector yields the j-th column (`Matrix.mulVec_single_one`). Let U be the matrix whose columns are the basis vectors, and let V be the matrix whose j-th column contains the coordinates of column j of M in basis b.
uses
Module.finBasisOfFinrankEq,Matrix.mulVec_single_onelet r := Matrix.rank M let b : Module.Basis (Fin r) ℝ M.mulVecLin.range := Module.finBasisOfFinrankEq ℝ M.mulVecLin.range rfl have hj (j : n) : (fun i => M i j) ∈ M.mulVecLin.range := ⟨Pi.single j 1, Matrix.mulVec_single_one M j⟩ let U : Matrix m (Fin r) ℝ := fun i k => (b k : m → ℝ) i let V : Matrix (Fin r) n ℝ := fun k j => b.repr ⟨fun i => M i j, hj j⟩ k
The matrix M factors as M = U * V.
By `Module.Basis.sum_repr`, column j of M is the linear combination ∑_k V_kj b_k. Evaluating this identity at entry i yields M_ij = ∑_k U_ik V_kj, which is the definition of the matrix product (U * V)_ij (`Matrix.mul_apply`).
uses
Module.Basis.sum_repr,congr_arg,congr_fun,Submodule.coe_sum,Submodule.coe_smul,Finset.sum_apply,Pi.smul_apply,smul_eq_mul,Matrix.mul_apply,Finset.sum_congr,mul_commhave hM : M = U * V := by ext i j have h := Module.Basis.sum_repr b ⟨fun i => M i j, hj j⟩ have h_val := congr_arg Subtype.val h have h_eval := congr_fun h_val i simp only [Submodule.coe_sum, Submodule.coe_smul, Finset.sum_apply, Pi.smul_apply, smul_eq_mul] at h_eval rw [Matrix.mul_apply] rw [← h_eval] apply Finset.sum_congr rfl intro k _ simp [U, V, mul_comm]
Define candidate matrices A_i = u_i u_iᵀ and B_j = v_j v_jᵀ, reducing the goal to three subgoals.
For each row i of U, let A_i be the outer product of the row vector with itself. For each column j of V, let B_j be the outer product of the column vector with itself. Providing A and B as witnesses reduces the goal to proving: each A_i is positive semidefinite, each B_j is positive semidefinite, and tr(A_i B_j) = M_ij².
let A (i : m) : Matrix (Fin r) (Fin r) ℝ := Matrix.vecMulVec (U i) (U i) let B (j : n) : Matrix (Fin r) (Fin r) ℝ := Matrix.vecMulVec (fun k => V k j) (fun k => V k j) refine ⟨A, B, ?_, ?_, ?_⟩
Each matrix A_i is positive semidefinite.
As the outer product of a real vector with itself, A_i is positive semidefinite by `Matrix.posSemidef_vecMulVec_self_star`, using `star_trivial` since the conjugate transpose on real numbers is simply the transpose.
uses
Matrix.posSemidef_vecMulVec_self_star,star_trivial· intro i have := Matrix.posSemidef_vecMulVec_self_star (U i) rwa [star_trivial] at this
Each matrix B_j is positive semidefinite.
Similarly, each B_j is the outer product of a real column vector with itself, and is positive semidefinite by `Matrix.posSemidef_vecMulVec_self_star` and `star_trivial`.
uses
Matrix.posSemidef_vecMulVec_self_star,star_trivial· intro j have := Matrix.posSemidef_vecMulVec_self_star (fun k => V k j) rwa [star_trivial] at this
For each i and j, the trace of A_i * B_j equals (u_i · v_j)².
By `Matrix.vecMulVec_mul_vecMulVec`, the product of the two rank-one matrices A_i and B_j is (u_i · v_j) (u_i v_jᵀ). Taking the trace using `Matrix.trace_vecMulVec` and pulling out the scalar using `dotProduct_smul` evaluates tr(A_i B_j) to (u_i · v_j)².
uses
Matrix.vecMulVec_mul_vecMulVec,Matrix.trace_vecMulVec,dotProduct_smul· intro i j have h_tr : (A i * B j).trace = ((U i) ⬝ᵥ (fun k => V k j)) ^ 2 := by dsimp [A, B] rw [Matrix.vecMulVec_mul_vecMulVec] rw [Matrix.trace_vecMulVec] rw [dotProduct_smul] ring rw [h_tr]
The dot product u_i · v_j equals M_ij, completing the verification of the PSD factorization.
Since M = U * V, the (i, j)-th entry M_ij equals the dot product of the i-th row of U and the j-th column of V by `Matrix.mul_apply`. Substituting this into the trace identity gives tr(A_i B_j) = M_ij² = (M ∘ M)_ij.
uses
congr_fun,Matrix.mul_applyhave h_dot : (U i) ⬝ᵥ (fun k => V k j) = M i j := by rw [congr_fun (congr_fun hM i) j] rw [Matrix.mul_apply] rfl rw [h_dot] ring
Nat.sInf_le- If a natural number belongs to a set of natural numbers, the infimum of the set is at most that number.
Module.finBasisOfFinrankEq- A free module over a commutative ring with finite rank n admits a basis indexed by {0, ..., n - 1}.
Matrix.mulVec_single_one- Multiplying a matrix by the standard basis vector e_j yields its j-th column.
Module.Basis.sum_repr- Every vector decomposes as the sum of its basis coordinates times the respective basis vectors.
congr_arg- If two arguments are equal, a function takes the same value on both.
congr_fun- If two functions are equal, they take the same value at any point.
Submodule.coe_sum- The coercion of a finite sum in a submodule to the ambient module equals the sum of the coerced elements.
Submodule.coe_smul- The coercion of a scalar multiple in a submodule to the ambient module equals the scalar multiple of the coerced element.
Finset.sum_apply- Evaluating a finite sum of functions at a point equals the sum of the functions evaluated at that point.
Pi.smul_apply- Pointwise scalar multiplication of a function evaluates at any input to the scalar product of that function value.
smul_eq_mul- Scalar multiplication of a ring on itself coincides with the ring multiplication.
Matrix.mul_apply- The (i, k)-th entry of a matrix product M * N is the sum over j of M_ij * N_jk.
Finset.sum_congr- Sums over identical index sets of terms that are pointwise equal are equal.
mul_comm- Multiplication in a commutative structure satisfies a * b = b * a.
Matrix.posSemidef_vecMulVec_self_star- The outer product of a vector with its conjugate transpose, a a^*, is positive semidefinite.
star_trivial- On real numbers, the star involution (complex conjugation) is the identity map.
Matrix.vecMulVec_mul_vecMulVec- The product of two rank-one outer product matrices (u vᵀ)(w xᵀ) equals (v · w) (u xᵀ).
Matrix.trace_vecMulVec- The trace of the outer product matrix a bᵀ equals the dot product a · b.
dotProduct_smul- The dot product is linear in its second argument under scalar multiplication: v · (c • w) = c • (v · w).
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.
/-- The positive semidefinite rank of the Hadamard square of a real matrix is at most its ordinary rank. -/theorem matrix_psd_rank_hadamard_self_le_rank {m n : Type*} [Fintype m] [Fintype n] (M : Matrix m n ℝ) : matrix_psd_rank (Matrix.hadamard M M) ≤ Matrix.rank M := by classical apply Nat.sInf_le change matrix_has_psd_factorization (Matrix.hadamard M M) (Matrix.rank M) dsimp [matrix_has_psd_factorization] let r := Matrix.rank M let b : Module.Basis (Fin r) ℝ M.mulVecLin.range := Module.finBasisOfFinrankEq ℝ M.mulVecLin.range rfl have hj (j : n) : (fun i => M i j) ∈ M.mulVecLin.range := ⟨Pi.single j 1, Matrix.mulVec_single_one M j⟩ let U : Matrix m (Fin r) ℝ := fun i k => (b k : m → ℝ) i let V : Matrix (Fin r) n ℝ := fun k j => b.repr ⟨fun i => M i j, hj j⟩ k have hM : M = U * V := by ext i j have h := Module.Basis.sum_repr b ⟨fun i => M i j, hj j⟩ have h_val := congr_arg Subtype.val h have h_eval := congr_fun h_val i simp only [Submodule.coe_sum, Submodule.coe_smul, Finset.sum_apply, Pi.smul_apply, smul_eq_mul] at h_eval rw [Matrix.mul_apply] rw [← h_eval] apply Finset.sum_congr rfl intro k _ simp [U, V, mul_comm] let A (i : m) : Matrix (Fin r) (Fin r) ℝ := Matrix.vecMulVec (U i) (U i) let B (j : n) : Matrix (Fin r) (Fin r) ℝ := Matrix.vecMulVec (fun k => V k j) (fun k => V k j) refine ⟨A, B, ?_, ?_, ?_⟩ · intro i have := Matrix.posSemidef_vecMulVec_self_star (U i) rwa [star_trivial] at this · intro j have := Matrix.posSemidef_vecMulVec_self_star (fun k => V k j) rwa [star_trivial] at this · intro i j have h_tr : (A i * B j).trace = ((U i) ⬝ᵥ (fun k => V k j)) ^ 2 := by dsimp [A, B] rw [Matrix.vecMulVec_mul_vecMulVec] rw [Matrix.trace_vecMulVec] rw [dotProduct_smul] ring rw [h_tr] have h_dot : (U i) ⬝ᵥ (fun k => V k j) = M i j := by rw [congr_fun (congr_fun hM i) j] rw [Matrix.mul_apply] rfl rw [h_dot] ring