matrix3_unit_check_eq_true_iff
The computable checker matrix3_unit_check is true exactly when the list agrees with matrix multiplication on every pair of 3x3 matrix units.
Statement
theorem matrix3_unit_check_eq_true_iff (L : List (Matrix3Triad (ZMod 2))) :
matrix3_unit_check L = true ↔
∀ i j k l : Fin 3,
eval_matrix3_decomposition L (Matrix.single i j (1 : ZMod 2)) (Matrix.single k l (1 : ZMod 2))
= Matrix.single i j (1 : ZMod 2) * Matrix.single k l (1 : ZMod 2)- Source
- step towards matrix3_tensor_rank_zmod2_le_22
- Verified
- 23 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- matrix3_unit_checkA computable Bool-valued checker that tests a list L of triads over ZMod 2 against all 81 pairs of 3x3 matrix units: it returns true…
- Matrix3TriadGiven a type R, a Matrix3Triad R is a structure consisting of three 3-by-3 matrices with entries in R, labeled u, v, and w.
- eval_matrix3_decompositionGiven a commutative semiring R, a list L of Matrix3Triad R, and 3x3 matrices A and B over R, eval_matrix3_decomposition L A B is the sum…
- Used by 2
- matrix3_tensor_rank_le_zmod2_iff_unit_checkFor every natural number r, 3x3 matrix multiplication over ZMod 2 has a valid decomposition with at most r triads if and only if there is…
- matrix3_unit_check_witnessesThe checker matrix3_unit_check returns true on the classical 23-triad decomposition of 3x3 matrix multiplication over ZMod 2 (so the…
The proof, explained
The theorem establishes that the computable test `matrix3_unit_check L` returns `true` if and only if the candidate decomposition `L` matches matrix multiplication on all pairs of 3×3 matrix units over $\mathbb{Z}/2\mathbb{Z}$. The proof unfolds `matrix3_unit_check`, which is defined as four nested iterations of `List.all` over `List.finRange 3`. The simplifier turns these into universal quantifications over `Fin 3` and reflects the boolean `decide` into propositional equality, matching the right-hand side.
`matrix3_unit_check L = true` is equivalent to the proposition that the decomposition computes the product of all pairs of 3×3 matrix units.
The proof unfolds `matrix3_unit_check`, which is defined as four nested `List.all` checks over `List.finRange 3`. The simplifier applies `List.all_eq_true` to convert each `List.all` check into a universal quantifier over elements of the list, uses `List.mem_finRange` to discharge the membership condition since every index in `Fin 3` belongs to `List.finRange 3`, and applies `decide_eq_true_eq` to replace `decide (...) = true` with the equality itself. This reduces the left-hand side to the exact quantified statement on the right-hand side, closing the goal.
uses
matrix3_unit_check,List.all_eq_true,List.mem_finRange,decide_eq_true_eqsimp [matrix3_unit_check, List.all_eq_true, List.mem_finRange, decide_eq_true_eq]
matrix3_unit_check- The definition of the boolean checker, which tests whether the decomposition evaluates to the correct product across all 81 pairs of matrix units using nested `List.all` calls over `List.finRange 3`.
List.all_eq_true- A list satisfies `l.all p = true` if and only if `p x = true` for every element `x ∈ l`.
List.mem_finRange- Every index `x : Fin n` is an element of `List.finRange n`.
decide_eq_true_eq- The boolean reflection `decide p` evaluates to `true` if and only if the proposition `p` holds.
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 Bool checker is true exactly on the lists agreeing with matrix multiplication on the 81 matrix-unit pairs; it discharges a `decide` into the hypothesis of matrix3_valid_of_unit_checks. -/theorem matrix3_unit_check_eq_true_iff (L : List (Matrix3Triad (ZMod 2))) : matrix3_unit_check L = true ↔ ∀ i j k l : Fin 3, eval_matrix3_decomposition L (Matrix.single i j (1 : ZMod 2)) (Matrix.single k l (1 : ZMod 2)) = Matrix.single i j (1 : ZMod 2) * Matrix.single k l (1 : ZMod 2) := by simp [matrix3_unit_check, List.all_eq_true, List.mem_finRange, decide_eq_true_eq]