AFTD Auto-Formalizing Theoretical Domains

matrix_det_eq_permanent_of_char_two

theoremverifiedformalization

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.

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

    lines 3–4

    uses Matrix.det_apply', Matrix.permanent, Finset.sum_congr

      rw [Matrix.det_apply', Matrix.permanent]
      refine Finset.sum_congr rfl (fun σ _ => ?_)
  2. 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.

    lines 5–8

    uses Int.units_eq_one_or, CharTwo.neg_eq

      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]
  3. 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}.

    line 9

    uses one_mul

      rw [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

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