AFTD Auto-Formalizing Theoretical Domains

matrix_permanent_succ_column

theoremverifiedformalization

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.

  1. 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.

    lines 5–6

    uses Matrix.permanent_transpose, matrix_permanent_succ_row

      rw [← Matrix.permanent_transpose A]
      rw [matrix_permanent_succ_row A.transpose j]
  2. 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.

    lines 7–9

    uses Finset.sum_congr, Matrix.transpose_apply

      refine Finset.sum_congr rfl fun i _ => ?_
      simp only [Matrix.transpose_apply]
      congr 1
  3. 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.

    lines 10–11

    uses Matrix.permanent_transpose, Matrix.transpose_submatrix

      rw [← 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

/-- 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]
See it in the graphDiscuss this resultChallenge it