CommunicationComplexity.Deterministic.Rank.rank_rectMatrix_le_one
theoremverifiedimported Lean
Combinatorial rectangles have rank-one indicator matrices. Let $X$ be any set and $Y$ a finite set, and let $R \subseteq X \times Y$ be a rectangle, meaning $R = A \times B$ for some $A \subseteq X$ and $B \subseteq Y$. Let $M_R \in \bbr^{X \times Y}$ be its indicator matrix, with $(M_R)_{x,y} = 1$ when $(x,y) \in R$ and $(M_R)_{x,y} = 0$ otherwise. Then $\mathrm{rank}(M_R) \le 1$.
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in theorem CommunicationComplexity.Deterministic.Rank.rank_rectMatrix_le_one {X Y : Type*} [Fintype Y] (R : Set (X × Y)) (hR : Rectangle.IsRectangle R) : (rectMatrix R).rank ≤ 1
- Source
- TCSlib, `CommunicationComplexity.Deterministic.Rank.rank_rectMatrix_le_one`
- Lean proof
- By Lucy Horowitz, Timothe Kasriel, Mihir Singhal, from github.com/Shilun-Allan-Li/tcslib at
c8a02591b1e5(Copyright (c) 2026 Lucy Horowitz, Timothe Kasriel, and Mihir Singhal. All rights reserved, Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.25.0.CommunicationComplexity.Deterministic.Rank.rank_rectMatrix_le_one← CommunicationComplexity.Deterministic.Rank.rank_rectMatrix_le_one (TCSlib/CommunicationComplexity/DeterministicCC/Rank.lean:86): verbatim
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- CommunicationComplexity.Deterministic.Rank.rectMatrixFor a subset $R \subseteq X \times Y$, the matrix $M_R \in \mathbb{R}^{X \times Y}$ is defined by $(M_R)_{x,y} = 1$ if $(x,y) \in R$ and…
- CommunicationComplexity.Rectangle.IsRectangleA subset $S \subseteq X \times Y$ is a rectangle if it factors as a product $A \times B$ for some $A \subseteq X$ and…
- Used by 1
- CommunicationComplexity.Deterministic.Rank.boolFunctionRank_le_ncardRank bounded by monochromatic partition size. Let $X$ be a finite set, $Y$ a finite set, and $f : X \to Y \to \mathrm{Bool}$ a Boolean…
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.
set_option relaxedAutoImplicit false inset_option autoImplicit false in/-- The indicator matrix of a combinatorial rectangle `R = A ×ˢ B` has rank at most `1`, since it is the outer product of the indicator vectors of `A` and `B`. -/theorem CommunicationComplexity.Deterministic.Rank.rank_rectMatrix_le_one {X Y : Type*} [Fintype Y] (R : Set (X × Y)) (hR : Rectangle.IsRectangle R) : (rectMatrix R).rank ≤ 1 := by classical obtain ⟨A, B, rfl⟩ := hR suffices rectMatrix (A ×ˢ B) = Matrix.vecMulVec (fun x => if x ∈ A then (1 : ℝ) else 0) (fun y => if y ∈ B then (1 : ℝ) else 0) by rw [this]; exact Matrix.rank_vecMulVec_le _ _ ext x y; simp only [rectMatrix, Matrix.of_apply, Matrix.vecMulVec, Set.mem_prod_eq] cases Classical.em (x ∈ A) <;> cases Classical.em (y ∈ B) <;> simp_all