matrix_permanent_succ_column
For 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 (n+1), the permanent of A equals the sum over all row indices i : Fin (n+1) of A i j times the permanent of the submatrix obtained by deleting row i and column j: A.permanent = ∑ i : Fin n.succ, A i j * (A.submatrix i.succAbove j.succAbove).permanent.
Statement
theorem matrix_permanent_succ_column {n : ℕ} {R : Type*} [CommSemiring R] (A : Matrix (Fin n.succ) (Fin n.succ) R) (j : Fin n.succ) : A.permanent = ∑ i : Fin n.succ, A i j * (A.submatrix i.succAbove j.succAbove).permanent
- Formalizes
- Minc, Permanents, Encyclopedia of Mathematics and its Applications, Addison-Wesley, 1978, Section 1.2
- Verified
- 08 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 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 any natural number $n$, any commutative semiring $R$, any $(n+1) \times (n+1)$ matrix $A$ with entries in $R$, and any column index $j \in \mathrm{Fin}(n+1)$, the permanent of $A$ equals the sum over all row indices $i \in \mathrm{Fin}(n+1)$ of $A_{i, j}$ multiplied by the permanent of the $n \times n$ submatrix 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 column expansion formula for the permanent is derived from the row expansion formula by transposition. Because transposition preserves the permanent, expanding the permanent of A along column j is equivalent to expanding the permanent of Aᵀ along row j. Comparing the two expansions term by term, each scalar entry (Aᵀ) j i matches A i j, and the resulting minor of Aᵀ is the transpose of the corresponding minor of A, which therefore has the same permanent.
The permanent of A equals the row expansion of Aᵀ along row j.
Because transposition preserves the permanent (Matrix.permanent_transpose), we rewrite the permanent of A as the permanent of Aᵀ. Applying row expansion along row j to Aᵀ (matrix_permanent_succ_row) expresses this permanent as the sum over i of (Aᵀ) j i times the permanent of the minor of Aᵀ deleting row j and column i.
uses
Matrix.permanent_transpose,matrix_permanent_succ_rowrw [← Matrix.permanent_transpose A] rw [matrix_permanent_succ_row A.transpose j]
It suffices to show that the minor of Aᵀ deleting row j and column i has the same permanent as the minor of A deleting row i and column j.
By Finset.sum_congr, the two sums are equal if their corresponding terms agree for each row index i. Transposition swaps indices, so (Aᵀ) j i = A i j by Matrix.transpose_apply. Removing this matching scalar factor (congr 1) reduces the goal to showing that the permanents of the respective submatrices are equal.
uses
Finset.sum_congr,Matrix.transpose_applyrefine Finset.sum_congr rfl fun i _ => ?_ simp only [Matrix.transpose_apply] congr 1
The permanent of the submatrix of Aᵀ deleting row j and column i equals the permanent of the submatrix of A deleting row i and column j.
Using Matrix.permanent_transpose, the permanent of the submatrix of A deleting row i and column j is equal to the permanent of its transpose. By Matrix.transpose_submatrix, transposing this submatrix yields precisely the submatrix of Aᵀ deleting row j and column i, which closes the goal.
uses
Matrix.permanent_transpose,Matrix.transpose_submatrixrw [← Matrix.permanent_transpose (A.submatrix i.succAbove j.succAbove)] rw [Matrix.transpose_submatrix]
Matrix.permanent_transpose- The permanent of the transpose of a square matrix equals the permanent of the original matrix.
matrix_permanent_succ_row- Laplace row expansion for the permanent: the permanent of an (n+1) × (n+1) matrix equals the sum along any row of each entry times the permanent of the corresponding minor.
Finset.sum_congr- Two finite sums are equal if their index sets are identical and their terms are equal at every element.
Matrix.transpose_apply- The entry at (i, j) of the transpose of a matrix is the entry at (j, i) of the original matrix.
Matrix.transpose_submatrix- The transpose of a submatrix formed by row map r and column map c equals the submatrix of the transpose formed by swapping r and c.
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.
/-- Laplace column expansion for the permanent over a commutative semiring. -/theorem matrix_permanent_succ_column {n : ℕ} {R : Type*} [CommSemiring R] (A : Matrix (Fin n.succ) (Fin n.succ) R) (j : Fin n.succ) : A.permanent = ∑ i : Fin n.succ, A i j * (A.submatrix i.succAbove j.succAbove).permanent := by rw [← Matrix.permanent_transpose A] rw [matrix_permanent_succ_row A.transpose j] refine Finset.sum_congr rfl fun i _ => ?_ simp only [Matrix.transpose_apply] congr 1 rw [← Matrix.permanent_transpose (A.submatrix i.succAbove j.succAbove)] rw [Matrix.transpose_submatrix]