matrix_permanent_mul_of_char_two
For every commutative ring R of characteristic 2 and any square matrices A and B over R indexed by a finite type n with decidable equality, the permanent of the matrix product A * B equals the product of the permanent of A and the permanent of B.
Statement
theorem matrix_permanent_mul_of_char_two {n R : Type*} [DecidableEq n] [Fintype n] [CommRing R] [CharP R 2] (A B : Matrix n n R) : (A * B).permanent = A.permanent * B.permanent
- Related work
- folklore; Valiant 1979
- Verified
- 20 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- matrix_det_eq_permanent_of_char_twoFor every commutative ring R of characteristic 2 and any square matrix M over R indexed by a finite type n with decidable equality, the…
Read back from the Lean
For any finite type $n$ with decidable equality and any commutative ring $R$ of characteristic 2, and for any two $n \times n$ matrices $A$ and $B$ with entries in $R$, the permanent of their matrix product $A * B$ equals the product of their permanents, $\operatorname{perm}(A) \cdot \operatorname{perm}(B)$.
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 proof reduces the multiplicativity of the permanent to that of the determinant. Over a commutative ring of characteristic 2, signs of permutations are trivial, so the permanent and the determinant of a square matrix are identical. Rewriting each permanent as a determinant allows the claim to follow directly from the standard multiplicativity of the determinant.
The statement reduces to the multiplicativity of the determinant: det(A * B) = det(A) * det(B).
In characteristic 2, 1 = -1, so the sign of any permutation is 1 and the determinant coincides with the permanent (matrix_det_eq_permanent_of_char_two). Replacing each permanent in the goal—(A * B).permanent, A.permanent, and B.permanent—with the corresponding determinant converts the equation into one about determinants.
uses
matrix_det_eq_permanent_of_char_tworw [← matrix_det_eq_permanent_of_char_two, ← matrix_det_eq_permanent_of_char_two A, ← matrix_det_eq_permanent_of_char_two B]det(A * B) = det(A) * det(B), closing the goal.
The determinant is multiplicative over any commutative ring, as established by Matrix.det_mul.
uses
Matrix.det_mulexact Matrix.det_mul A B
matrix_det_eq_permanent_of_char_two- Over a commutative ring of characteristic 2, the determinant of any square matrix equals its permanent.
Matrix.det_mul- The determinant of the product of two square matrices over a commutative ring equals the product of their determinants.
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.
/-- Over any commutative ring of characteristic 2, the permanent of a product of square matrices equals the product of their permanents. -/theorem matrix_permanent_mul_of_char_two {n R : Type*} [DecidableEq n] [Fintype n] [CommRing R] [CharP R 2] (A B : Matrix n n R) : (A * B).permanent = A.permanent * B.permanent := by rw [← matrix_det_eq_permanent_of_char_two, ← matrix_det_eq_permanent_of_char_two A, ← matrix_det_eq_permanent_of_char_two B] exact Matrix.det_mul A B