AFTD Auto-Formalizing Theoretical Domains

matrix_psd_rank_hadamard_self_le_rank

theoremverified

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

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.

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

    lines 3–6

    uses Nat.sInf_le

      classical
      apply Nat.sInf_le
      change matrix_has_psd_factorization (Matrix.hadamard M M) (Matrix.rank M)
      dsimp [matrix_has_psd_factorization]
  2. 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.

    lines 7–12

    uses Module.finBasisOfFinrankEq, Matrix.mulVec_single_one

      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
  3. 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`).

    lines 13–23

    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_comm

      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]
  4. 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².

    lines 24–26

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

    lines 27–29

    uses Matrix.posSemidef_vecMulVec_self_star, star_trivial

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

    lines 30–32

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

    lines 33–40

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

    lines 41–46

    uses congr_fun, Matrix.mul_apply

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

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