AFTD Auto-Formalizing Theoretical Domains

matrix_permanent_succ_row_zero

theoremverified

For 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 sum over all columns j : Fin (n+1) of A 0 j times the permanent of the submatrix obtained by deleting row 0 and column j: permanent A = ∑ j : Fin (n+1), A 0 j * permanent (A.submatrix Fin.succ j.succAbove).

Statement

theorem matrix_permanent_succ_row_zero {n : ℕ} {R : Type*} [CommSemiring R]
    (A : Matrix (Fin n.succ) (Fin n.succ) R) :
    A.permanent = ∑ j : Fin n.succ, A 0 j * (A.submatrix Fin.succ j.succAbove).permanent
Source
Mathlib/LinearAlgebra/Matrix/Determinant/Basic.lean:763
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1
  • matrix_permanent_succ_rowFor 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),…

Read back from the Lean

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

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 theorem proves the Laplacian expansion of the permanent of an (n+1) × (n+1) matrix along row 0. It first proves an auxiliary lemma expanding along column 0 by decomposing every permutation in Sₙ₊₁ into its value at 0 and a residual permutation in Sₙ, separating the case where 0 maps to 0 from the cases where 0 maps to a successor index (using a column cycle permutation to align the deleted row). The main theorem then deduces the row 0 expansion directly from the column 0 expansion by applying the transpose invariance of the permanent.

  1. The permanent of A is expressed as an iterated sum over the image index x ∈ Fin (n + 1) of 0 and the remaining permutation y ∈ Sₙ of the product of matrix entries.

    By definition, Matrix.permanent sums over all permutations σ ∈ Sₙ₊₁. Using Finset.univ_perm_fin_succ, the set of permutations of Fin (n + 1) is decomposed into pairs (x, y) ∈ Fin (n + 1) × Sₙ via Equiv.Perm.decomposeFin.symm, where x is the image of 0. Rewriting the product set into an iterated sum with Finset.sum_product and Finset.sum_map converts the permanent into a sum over x and y of the product of matrix entries along the permutation.

    lines 4–5

    uses Matrix.permanent, Finset.univ_perm_fin_succ, Finset.univ_product_univ, Finset.sum_map, Equiv.toEmbedding_apply, Finset.sum_product, Matrix.submatrix

      rw [Matrix.permanent, Finset.univ_perm_fin_succ, ← Finset.univ_product_univ]
      simp only [Finset.sum_map, Equiv.toEmbedding_apply, Finset.sum_product, Matrix.submatrix]
  2. It suffices to verify equality of the summands for each row index i ∈ Fin (n + 1), splitting into the base case i = 0 and successor cases i = succ(i').

    Using Finset.sum_congr, two sums over Finset.univ are equal if their corresponding summands match for each index i. Applying Fin.cases to i separates the proof into two cases: i = 0 (when the permutation maps 0 to 0) and i = succ(i') for some i' ∈ Fin n.

    line 6

    uses Finset.sum_congr, Fin.cases

      refine Finset.sum_congr rfl fun i _ => Fin.cases ?_ (fun i => ?_) i
  3. When i = 0, the sum over permutations in Sₙ equals A 0 0 times the permanent of the submatrix omitting row 0 and column 0.

    When i = 0, the reconstructed permutation sends 0 to 0 and each successor k + 1 to y(k) + 1 because the swap of 0 with 0 is the identity. Factoring the index 0 term out of the product with Fin.prod_univ_succ gives A 0 0, and factoring this scalar out of the sum using Finset.mul_sum leaves the sum over y ∈ Sₙ of the product over k of A (y(k) + 1) (k + 1). This is precisely the permanent of the submatrix omitting row 0 and column 0 (using Fin.succAbove_zero).

    lines 7–11

    uses Fin.prod_univ_succ, Matrix.permanent, Finset.mul_sum, Equiv.Perm.decomposeFin_symm_apply_zero, Equiv.swap_self, id, Equiv.Perm.decomposeFin_symm_apply_succ, Fin.succAbove_zero, Equiv.coe_refl, Matrix.of_apply

      · simp only [Fin.prod_univ_succ, Matrix.permanent, Finset.mul_sum,
          Equiv.Perm.decomposeFin_symm_apply_zero,
          Equiv.swap_self, id,
          Equiv.Perm.decomposeFin_symm_apply_succ, Fin.succAbove_zero, Equiv.coe_refl,
          Matrix.of_apply]
  4. When i = succ(i'), the sum over y ∈ Sₙ equals A (succ i') 0 times the permanent of the submatrix omitting row succ(i') and column 0.

    The permanent of the submatrix is unchanged if its columns are permuted by Fin.cycleRange i' (via Matrix.permanent_permute_cols). Distributing the factor A (succ i') 0 inside the sum with Finset.mul_sum, we compare summands for each permutation σ ∈ Sₙ. Factoring out the term at 0 yields A (succ i') 0, while Fin.succAbove_cycleRange identifies the remaining row indices swap(0, succ i')(succ(σ(k))) with succAbove(succ i')(cycleRange(i')(σ(k))), matching the column-permuted submatrix entries.

    lines 12–16

    uses Matrix.permanent_permute_cols, Fin.cycleRange, Matrix.permanent, Finset.mul_sum, Finset.sum_congr, Fin.prod_univ_succ, Fin.succAbove_cycleRange, Equiv.Perm.decomposeFin_symm_apply_zero, Equiv.Perm.decomposeFin_symm_apply_succ, Matrix.submatrix_apply, Matrix.of_apply, id

      · rw [← Matrix.permanent_permute_cols (Fin.cycleRange i), Matrix.permanent, Finset.mul_sum]
        refine Finset.sum_congr rfl fun σ _ => ?_
        simp only [Fin.prod_univ_succ, Fin.succAbove_cycleRange,
          Equiv.Perm.decomposeFin_symm_apply_zero, Equiv.Perm.decomposeFin_symm_apply_succ,
          Matrix.submatrix_apply, Matrix.of_apply, id]
  5. The permanent of A is rewritten as the column 0 expansion of its transpose Aᵀ, reducing the row 0 expansion to matching summands column by column.

    Since the permanent is invariant under matrix transposition (Matrix.permanent_transpose), A.permanent equals (Aᵀ).permanent. Expanding Aᵀ along column 0 using the auxiliary lemma matrix_permanent_succ_row_zero_column_zero gives a sum over columns j of Aᵀ j 0 times the permanent of the submatrix of Aᵀ omitting row j and column 0. Applying Finset.sum_congr reduces the claim to verifying that each summand matches index-wise.

    lines 22–23

    uses Matrix.permanent_transpose, matrix_permanent_succ_row_zero_column_zero, Finset.sum_congr

      rw [← Matrix.permanent_transpose A, matrix_permanent_succ_row_zero_column_zero]
      refine Finset.sum_congr rfl fun j _ => ?_
  6. Each summand in the transposed expansion simplifies to A 0 j times the permanent of the submatrix omitting row 0 and column j, concluding the proof.

    Applying Matrix.permanent_transpose to the submatrix permanent allows rewriting it as the permanent of its transpose. By Matrix.transpose_submatrix and Matrix.transpose_transpose, (Aᵀ.submatrix j.succAbove Fin.succ)ᵀ simplifies to A.submatrix Fin.succ j.succAbove, while Matrix.transpose_apply simplifies Aᵀ j 0 to A 0 j.

    lines 24–25

    uses Matrix.permanent_transpose, Matrix.transpose_apply, Matrix.transpose_submatrix, Matrix.transpose_transpose

      rw [← Matrix.permanent_transpose]
      simp only [Matrix.transpose_apply, Matrix.transpose_submatrix, Matrix.transpose_transpose]
Matrix.permanent
The permanent of an n × n matrix M, defined as the sum over all permutations σ of the product of entries M (σ i) i.
Finset.univ_perm_fin_succ
Every permutation of Fin (n + 1) can be uniquely decomposed via an equivalence into a pair in Fin (n + 1) × Perm (Fin n), where the first component is the image of 0.
Finset.univ_product_univ
The Cartesian product of the universal finsets of two finite types is the universal finset of the product type.
Finset.sum_map
Summing a function over the image of a finset under an embedding equals summing the composite function over the original finset.
Equiv.toEmbedding_apply
Coercing an equivalence to an embedding and evaluating it at an element is equal to applying the equivalence directly.
Finset.sum_product
A sum over a Cartesian product of two finsets equals the iterated sum over each finset.
Matrix.submatrix
Forms a submatrix by reindexing rows and columns via two given index mappings.
Finset.sum_congr
Two finite sums with identical index sets are equal if their summands agree at every element.
Fin.cases
Principle of case analysis on Fin (n + 1), splitting any index into 0 or the successor of some index in Fin n.
Fin.prod_univ_succ
A product over Fin (n + 1) factors into the term at index 0 multiplied by the product over all successor indices.
Finset.mul_sum
Left multiplication by a scalar distributes over a finite sum.
Equiv.Perm.decomposeFin_symm_apply_zero
The permutation reconstructed from (p, e) maps 0 to p.
Equiv.swap_self
Swapping an element with itself is the identity permutation.
id
The identity function, which maps every element to itself.
Equiv.Perm.decomposeFin_symm_apply_succ
The permutation reconstructed from (p, e) maps succ(x) to swap(0, p)(succ(e(x))).
Fin.succAbove_zero
The row-omission map Fin.succAbove 0 that skips 0 is equal to Fin.succ.
Equiv.coe_refl
The coercion of the identity equivalence to a function is the identity function id.
Matrix.of_apply
The entry of a matrix defined by a function f at (i, j) is f i j.
Matrix.permanent_permute_cols
Permuting the columns of a matrix by an arbitrary permutation leaves its permanent unchanged.
Fin.cycleRange
The permutation of Fin n that cyclically shifts the initial segment up to index i.
Fin.succAbove_cycleRange
Applying succAbove (succ i) to the column cycle permutation cycleRange(i)(j) equals swap(0, succ i)(succ j).
Matrix.submatrix_apply
The entry of a submatrix at (i, j) is the entry of the original matrix at the reindexed coordinates.
Matrix.permanent_transpose
The permanent of the transpose of a square matrix equals the permanent of the original matrix.
matrix_permanent_succ_row_zero_column_zero
The permanent of an (n+1) × (n+1) matrix equals the sum over all rows i of A i 0 times the permanent of the submatrix omitting row i and column 0.
Matrix.transpose_submatrix
The transpose of a submatrix with row map r and column map c is the submatrix of the transpose with row map c and column map r.
Matrix.transpose_transpose
Transposing a matrix twice yields the original matrix.
Matrix.transpose_apply
The (i, j) entry of the transpose matrix Mᵀ is the (j, i) entry of M.

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

theorem matrix_permanent_succ_row_zero_column_zero {n : ℕ} {R : Type*} [CommSemiring R]    (A : Matrix (Fin n.succ) (Fin n.succ) R) :    A.permanent = ∑ i : Fin n.succ, A i 0 * (A.submatrix i.succAbove Fin.succ).permanent := by  rw [Matrix.permanent, Finset.univ_perm_fin_succ, ← Finset.univ_product_univ]  simp only [Finset.sum_map, Equiv.toEmbedding_apply, Finset.sum_product, Matrix.submatrix]  refine Finset.sum_congr rfl fun i _ => Fin.cases ?_ (fun i => ?_) i  · simp only [Fin.prod_univ_succ, Matrix.permanent, Finset.mul_sum,      Equiv.Perm.decomposeFin_symm_apply_zero,      Equiv.swap_self, id,      Equiv.Perm.decomposeFin_symm_apply_succ, Fin.succAbove_zero, Equiv.coe_refl,      Matrix.of_apply]  · rw [← Matrix.permanent_permute_cols (Fin.cycleRange i), Matrix.permanent, Finset.mul_sum]    refine Finset.sum_congr rfl fun σ _ => ?_    simp only [Fin.prod_univ_succ, Fin.succAbove_cycleRange,      Equiv.Perm.decomposeFin_symm_apply_zero, Equiv.Perm.decomposeFin_symm_apply_succ,      Matrix.submatrix_apply, Matrix.of_apply, id]/-- Laplacian expansion of the permanent of an (n+1) x (n+1) matrix along row 0. -/theorem matrix_permanent_succ_row_zero {n : ℕ} {R : Type*} [CommSemiring R]    (A : Matrix (Fin n.succ) (Fin n.succ) R) :    A.permanent = ∑ j : Fin n.succ, A 0 j * (A.submatrix Fin.succ j.succAbove).permanent := by  rw [← Matrix.permanent_transpose A, matrix_permanent_succ_row_zero_column_zero]  refine Finset.sum_congr rfl fun j _ => ?_  rw [← Matrix.permanent_transpose]  simp only [Matrix.transpose_apply, Matrix.transpose_submatrix, Matrix.transpose_transpose]
See it in the graphDiscuss this resultChallenge it