binary_rank
For 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 binary matrices A : Matrix (Fin n) (Fin k) (Fin 2) and B : Matrix (Fin k) (Fin m) (Fin 2) whose values in ℕ satisfy H.map (·.val) = A.map (·.val) * B.map (·.val).
Statement
noncomputable def binary_rank {n m : ℕ} (H : Matrix (Fin n) (Fin m) (Fin 2)) : ℕ
- Defined in
- arXiv:2611.14163, Definition 2.1
- Verified
- 12 Nov 2026
- Axioms
- none listed
- Used by 1
- binary_rank_zeroThe all-zero binary matrix of dimensions n × m with entries in Fin 2 has binary rank 0.
Read back from the Lean
For natural numbers n and m and a matrix H : Matrix (Fin n) (Fin m) (Fin 2), binary_rank H is defined as the infimum (in ℕ, via sInf) of the set of all k : ℕ such that there exist matrices A : Matrix (Fin n) (Fin k) (Fin 2) and B : Matrix (Fin k) (Fin m) (Fin 2) satisfying H.map (·.val) = A.map (·.val) * B.map (·.val), where the entries of H, A, and B are mapped to ℕ via Fin.val and matrix multiplication is computed over ℕ.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- The binary rank of a binary matrix H is the minimum inner dimension k of a binary factorization H = A * B over ℕ. -/ noncomputable def binary_rank {n m : ℕ} (H : Matrix (Fin n) (Fin m) (Fin 2)) : ℕ := sInf {k : ℕ | ∃ (A : Matrix (Fin n) (Fin k) (Fin 2)) (B : Matrix (Fin k) (Fin m) (Fin 2)), H.map (·.val) = A.map (·.val) * B.map (·.val)}