AFTD Auto-Formalizing Theoretical Domains

matrix_has_psd_factorization_hadamard_self

theoremverified

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

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.

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

    lines 3–10

    uses Module.finBasisOfFinrankEq, Matrix.mulVec_single_one

      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
  2. 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.

    lines 11–21

    uses Module.Basis.sum_repr, Matrix.mul_apply, mul_comm

      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]
  3. 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.

    lines 22–24

      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, ?_, ?_, ?_⟩
  4. 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.

    lines 25–27

    uses Matrix.posSemidef_vecMulVec_self_star, star_trivial

      · intro i
        have := Matrix.posSemidef_vecMulVec_self_star (U i)
        rwa [star_trivial] at this
  5. 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.

    lines 28–30

    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
  6. 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.

    lines 31–41

    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)².

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

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