matrix_support_psd_rank_bound_le_rank
For finite types m and n, let b : Set (m × n) → ℝ be a function on support patterns such that b (matrix_support M) ≤ (matrix_psd_rank M : ℝ) for every nonnegative real matrix M : Matrix m n ℝ. Then b (matrix_support M) ≤ (Matrix.rank M : ℝ) for every nonnegative real matrix M.
Statement
theorem matrix_support_psd_rank_bound_le_rank {m n : Type*} [Fintype m] [Fintype n] (b : Set (m × n) → ℝ) (h_bound : ∀ (M : Matrix m n ℝ), (∀ i j, 0 ≤ M i j) → b (matrix_support M) ≤ (matrix_psd_rank M : ℝ)) (M : Matrix m n ℝ) (hM : ∀ i j, 0 ≤ M i j) : b (matrix_support M) ≤ (Matrix.rank M : ℝ)
- Formalizes
- scout/2610-04498-rank-sensitive-vertex-bounds-for-semidefinite-lifts.md:2048
- Verified
- 23 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- matrix_supportThe support of an m × n matrix M is the set of index pairs (i, j) ∈ m × n such that M_ij ≠ 0.
- 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_support_hadamard_selfFor any real matrix M, the Hadamard square M ∘ M has the same support as M.
- 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
Given finite types $m$ and $n$, a function $b : \mathrm{Set}(m \times n) \to \mathbb{R}$, and a proof that for every entrywise non-negative matrix $M' \in \mathrm{Matrix}(m, n, \mathbb{R})$ (i.e., $\forall i\, j, 0 \le M'_{i, j}$), $b(\mathrm{matrix\_support}(M')) \le (\mathrm{matrix\_psd\_rank}(M') : \mathbb{R})$: Then for any entrywise non-negative matrix $M \in \mathrm{Matrix}(m, n, \mathbb{R})$ (satisfying $\forall i\, j, 0 \le M_{i, j}$), $b(\mathrm{matrix\_support}(M)) \le (\mathrm{Matrix.rank}(M) : \mathbb{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 applies the hypothesized support-based lower bound to the Hadamard square $M \odot M$ (the entrywise product of $M$ with itself). Because squaring real numbers preserves both nonnegativity and nonzeroness, $M \odot M$ is nonnegative and has the exact same support pattern as $M$. The result follows by chaining this bound with the known theorem that the positive semidefinite rank of $M \odot M$ is bounded above by the ordinary rank of $M$.
The Hadamard self-product $M \odot M$ is entrywise nonnegative.
Line 3 acknowledges the hypothesis hM that $M$ is nonnegative. Line 4 constructs h_nonneg, showing that each entry $(M \odot M)_{i,j} = M_{i,j}^2$ is nonnegative using mul_self_nonneg.
uses
mul_self_nonneghave _ := hM have h_nonneg : ∀ i j, 0 ≤ Matrix.hadamard M M i j := fun i j => mul_self_nonneg (M i j)
$b(\operatorname{matrix\_support} M) \le \operatorname{matrix\_psd\_rank}(M \odot M)$
Applying the hypothesis h_bound to $M \odot M$ with the nonnegativity witness h_nonneg yields $b(\operatorname{matrix\_support}(M \odot M)) \le \operatorname{matrix\_psd\_rank}(M \odot M)$. Rewriting with matrix_support_hadamard_self replaces the support of $M \odot M$ with the support of $M$.
uses
matrix_support_hadamard_selfhave h1 := h_bound (Matrix.hadamard M M) h_nonneg rw [matrix_support_hadamard_self] at h1
$b(\operatorname{matrix\_support} M) \le \operatorname{Matrix.rank} M$
By matrix_psd_rank_hadamard_self_le_rank, the semidefinite rank of $M \odot M$ is at most the ordinary rank of $M$. Casting this inequality to the real numbers via Nat.cast_le.mpr and chaining it with the inequality from the previous step via transitivity completes the proof.
uses
Nat.cast_le.mpr,matrix_psd_rank_hadamard_self_le_rankexact h1.trans (Nat.cast_le.mpr (matrix_psd_rank_hadamard_self_le_rank M))
mul_self_nonneg- The square of any element in an ordered semiring is nonnegative ($0 \le a \cdot a$).
matrix_support_hadamard_self- The support (the set of non-zero entries) of the Hadamard self-product $M \odot M$ equals the support of $M$.
matrix_psd_rank_hadamard_self_le_rank- The positive semidefinite rank of the Hadamard self-product $M \odot M$ of a real matrix is at most the ordinary rank of $M$.
Nat.cast_le.mpr- An inequality between natural numbers implies the corresponding inequality between their casts into an ordered semiring such as $\mathbb{R}$.
- The hypothesis `hM` (that $M$ is entrywise nonnegative) is acknowledged in line 3 (`have _ := hM`) to prevent an unused variable warning; mathematically, the entrywise square $M \odot M$ is nonnegative for any real matrix $M$, regardless of the signs of the entries 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
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.
/-- Any support-based lower bound for semidefinite rank cannot exceed the ordinary rank of any nonnegative matrix. -/theorem matrix_support_psd_rank_bound_le_rank {m n : Type*} [Fintype m] [Fintype n] (b : Set (m × n) → ℝ) (h_bound : ∀ (M : Matrix m n ℝ), (∀ i j, 0 ≤ M i j) → b (matrix_support M) ≤ (matrix_psd_rank M : ℝ)) (M : Matrix m n ℝ) (hM : ∀ i j, 0 ≤ M i j) : b (matrix_support M) ≤ (Matrix.rank M : ℝ) := by have _ := hM have h_nonneg : ∀ i j, 0 ≤ Matrix.hadamard M M i j := fun i j => mul_self_nonneg (M i j) have h1 := h_bound (Matrix.hadamard M M) h_nonneg rw [matrix_support_hadamard_self] at h1 exact h1.trans (Nat.cast_le.mpr (matrix_psd_rank_hadamard_self_le_rank M))