binary_rank_zero
The all-zero binary matrix of dimensions n × m with entries in Fin 2 has binary rank 0.
Statement
theorem binary_rank_zero (n m : ℕ) :
binary_rank (0 : Matrix (Fin n) (Fin m) (Fin 2)) = 0- Formalizes
- arXiv:2611.14163, Definition 2.1
- Verified
- 12 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- binary_rankFor an n × m binary matrix H with entries in Fin 2, the binary rank is the infimum in ℕ of all natural numbers k for which there exist…
- positive_matrix_order_four_left_stationaryA strictly positive order-four real matrix with constant row sum has a strictly positive normalized left eigenvector with that eigenvalue.
Read back from the Lean
For any two natural numbers $n$ and $m$, the binary rank of the $n \times m$ zero matrix with entries in $\text{Fin } 2$ is $0$.
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 binary rank of an n × m binary matrix is defined as the minimal dimension k such that the matrix factors as the product of an n × k matrix and a k × m matrix over Fin 2. For the all-zero matrix, choosing k = 0 yields a valid factorisation because matrix multiplication over an empty intermediate index Fin 0 produces all zeros. Since 0 is in the set of valid intermediate dimensions, the infimum of the set is 0.
The binary rank of the n × m zero matrix over Fin 2 is 0. automation
Unfolding the definition of `binary_rank`, the binary rank of a matrix is the infimum of all k ∈ ℕ for which the matrix can be factored as the product of an n × k matrix and a k × m matrix over Fin 2. For k = 0, the unique n × 0 and 0 × m matrices over Fin 2 have product equal to the n × m zero matrix, since each entry is a sum over the empty index type Fin 0. Because 0 belongs to the set of factorisation dimensions, the infimum of this set in ℕ is 0. The automation (`simpa`) simplifies the matrix product over Fin 0 and applies the infimum properties in ℕ to close the goal.
uses
positive_matrix_order_four_left_stationarybinary_rank (0 : Matrix (Fin n) (Fin m) (Fin 2)) = 0 := by first | exact positive_matrix_order_four_left_stationary | (apply positive_matrix_order_four_left_stationary <;> assumption) | (apply positive_matrix_order_four_left_stationary <;> simp_all) | simpa using positive_matrix_order_four_left_stationary | (simp only [binary_rank] at *; first | exact positive_matrix_order_four_left_stationary | (apply positive_matrix_order_four_left_stationary <;> assumption) | (apply positive_matrix_order_four_left_stationary <;> simp_all) | simpa using positive_matrix_order_four_left_stationary)
positive_matrix_order_four_left_stationary- A 4 × 4 real matrix with strictly positive entries and constant row sum r possesses a strictly positive stationary probability vector associated with eigenvalue r.
- The tactic script invokes `simpa using positive_matrix_order_four_left_stationary`, which was generated by automated search. The lemma `positive_matrix_order_four_left_stationary` (concerning Perron-Frobenius stationary vectors for 4×4 positive matrices) is completely irrelevant to the problem; `simpa` discharges the goal solely through its simplifier `simp`, leaving the lemma unused.
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.
/-- The all-zero binary matrix has binary rank zero. -/theorem binary_rank_zero (n m : ℕ) : binary_rank (0 : Matrix (Fin n) (Fin m) (Fin 2)) = 0 := by first | exact positive_matrix_order_four_left_stationary | (apply positive_matrix_order_four_left_stationary <;> assumption) | (apply positive_matrix_order_four_left_stationary <;> simp_all) | simpa using positive_matrix_order_four_left_stationary | (simp only [binary_rank] at *; first | exact positive_matrix_order_four_left_stationary | (apply positive_matrix_order_four_left_stationary <;> assumption) | (apply positive_matrix_order_four_left_stationary <;> simp_all) | simpa using positive_matrix_order_four_left_stationary)