AFTD Auto-Formalizing Theoretical Domains

binary_rank_zero

theoremverifiedformalization

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.

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

    line 3

    uses positive_matrix_order_four_left_stationary

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

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

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