matrix_permanent_succ_row
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.
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.
uses
Matrix.permanent_permute_cols,matrix_permanent_succ_row_zerorw [← Matrix.permanent_permute_cols i.cycleRange⁻¹, matrix_permanent_succ_row_zero]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`.
uses
Finset.sum_congr,Matrix.submatrix_apply,Matrix.submatrix_submatrix,Equiv.Perm.inv_defrefine Finset.sum_congr rfl fun j _ => ?_ simp only [Matrix.submatrix_apply, Matrix.submatrix_submatrix, Equiv.Perm.inv_def]
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.
uses
Fin.cycleRange_symm_zero,Fin.cycleRange_symm_succhave 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).
- Despite its name mentioning columns, the lemma `Matrix.permanent_permute_cols` actually permutes the rows of the matrix, as shown by its type `(M.submatrix (⇑σ) id).permanent = M.permanent`.
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.
/-- 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