AFTD Auto-Formalizing Theoretical Domains

matrix_psd_rank_le_rank_of_hadamard_eq

theoremverifiedformalization

For 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 = Matrix.hadamard R R, then the positive semidefinite rank of M is at most the ordinary rank of R (matrix_psd_rank M ≤ Matrix.rank R).

Statement

theorem matrix_psd_rank_le_rank_of_hadamard_eq {m n : Type*} [Fintype m] [Fintype n] (M R : Matrix m n ℝ) (hM : ∀ i j, 0 ≤ M i j) (hR : M = Matrix.hadamard R R) : matrix_psd_rank M ≤ Matrix.rank R
Formalizes
arXiv:2610.04498 Lemma 2.1 -- Rank-sensitive vertex bounds for semidefinite lifts
Verified
26 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • 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_factorization_hadamard_selfFor finite types m and n and any real matrix R : Matrix m n ℝ, the Hadamard square Matrix.hadamard R R has a positive semidefinite…
  • matrix_psd_rank_hadamard_self_le_rankFor 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…

Read back from the Lean

For any finite types m and n, and any real matrices M, R : Matrix m n ℝ, if every entry of M is non-negative (∀ i j, 0 ≤ M i j) and M is the Hadamard (entrywise) product of R with itself (M = Matrix.hadamard R R), then the PSD rank of M (matrix_psd_rank M) is less than or equal to the matrix rank of R (Matrix.rank R).

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 proof substitutes the assumption that $M$ is the Hadamard square $R \odot R$ directly into the goal. The claim then follows immediately from `matrix_psd_rank_hadamard_self_le_rank`, which establishes that the positive semidefinite rank of the Hadamard square of any real matrix is bounded by its ordinary rank.

  1. The positive semidefinite rank of $M$ is at most the rank of $R$.

    Substitute the equality $M = R \odot R$ (given by $hR$) into the goal, reducing the inequality to $\operatorname{psd-rank}(R \odot R) \le \operatorname{rank}(R)$. This holds directly by `matrix_psd_rank_hadamard_self_le_rank` applied to $R$.

    lines 3–4

    uses matrix_psd_rank_hadamard_self_le_rank

      subst hR
      exact matrix_psd_rank_hadamard_self_le_rank R
matrix_psd_rank_hadamard_self_le_rank
For any real matrix $M$, the positive semidefinite rank of its entrywise square (Hadamard square) $M \odot M$ is at most the ordinary rank of $M$.

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

/-- If M is a nonnegative real matrix equal to the Hadamard square of R, then the positive semidefinite rank of M is at most the rank of R. -/theorem matrix_psd_rank_le_rank_of_hadamard_eq {m n : Type*} [Fintype m] [Fintype n] (M R : Matrix m n ℝ) (hM : ∀ i j, 0 ≤ M i j) (hR : M = Matrix.hadamard R R) : matrix_psd_rank M ≤ Matrix.rank R := by  subst hR  exact matrix_psd_rank_hadamard_self_le_rank R
See it in the graphDiscuss this resultChallenge it