matrix_psd_rank_le_rank_of_hadamard_eq
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.
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$.
uses
matrix_psd_rank_hadamard_self_le_ranksubst 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$.
- The hypothesis `hM` that $M$ is entrywise nonnegative is not used in the proof; any Hadamard square of a real matrix has entries $R_{i,j}^2 \ge 0$, and `matrix_psd_rank_hadamard_self_le_rank` holds without requiring nonnegativity as an explicit hypothesis.
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.
/-- 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