matrix_has_psd_factorization_hadamard_self
For finite types m and n and any real matrix R : Matrix m n ℝ, the Hadamard square Matrix.hadamard R R has a positive semidefinite factorization of size Matrix.rank R.
Statement
theorem matrix_has_psd_factorization_hadamard_self {m n : Type*} [Fintype m] [Fintype n] (R : Matrix m n ℝ) : matrix_has_psd_factorization (Matrix.hadamard R R) (Matrix.rank R)
- Source
- arXiv:2610.04498 Lemma 2.1 proof -- Rank-sensitive vertex bounds for semidefinite lifts
- Verified
- 26 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- 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…
- matrix_trace_vecMulVec_mul_vecMulVecFor any finite type r and vectors u, v : r → ℝ, the trace of the product of outer products vecMulVec u u and vecMulVec v v equals the…
- Used by 1
- 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 any finite types $m$ and $n$, and any real $m \times n$ matrix $R$, the Hadamard product of $R$ with itself has a positive semidefinite (PSD) factorization of size equal to the rank of $R$ (that is, matrix_has_psd_factorization (Matrix.hadamard R R) (Matrix.rank R) holds).
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 entrywise Hadamard square R ⊙ R of a real matrix R has a positive semidefinite factorization of size r = rank R. The proof explicitly constructs a rank factorization R = U * V of size m × r and r × n using a basis for the column space of R. Setting the factors to be the rank-one matrices A i = U i (U i)ᵀ and B j = (V · j)(V · j)ᵀ, each A i and B j is positive semidefinite, and the trace formula trace(A i * B j) = (U i · V · j)² = (R i j)² completes the factorization.
Fix r = rank R and construct factor matrices U ∈ ℝ^{m × r} and V ∈ ℝ^{r × n} from a basis of the column space of R.
Unfolding the definition of a positive semidefinite factorization, the goal is to find positive semidefinite matrices A i and B j of size r × r such that (R ⊙ R) i j = R i j ^ 2 = trace(A i * B j), with r = rank R. The column space (range of the linear map defined by R) has dimension r, so Module.finBasisOfFinrankEq produces a basis b indexed by Fin r. Each column of R lies in this range because R e_j = R col j by Matrix.mulVec_single_one. We define U by taking the basis vectors as its columns, and V by taking the coordinates of the columns of R relative to b.
uses
Module.finBasisOfFinrankEq,Matrix.mulVec_single_oneclassical dsimp [matrix_has_psd_factorization] let r := Matrix.rank R let b : Module.Basis (Fin r) ℝ R.mulVecLin.range := Module.finBasisOfFinrankEq ℝ R.mulVecLin.range rfl have hj (j : n) : (fun i => R i j) ∈ R.mulVecLin.range := ⟨Pi.single j 1, Matrix.mulVec_single_one R 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 => R i j, hj j⟩ k
The matrix R factors as the product U * V.
To establish R = U * V, we show each entry (i, j) matches. By Module.Basis.sum_repr, the j-th column of R is the sum over k of V k j • b k. Evaluating this column vector equality at row index i gives R i j = ∑ k, b k i * V k j. By definition of U, b k i = U i k. Using mul_comm, this sum is ∑ k, U i k * V k j, which equals (U * V) i j by Matrix.mul_apply.
uses
Module.Basis.sum_repr,Matrix.mul_apply,mul_commhave hR : R = U * V := by ext i j have h := Module.Basis.sum_repr b ⟨fun i => R 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]
Candidate families of matrices A i and B j are defined as outer products of the rows of U and columns of V.
For each row index i ∈ m, define A i = Matrix.vecMulVec (U i) (U i) (the rank-one matrix U i (U i)ᵀ), and for each column index j ∈ n, define B j = Matrix.vecMulVec (V · j) (V · j). Providing these witnesses splits the remaining goal into three obligations: positive semidefiniteness of each A i, positive semidefiniteness of each B j, and the trace identity.
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, ?_, ?_, ?_⟩
For each i ∈ m, the matrix A i is positive semidefinite.
The outer product of a vector with its conjugate transpose is positive semidefinite by Matrix.posSemidef_vecMulVec_self_star. For real numbers, the star involution is trivial by star_trivial, so A i = U i (U i)ᵀ is positive semidefinite.
uses
Matrix.posSemidef_vecMulVec_self_star,star_trivial· intro i have := Matrix.posSemidef_vecMulVec_self_star (U i) rwa [star_trivial] at this
For each j ∈ n, the matrix B j is positive semidefinite.
Similarly, each B j is the outer product of the j-th column of V with itself. By Matrix.posSemidef_vecMulVec_self_star and star_trivial, B j is positive semidefinite.
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 all i ∈ m and j ∈ n, trace(A i * B j) = R i j * R i j.
By matrix_trace_vecMulVec_mul_vecMulVec, the trace of (U i (U i)ᵀ) * (V · j (V · j)ᵀ) is the square of the dot product (U i · V · j)². Since R = U * V, the definition of matrix multiplication in Matrix.mul_apply shows that this dot product is (U * V) i j = R i j. Substituting this yields trace(A i * B j) = R i j ^ 2, which matches R i j * R i j by ring arithmetic.
uses
matrix_trace_vecMulVec_mul_vecMulVec,Matrix.mul_apply· 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_trace_vecMulVec_mul_vecMulVec] rw [h_tr] have h_dot : (U i) ⬝ᵥ (fun k => V k j) = R i j := by rw [congr_fun (congr_fun hR i) j] rw [Matrix.mul_apply] rfl rw [h_dot] ring
Module.finBasisOfFinrankEq- A vector space (or free module) of finite rank r has a basis indexed by Fin r.
Matrix.mulVec_single_one- Multiplying a matrix by the j-th standard unit vector yields the j-th column of the matrix.
Module.Basis.sum_repr- Any vector in a module equals the linear combination of the basis vectors weighted by its coordinates in that basis.
Matrix.mul_apply- The (i, k)-th entry of a matrix product M * N is the sum over j of M i j * N j k.
mul_comm- Multiplication is commutative: a * b = b * a.
Matrix.posSemidef_vecMulVec_self_star- The outer product a a* of any vector with its conjugate transpose is positive semidefinite.
star_trivial- In a ring with trivial star involution (such as the real numbers ℝ), star r = r.
matrix_trace_vecMulVec_mul_vecMulVec- The trace of the product of two rank-one matrices (u uᵀ)(v vᵀ) equals the square of their dot product (u · v)².
- In textbook proofs, one typically takes an abstract rank factorization R = U V for granted; here, Lean explicitly constructs U and V by selecting a basis for the range of the linear map associated with R.
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 entrywise Hadamard square R ⊙ R of a real matrix R has a positive semidefinite factorization of size rank R. -/theorem matrix_has_psd_factorization_hadamard_self {m n : Type*} [Fintype m] [Fintype n] (R : Matrix m n ℝ) : matrix_has_psd_factorization (Matrix.hadamard R R) (Matrix.rank R) := by classical dsimp [matrix_has_psd_factorization] let r := Matrix.rank R let b : Module.Basis (Fin r) ℝ R.mulVecLin.range := Module.finBasisOfFinrankEq ℝ R.mulVecLin.range rfl have hj (j : n) : (fun i => R i j) ∈ R.mulVecLin.range := ⟨Pi.single j 1, Matrix.mulVec_single_one R 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 => R i j, hj j⟩ k have hR : R = U * V := by ext i j have h := Module.Basis.sum_repr b ⟨fun i => R 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_trace_vecMulVec_mul_vecMulVec] rw [h_tr] have h_dot : (U i) ⬝ᵥ (fun k => V k j) = R i j := by rw [congr_fun (congr_fun hR i) j] rw [Matrix.mul_apply] rfl rw [h_dot] ring