AFTD Auto-Formalizing Theoretical Domains

matrix_support_psd_rank_bound_le_rank

theoremverifiedformalization

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

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

    lines 3–4

    uses mul_self_nonneg

      have _ := hM
      have h_nonneg : ∀ i j, 0 ≤ Matrix.hadamard M M i j := fun i j => mul_self_nonneg (M i j)
  2. $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$.

    lines 5–6

    uses matrix_support_hadamard_self

      have h1 := h_bound (Matrix.hadamard M M) h_nonneg
      rw [matrix_support_hadamard_self] at h1
  3. $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.

    line 7

    uses Nat.cast_le.mpr, matrix_psd_rank_hadamard_self_le_rank

      exact 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}$.

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

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