matrix_permanent_succ_row_zero
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.
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.
uses
Matrix.permanent,Finset.univ_perm_fin_succ,Finset.univ_product_univ,Finset.sum_map,Equiv.toEmbedding_apply,Finset.sum_product,Matrix.submatrixrw [Matrix.permanent, Finset.univ_perm_fin_succ, ← Finset.univ_product_univ] simp only [Finset.sum_map, Equiv.toEmbedding_apply, Finset.sum_product, Matrix.submatrix]
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.
uses
Finset.sum_congr,Fin.casesrefine Finset.sum_congr rfl fun i _ => Fin.cases ?_ (fun i => ?_) i
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).
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]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.
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]
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.
uses
Matrix.permanent_transpose,matrix_permanent_succ_row_zero_column_zero,Finset.sum_congrrw [← Matrix.permanent_transpose A, matrix_permanent_succ_row_zero_column_zero] refine Finset.sum_congr rfl fun j _ => ?_
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.
uses
Matrix.permanent_transpose,Matrix.transpose_apply,Matrix.transpose_submatrix,Matrix.transpose_transposerw [← 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.
- The column 0 expansion in `matrix_permanent_succ_row_zero_column_zero` relies on an algebraic alignment using `Fin.cycleRange i`, which cyclically permutes the submatrix columns so that the permutation action `Equiv.swap 0 (Fin.succ i)` aligns with the submatrix row deletion map `Fin.succAbove (Fin.succ 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
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.
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]