complete_uniform_hypergraph_schmidt_rank_k_eq_add
For any positive integers a and b, when k = a + b, the rank over the rationals of the (a + 1) by (b + 1) matrix with entries (-1)^(Nat.choose (i + j) (a + b)) for 0 ≤ i ≤ a and 0 ≤ j ≤ b is equal to 2.
Statement
theorem complete_uniform_hypergraph_schmidt_rank_k_eq_add (a b : ℕ) (ha : 1 ≤ a) (hb : 1 ≤ b) : Matrix.rank (fun (i : Fin (a + 1)) (j : Fin (b + 1)) => (-1 : ℚ) ^ (Nat.choose (i.val + j.val) (a + b))) = 2
- Formalizes
- OP-1672
- Verified
- 16 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext
Read back from the Lean
For any natural numbers $a$ and $b$ satisfying $1 \le a$ and $1 \le b$, the rank over the rational numbers $\mathbb{Q}$ of the $(a+1) \times (b+1)$ matrix whose $(i, j)$-th entry (for $i \in \{0, \dots, a\}$ and $j \in \{0, \dots, b\}$) is $(-1)^{\binom{i + j}{a + b}}$ is equal to $2$.
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
To prove that the $(a+1) \times (b+1)$ matrix $M$ with entries $(-1)^{\binom{i+j}{a+b}}$ has rational rank 2 when $a, b \ge 1$, the proof establishes both $\mathrm{rank}(M) \le 2$ and $\mathrm{rank}(M) \ge 2$. Because row indices $i \le a$ and column indices $j \le b$ sum to at most $a+b$ with equality strictly when $(i,j)=(a,b)$, the binomial coefficient vanishes everywhere except at $(a,b)$ where it equals 1. Thus $M$ is an all-ones matrix minus 2 at $(a,b)$, which decomposes as the sum of two rank-1 outer products, giving $\mathrm{rank}(M) \le 2$ by subadditivity of rank. Finally, the $2 \times 2$ submatrix spanned by rows $\{0, a\}$ and columns $\{0, b\}$ has non-zero determinant $-2$, proving $\mathrm{rank}(M) \ge 2$.
For any rational matrices $A$ and $B$, $\mathrm{rank}(A + B) \le \mathrm{rank}(A) + \mathrm{rank}(B)$.
We enable classical logic and unfold the definition of matrix rank (`Matrix.rank`) to the dimension of the range of the corresponding linear map (`mulVecLin`). The linear map of $A + B$ equals the sum of the linear maps of $A$ and $B$ (`Matrix.mulVecLin_add`), so its range is contained in the subspace sum of their ranges (`LinearMap.range_add_le`). Applying monotonicity of subspace dimension (`Submodule.finrank_mono`) and the dimension bound for a sum of subspaces (`Submodule.finrank_add_le_finrank_add_finrank`), we conclude that rank is subadditive.
uses
Matrix.rank,Matrix.mulVecLin_add,Submodule.finrank_mono,LinearMap.range_add_le,Submodule.finrank_add_le_finrank_add_finrankclassical have hrank_add_le : ∀ {X Y : Type} [Fintype Y] (A B : Matrix X Y ℚ), (A + B).rank ≤ A.rank + B.rank := by intro X Y _ A B rw [Matrix.rank, Matrix.rank, Matrix.rank, Matrix.mulVecLin_add] exact (Submodule.finrank_mono (LinearMap.range_add_le A.mulVecLin B.mulVecLin)).trans (Submodule.finrank_add_le_finrank_add_finrank _ _)
We define the matrix $M$ and two rank-one indicator vectors $u$ and $v$ that isolate its bottom-right corner.
We abbreviate the given matrix as $M$, having entries $M_{i, j} = (-1)^{\binom{i+j}{a+b}}$, and restate the theorem as $\mathrm{rank}(M) = 2$. We define vectors $u$ (which takes the value $-2$ at row index $a$ and $0$ elsewhere) and $v$ (which takes the value $1$ at column index $b$ and $0$ elsewhere). Their outer product $u v^T$ is zero everywhere except at position $(a, b)$, where it equals $-2$.
set M : Matrix (Fin (a+1)) (Fin (b+1)) ℚ := fun i j => (-1:ℚ) ^ (Nat.choose (i.val+j.val) (a+b)) with hM change Matrix.rank M = 2 let u : Fin (a+1) → ℚ := fun i => if i.val = a then -2 else 0 let v : Fin (b+1) → ℚ := fun j => if j.val = b then 1 else 0
Every entry $M_{i, j}$ satisfies $M_{i, j} = 1 + u_i v_j$.
For row index $i \le a$ and column index $j \le b$ (`Nat.lt_succ_iff.mp`), the sum satisfies $i + j \le a + b$ (`Nat.add_le_add`), with equality if and only if $i = a$ and $j = b$. In the equality case $i = a \land j = b$, the binomial coefficient is $\binom{a+b}{a+b} = 1$ (`Nat.choose_self`), so $M_{a, b} = (-1)^1 = -1$, which matches $1 + u_a v_b = 1 + (-2) \cdot 1 = -1$ (`if_pos`). In the strict inequality case $i + j < a + b$ (`lt_of_le_of_ne`), the binomial coefficient is $0$ (`Nat.choose_eq_zero_of_lt`), giving $M_{i, j} = (-1)^0 = 1$; since at least one of $i = a$ or $j = b$ fails, the product $u_i v_j$ vanishes (`if_neg`), matching $1 + 0 = 1$.
uses
Nat.lt_succ_iff.mp,Nat.add_le_add,Nat.choose_self,if_pos,lt_of_le_of_ne,Nat.choose_eq_zero_of_lt,if_neghave hchoose : ∀ (i : Fin (a+1)) (j : Fin (b+1)), M i j = 1 + u i * v j := by intro i j rw [hM] dsimp only [u, v] have hi : i.val ≤ a := Nat.lt_succ_iff.mp i.isLt have hj : j.val ≤ b := Nat.lt_succ_iff.mp j.isLt have hle : i.val + j.val ≤ a + b := Nat.add_le_add hi hj have hiff : i.val + j.val = a + b ↔ i.val = a ∧ j.val = b := by omega by_cases h : i.val = a ∧ j.val = b · have hsum : i.val + j.val = a + b := hiff.mpr h have hch : Nat.choose (i.val + j.val) (a + b) = 1 := by rw [hsum, Nat.choose_self] rw [hch] rw [if_pos h.1, if_pos h.2] norm_num · have hsum_ne : i.val + j.val ≠ a + b := fun hs => h (hiff.mp hs) have hlt : i.val + j.val < a + b := lt_of_le_of_ne hle hsum_ne have hch : Nat.choose (i.val + j.val) (a + b) = 0 := Nat.choose_eq_zero_of_lt hlt have hprod : (if i.val = a then (-2 : ℚ) else 0) * (if j.val = b then (1 : ℚ) else 0) = 0 := by by_cases h1 : i.val = a · have h2 : j.val ≠ b := fun h2 => h ⟨h1, h2⟩ rw [if_pos h1, if_neg h2]; norm_num · rw [if_neg h1]; norm_num rw [hch, hprod] norm_num
The rank of $M$ is at most 2.
Using the entrywise identity $M_{i, j} = 1 + u_i v_j$, we express $M$ as the sum of the all-ones outer product $\mathbf{1} \mathbf{1}^T$ and the outer product $u v^T$ (`Matrix.add_apply`, `Matrix.vecMulVec_apply`). Each outer product has rank at most 1 (`Matrix.rank_vecMulVec_le`). By our subadditivity lemma, $\mathrm{rank}(M) \le 1 + 1 = 2$.
uses
Matrix.add_apply,Matrix.vecMulVec_apply,Matrix.rank_vecMulVec_lehave hupper : Matrix.rank M ≤ 2 := by have hM_eq : M = Matrix.vecMulVec (fun _ : Fin (a+1) => (1:ℚ)) (fun _ : Fin (b+1) => (1:ℚ)) + (Matrix.vecMulVec u v : Matrix (Fin (a+1)) (Fin (b+1)) ℚ) := by ext i j rw [Matrix.add_apply, Matrix.vecMulVec_apply, Matrix.vecMulVec_apply, hchoose] norm_num rw [hM_eq] have h2 := hrank_add_le (Matrix.vecMulVec (fun _ : Fin (a+1) => (1:ℚ)) (fun _ : Fin (b+1) => (1:ℚ))) (Matrix.vecMulVec u v : Matrix (Fin (a+1)) (Fin (b+1)) ℚ) have h3 : (Matrix.vecMulVec (fun _ : Fin (a+1) => (1:ℚ)) (fun _ : Fin (b+1) => (1:ℚ)) : Matrix (Fin (a+1)) (Fin (b+1)) ℚ).rank ≤ 1 := Matrix.rank_vecMulVec_le _ _ have h4 : (Matrix.vecMulVec u v : Matrix (Fin (a+1)) (Fin (b+1)) ℚ).rank ≤ 1 := Matrix.rank_vecMulVec_le _ _ omega
The rank of $M$ is at least 2.
We consider the $2 \times 2$ submatrix on rows $\{0, a\}$ and columns $\{0, b\}$ (valid indices via `Nat.lt_succ_self`). Using the formula for $2 \times 2$ determinants (`Matrix.det_fin_two`) and our entry identity (`Matrix.submatrix_apply`, `Matrix.cons_val_zero`, `Matrix.cons_val_one`), its entries are $M_{0,0}=1$, $M_{0,b}=1$, $M_{a,0}=1$, and $M_{a,b}=-1$ because $a \ge 1$ and $b \ge 1$ ensure $0 \ne a$ and $0 \ne b$. The determinant is $1 \cdot (-1) - 1 \cdot 1 = -2 \ne 0$, so the submatrix has full rank 2 (`Matrix.rank_of_det_ne_zero`). Since submatrices cannot have higher rank than the ambient matrix (`Matrix.rank_submatrix_le`), we obtain $2 \le \mathrm{rank}(M)$.
uses
Nat.lt_succ_self,Matrix.rank_of_det_ne_zero,Matrix.det_fin_two,Matrix.submatrix_apply,Matrix.cons_val_zero,Matrix.cons_val_one,Matrix.rank_submatrix_lehave hlower : 2 ≤ Matrix.rank M := by let r : Fin 2 → Fin (a+1) := ![0, ⟨a, Nat.lt_succ_self a⟩] let c : Fin 2 → Fin (b+1) := ![0, ⟨b, Nat.lt_succ_self b⟩] have hsub : (M.submatrix r c).rank = 2 := by apply Matrix.rank_of_det_ne_zero rw [Matrix.det_fin_two] simp only [Matrix.submatrix_apply] rw [hchoose, hchoose, hchoose, hchoose] simp only [r, c, Matrix.cons_val_zero, Matrix.cons_val_one, u, v] simp [show ¬ (0:ℕ) = a by omega, show ¬ (0:ℕ) = b by omega] have hle := Matrix.rank_submatrix_le M r c omega
The rank of $M$ is exactly 2.
Combining the upper bound $\mathrm{rank}(M) \le 2$ and the lower bound $2 \le \mathrm{rank}(M)$, linear integer arithmetic concludes that $\mathrm{rank}(M) = 2$.
omega
Matrix.rank- The rank of a matrix over a commutative ring, defined as the dimension of the range of the corresponding linear map.
Matrix.mulVecLin_add- The linear map associated with the sum of two matrices is the sum of their individual linear maps: $(M + N).\mathrm{mulVecLin} = M.\mathrm{mulVecLin} + N.\mathrm{mulVecLin}$.
Submodule.finrank_mono- If a submodule is contained in another, its dimension is less than or equal to the larger submodule's dimension: $s \le t \implies \dim(s) \le \dim(t)$.
LinearMap.range_add_le- The range of the sum of two linear maps is contained in the sum of their ranges: $\mathrm{range}(f + g) \le \mathrm{range}(f) \sqcup \mathrm{range}(g)$.
Submodule.finrank_add_le_finrank_add_finrank- The dimension of the sum of two submodules is bounded by the sum of their dimensions: $\dim(s \sqcup t) \le \dim(s) + \dim(t)$.
Nat.lt_succ_iff.mp- For natural numbers $n$ and $m$, if $n < m + 1$, then $n \le m$.
Nat.add_le_add- If $a \le b$ and $c \le d$ for natural numbers, then $a + c \le b + d$.
Nat.choose_self- For any natural number $n$, $\binom{n}{n} = 1$.
if_pos- If a condition $c$ is true, then `if c then t else e` equals $t$.
lt_of_le_of_ne- In a partial order, if $a \le b$ and $a \ne b$, then $a < b$.
Nat.choose_eq_zero_of_lt- If $n < k$ for natural numbers, then $\binom{n}{k} = 0$.
if_neg- If a condition $c$ is false, then `if c then t else e` equals $e$.
Matrix.add_apply- The $(i, j)$-th entry of the sum of two matrices $A + B$ is $A_{i,j} + B_{i,j}$.
Matrix.vecMulVec_apply- The $(i, j)$-th entry of the outer product matrix $w v^T$ is $w_i \cdot v_j$.
Matrix.rank_vecMulVec_le- The rank of an outer product matrix $w v^T$ is at most 1.
Nat.lt_succ_self- For any natural number $n$, $n < n + 1$.
Matrix.rank_of_det_ne_zero- A square matrix over an integral domain with non-zero determinant has full rank equal to its dimension.
Matrix.det_fin_two- The determinant of a $2 \times 2$ matrix $A$ is $A_{0,0} A_{1,1} - A_{0,1} A_{1,0}$.
Matrix.submatrix_apply- The $(i, j)$-th entry of a submatrix $(A)_{r, c}$ is $A_{r(i), c(j)}$.
Matrix.cons_val_zero- The 0-th entry of a vector formed by prepending an element $x$ is $x$.
Matrix.cons_val_one- The 1-st entry of a vector formed by prepending an element $x$ to $u$ is $u(0)$.
Matrix.rank_submatrix_le- The rank of any submatrix of $A$ is at most the rank of $A$.
- The subadditivity of matrix rank (`hrank_add_le`) is established as an inline helper lemma using the finite dimension of the range of linear maps, as this general property was not directly cited from Mathlib.
- Indices in the $(a+1) \times (b+1)$ matrix are elements of `Fin (a + 1)` and `Fin (b + 1)`. The hypotheses $a \ge 1$ and $b \ge 1$ ensure that $0 \ne a$ and $0 \ne b$, so the selected $2 \times 2$ submatrix has distinct rows and columns.
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.
/-- For k = a + b and any positive integers a and b, the rational rank of the (a+1) x (b+1) complete (a+b)-uniform hypergraph matrix is exactly 2. -/theorem complete_uniform_hypergraph_schmidt_rank_k_eq_add (a b : ℕ) (ha : 1 ≤ a) (hb : 1 ≤ b) : Matrix.rank (fun (i : Fin (a + 1)) (j : Fin (b + 1)) => (-1 : ℚ) ^ (Nat.choose (i.val + j.val) (a + b))) = 2 := by classical have hrank_add_le : ∀ {X Y : Type} [Fintype Y] (A B : Matrix X Y ℚ), (A + B).rank ≤ A.rank + B.rank := by intro X Y _ A B rw [Matrix.rank, Matrix.rank, Matrix.rank, Matrix.mulVecLin_add] exact (Submodule.finrank_mono (LinearMap.range_add_le A.mulVecLin B.mulVecLin)).trans (Submodule.finrank_add_le_finrank_add_finrank _ _) set M : Matrix (Fin (a+1)) (Fin (b+1)) ℚ := fun i j => (-1:ℚ) ^ (Nat.choose (i.val+j.val) (a+b)) with hM change Matrix.rank M = 2 let u : Fin (a+1) → ℚ := fun i => if i.val = a then -2 else 0 let v : Fin (b+1) → ℚ := fun j => if j.val = b then 1 else 0 have hchoose : ∀ (i : Fin (a+1)) (j : Fin (b+1)), M i j = 1 + u i * v j := by intro i j rw [hM] dsimp only [u, v] have hi : i.val ≤ a := Nat.lt_succ_iff.mp i.isLt have hj : j.val ≤ b := Nat.lt_succ_iff.mp j.isLt have hle : i.val + j.val ≤ a + b := Nat.add_le_add hi hj have hiff : i.val + j.val = a + b ↔ i.val = a ∧ j.val = b := by omega by_cases h : i.val = a ∧ j.val = b · have hsum : i.val + j.val = a + b := hiff.mpr h have hch : Nat.choose (i.val + j.val) (a + b) = 1 := by rw [hsum, Nat.choose_self] rw [hch] rw [if_pos h.1, if_pos h.2] norm_num · have hsum_ne : i.val + j.val ≠ a + b := fun hs => h (hiff.mp hs) have hlt : i.val + j.val < a + b := lt_of_le_of_ne hle hsum_ne have hch : Nat.choose (i.val + j.val) (a + b) = 0 := Nat.choose_eq_zero_of_lt hlt have hprod : (if i.val = a then (-2 : ℚ) else 0) * (if j.val = b then (1 : ℚ) else 0) = 0 := by by_cases h1 : i.val = a · have h2 : j.val ≠ b := fun h2 => h ⟨h1, h2⟩ rw [if_pos h1, if_neg h2]; norm_num · rw [if_neg h1]; norm_num rw [hch, hprod] norm_num have hupper : Matrix.rank M ≤ 2 := by have hM_eq : M = Matrix.vecMulVec (fun _ : Fin (a+1) => (1:ℚ)) (fun _ : Fin (b+1) => (1:ℚ)) + (Matrix.vecMulVec u v : Matrix (Fin (a+1)) (Fin (b+1)) ℚ) := by ext i j rw [Matrix.add_apply, Matrix.vecMulVec_apply, Matrix.vecMulVec_apply, hchoose] norm_num rw [hM_eq] have h2 := hrank_add_le (Matrix.vecMulVec (fun _ : Fin (a+1) => (1:ℚ)) (fun _ : Fin (b+1) => (1:ℚ))) (Matrix.vecMulVec u v : Matrix (Fin (a+1)) (Fin (b+1)) ℚ) have h3 : (Matrix.vecMulVec (fun _ : Fin (a+1) => (1:ℚ)) (fun _ : Fin (b+1) => (1:ℚ)) : Matrix (Fin (a+1)) (Fin (b+1)) ℚ).rank ≤ 1 := Matrix.rank_vecMulVec_le _ _ have h4 : (Matrix.vecMulVec u v : Matrix (Fin (a+1)) (Fin (b+1)) ℚ).rank ≤ 1 := Matrix.rank_vecMulVec_le _ _ omega have hlower : 2 ≤ Matrix.rank M := by let r : Fin 2 → Fin (a+1) := ![0, ⟨a, Nat.lt_succ_self a⟩] let c : Fin 2 → Fin (b+1) := ![0, ⟨b, Nat.lt_succ_self b⟩] have hsub : (M.submatrix r c).rank = 2 := by apply Matrix.rank_of_det_ne_zero rw [Matrix.det_fin_two] simp only [Matrix.submatrix_apply] rw [hchoose, hchoose, hchoose, hchoose] simp only [r, c, Matrix.cons_val_zero, Matrix.cons_val_one, u, v] simp [show ¬ (0:ℕ) = a by omega, show ¬ (0:ℕ) = b by omega] have hle := Matrix.rank_submatrix_le M r c omega omega