AFTD Auto-Formalizing Theoretical Domains

matrix_permanent_succ_row

theoremverifiedoriginal

For any commutative semiring R, any natural number n, any square matrix A of size (n+1) x (n+1) over R, and any row index i : Fin (n+1), the permanent of A equals the sum over all columns j : Fin (n+1) of A i j times the permanent of the submatrix obtained by deleting row i and column j: permanent A = ∑ j : Fin (n+1), A i j * permanent (A.submatrix i.succAbove j.succAbove).

Statement

theorem matrix_permanent_succ_row {n : ℕ} {R : Type*} [CommSemiring R]
    (A : Matrix (Fin n.succ) (Fin n.succ) R) (i : Fin n.succ) :
    A.permanent = ∑ j : Fin n.succ, A i j * (A.submatrix i.succAbove j.succAbove).permanent
Related work
Mathlib/LinearAlgebra/Matrix/Determinant/Basic.lean:771
Verified
20 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • matrix_permanent_succ_row_zeroFor any commutative semiring R, any natural number n, and any square matrix A of size (n+1) x (n+1) over R, the permanent of A equals the…
Used by 1
  • matrix_permanent_succ_columnFor any commutative semiring R, any natural number n, any square matrix A of size (n+1) x (n+1) over R, and any column index j : Fin…

Read back from the Lean

For any natural number $n$, any commutative semiring $R$, any $(n+1) \times (n+1)$ matrix $A$ with entries in $R$, and any row index $i \in \mathrm{Fin}(n+1)$: the permanent of $A$ equals the sum over all column indices $j \in \mathrm{Fin}(n+1)$ of $A_{i, j}$ multiplied by the permanent of the $n \times n$ submatrix of $A$ obtained by deleting row $i$ and column $j$ (via i.succAbove and j.succAbove).

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 Laplace expansion along an arbitrary row i is proved by reducing it to the expansion along row 0 via a row permutation. Applying the inverse cyclic permutation `i.cycleRange⁻¹` moves row i to row 0 while preserving the permanent. Expanding along row 0 and comparing the terms shows that the (0, j) entry is A i j and the submatrix omitting row 0 corresponds precisely to deleting row i from A.

  1. The permanent of A equals the row-0 Laplace expansion of the row-permuted matrix obtained by applying `i.cycleRange⁻¹` to the rows of A.

    By `Matrix.permanent_permute_cols`, permuting the rows of A by the permutation `i.cycleRange⁻¹` leaves the permanent unchanged. Applying the known base case `matrix_permanent_succ_row_zero` to this permuted matrix then expresses the permanent as the sum over columns j of the product of its (0, j) entry and the permanent of the submatrix omitting row 0 and column j.

    line 5

    uses Matrix.permanent_permute_cols, matrix_permanent_succ_row_zero

      rw [← Matrix.permanent_permute_cols i.cycleRange⁻¹, matrix_permanent_succ_row_zero]
  2. It suffices to show that for every column j, the j-th summand of the permuted expansion simplifies to `A ((Equiv.symm i.cycleRange) 0) j * (A.submatrix (⇑(Equiv.symm i.cycleRange) ∘ Fin.succ) (id ∘ j.succAbove)).permanent`, and equals `A i j * (A.submatrix i.succAbove j.succAbove).permanent`.

    Using `Finset.sum_congr`, equality of the two sums reduces to equality of each column's summand. Simplifying the submatrix operations on the left-hand side evaluates the (0, j) entry using `Matrix.submatrix_apply`, merges the nested submatrix extractions into composed row and column maps using `Matrix.submatrix_submatrix`, and rewrites the permutation inverse using `Equiv.Perm.inv_def`.

    lines 6–7

    uses Finset.sum_congr, Matrix.submatrix_apply, Matrix.submatrix_submatrix, Equiv.Perm.inv_def

      refine Finset.sum_congr rfl fun j _ => ?_
      simp only [Matrix.submatrix_apply, Matrix.submatrix_submatrix, Equiv.Perm.inv_def]
  3. For each column j, the j-th summand in the row-0 expansion matches the j-th summand in the expansion along row i, completing the proof.

    The inverse cycle permutation maps 0 to i by `Fin.cycleRange_symm_zero`, so the entry at row 0 is A i j. Furthermore, precomposing the inverse permutation with `Fin.succ` yields `i.succAbove` by `Fin.cycleRange_symm_succ`, showing that omitting row 0 of the permuted matrix corresponds to omitting row i of A. Along with `id ∘ j.succAbove = j.succAbove`, substituting these three identities makes both sides definitionally equal.

    lines 8–12

    uses Fin.cycleRange_symm_zero, Fin.cycleRange_symm_succ

      have h1 : i.cycleRange.symm 0 = i := Fin.cycleRange_symm_zero i
      have h2 : (⇑i.cycleRange.symm ∘ Fin.succ) = i.succAbove := funext (Fin.cycleRange_symm_succ i)
      have h3 : (id ∘ j.succAbove) = j.succAbove := rfl
      rw [h1, h2, h3]
      rfl
Matrix.permanent_permute_cols
Permuting the rows of a square matrix by an equivalence permutation does not change its permanent: `(M.submatrix (⇑σ) id).permanent = M.permanent`.
matrix_permanent_succ_row_zero
Laplace expansion of the permanent of an (n+1) × (n+1) matrix along row 0: the permanent equals the sum over all columns j of `A 0 j` times the permanent of the submatrix deleting row 0 and column j.
Finset.sum_congr
Two finite sums are equal if their index sets are equal and their summands agree on every element in the index set.
Matrix.submatrix_apply
The (i, j)-th entry of a submatrix is obtained by evaluating the original matrix at the reindexed row and column: `(A.submatrix r c) i j = A (r i) (c j)`.
Matrix.submatrix_submatrix
Taking successive submatrices corresponds to composing the respective row and column indexing functions: `(A.submatrix r₁ c₁).submatrix r₂ c₂ = A.submatrix (r₁ ∘ r₂) (c₁ ∘ c₂)`.
Equiv.Perm.inv_def
The group inverse `f⁻¹` of a permutation equals its inverse equivalence `Equiv.symm f`.
Fin.cycleRange_symm_zero
The inverse of the cyclic permutation `i.cycleRange` maps 0 to i.
Fin.cycleRange_symm_succ
For any index j, the inverse of `i.cycleRange` maps `j.succ` to `i.succAbove j` (omitting index i).

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

/-- Laplacian expansion of the permanent of an (n+1) x (n+1) matrix along row i. -/theorem matrix_permanent_succ_row {n : ℕ} {R : Type*} [CommSemiring R]    (A : Matrix (Fin n.succ) (Fin n.succ) R) (i : Fin n.succ) :    A.permanent = ∑ j : Fin n.succ, A i j * (A.submatrix i.succAbove j.succAbove).permanent := by  rw [← Matrix.permanent_permute_cols i.cycleRange⁻¹, matrix_permanent_succ_row_zero]  refine Finset.sum_congr rfl fun j _ => ?_  simp only [Matrix.submatrix_apply, Matrix.submatrix_submatrix, Equiv.Perm.inv_def]  have h1 : i.cycleRange.symm 0 = i := Fin.cycleRange_symm_zero i  have h2 : (⇑i.cycleRange.symm ∘ Fin.succ) = i.succAbove := funext (Fin.cycleRange_symm_succ i)  have h3 : (id ∘ j.succAbove) = j.succAbove := rfl  rw [h1, h2, h3]  rfl
See it in the graphDiscuss this resultChallenge it