matrix_det_eq_permanent_of_char_two
For every commutative ring R of characteristic 2 and any square matrix M over R indexed by a finite type n with decidable equality, the determinant of M equals the permanent of M.
Statement
theorem matrix_det_eq_permanent_of_char_two {n R : Type*} [DecidableEq n] [Fintype n] [CommRing R] [CharP R 2] (M : Matrix n n R) : M.det = M.permanent
- Formalizes
- Valiant 1979, 'Completeness classes in algebra', STOC 1979, Sec. 3
- Verified
- 08 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- matrix_permanent_mul_of_char_twoFor every commutative ring R of characteristic 2 and any square matrices A and B over R indexed by a finite type n with decidable…
Read back from the Lean
For any finite type $n$ with decidable equality, any commutative ring $R$ of characteristic 2, and any $n \times n$ matrix $M$ with entries in $R$, the determinant of $M$ is equal to the permanent of $M$.
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 determinant and the permanent of a square matrix are both defined as sums over all permutations of the product of the entries chosen by the permutation, differing only by the sign factor sgn(σ) in the determinant. In any commutative ring of characteristic 2, -1 = 1, so the sign of every permutation evaluates to 1. Consequently, the summands of the determinant and the permanent coincide term by term, and the two values are equal.
The identity det M = permanent M reduces to showing that the determinant term equals the permanent term for each permutation σ.
By Matrix.det_apply' and the definition Matrix.permanent, both the determinant and the permanent are sums indexed by the permutations σ of n. Applying Finset.sum_congr, the two sums are equal if their terms agree for every permutation σ, that is, if sgn(σ) ∏ᵢ M_{σ(i), i} = ∏ᵢ M_{σ(i), i}.
uses
Matrix.det_apply',Matrix.permanent,Finset.sum_congrrw [Matrix.det_apply', Matrix.permanent] refine Finset.sum_congr rfl (fun σ _ => ?_)
In a ring of characteristic 2, the sign of any permutation σ evaluates to 1.
The sign of a permutation σ belongs to ℤˣ, so it is either 1 or -1 by Int.units_eq_one_or. If sgn(σ) = 1, its canonical image in R is 1. If sgn(σ) = -1, its image in R is -1, which equals 1 by CharTwo.neg_eq because R has characteristic 2.
uses
Int.units_eq_one_or,CharTwo.neg_eqhave hsign : (↑↑(Equiv.Perm.sign σ) : R) = 1 := by rcases Int.units_eq_one_or (Equiv.Perm.sign σ) with h | h <;> rw [h] · simp · simp [CharTwo.neg_eq]
The summands of the determinant and permanent agree for every permutation σ, concluding the proof.
Substituting the fact that the sign factor is 1 (hsign), the summand simplifies via 1 * a = a (one_mul) to the permanent summand ∏ᵢ M_{σ(i), i}.
uses
one_mulrw [hsign, one_mul]
Matrix.det_apply'- The determinant of a square matrix M equals the Leibniz sum over all permutations σ of sgn(σ) multiplied by the product of the diagonal entries M_{σ(i), i}.
Matrix.permanent- The permanent of a square matrix M is defined as the sum over all permutations σ of the product of the diagonal entries M_{σ(i), i}.
Finset.sum_congr- Two sums over the same finite set are equal if their corresponding terms are equal for all elements of the set.
Int.units_eq_one_or- The only invertible elements (units) in the integers ℤ are 1 and -1.
CharTwo.neg_eq- In any ring of characteristic 2, the additive inverse of any element equals the element itself (-x = x).
one_mul- Multiplying any element on the left by 1 leaves it unchanged (1 * a = a).
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 determinant of any square matrix equals its permanent. -/theorem matrix_det_eq_permanent_of_char_two {n R : Type*} [DecidableEq n] [Fintype n] [CommRing R] [CharP R 2] (M : Matrix n n R) : M.det = M.permanent := by rw [Matrix.det_apply', Matrix.permanent] refine Finset.sum_congr rfl (fun σ _ => ?_) have hsign : (↑↑(Equiv.Perm.sign σ) : R) = 1 := by rcases Int.units_eq_one_or (Equiv.Perm.sign σ) with h | h <;> rw [h] · simp · simp [CharTwo.neg_eq] rw [hsign, one_mul]