AFTD Auto-Formalizing Theoretical Domains

matrix_permanent_from_blocks_anti_diagonal

theoremverifiedformalization

For any commutative semiring R, any finite type n with decidable equality, and any square matrices B and C of size n x n over R, the permanent of the block matrix with 0 in the top-left block, B in the top-right block, C in the bottom-left block, and 0 in the bottom-right block equals the product of the permanent of B and the permanent of C: (Matrix.fromBlocks (0 : Matrix n n R) B C 0).permanent = B.permanent * C.permanent.

Statement

theorem matrix_permanent_from_blocks_anti_diagonal {n : Type*} [DecidableEq n] [Fintype n]
    {R : Type*} [CommSemiring R] (B C : Matrix n n R) :
    (Matrix.fromBlocks (0 : Matrix n n R) B C 0).permanent = B.permanent * C.permanent
Formalizes
Minc, Permanents (1978), Chapter 2; Valiant, Completeness classes in algebra (1979)
Verified
08 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1

Read back from the Lean

For every finite type $n$ with decidable equality, every commutative semiring $R$, and any two $n \times n$ matrices $B$ and $C$ over $R$, the permanent of the block matrix $\begin{pmatrix} 0 & B \\ C & 0 \end{pmatrix}$ (constructed via Matrix.fromBlocks 0 B C 0) is equal to the product of the permanent of $B$ and the permanent of $C$ (B.permanent * C.permanent).

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 proof evaluates the permanent of an anti-diagonal block matrix by swapping its two row blocks to convert it into a block diagonal matrix. Since permuting rows preserves the permanent, the permanent of the original matrix equals that of the resulting block matrix with diagonal blocks C and B. The claim then follows from the formula for the permanent of a block matrix with a zero upper-right block and the commutativity of multiplication.

  1. Permuting the row blocks of the block anti-diagonal matrix does not change its permanent.

    Applying Matrix.permanent_permute_cols with the equivalence Equiv.sumComm n n (which interchanges the two copies of n) shows that the permanent of the block matrix with blocks 0, B, C, 0 equals the permanent of the submatrix obtained by swapping the row blocks.

    lines 5–7

    uses Matrix.permanent_permute_cols

      have h1 : (Matrix.fromBlocks (0 : Matrix n n R) B C 0).permanent =
          ((Matrix.fromBlocks (0 : Matrix n n R) B C 0).submatrix (Equiv.sumComm n n) id).permanent := by
        rw [Matrix.permanent_permute_cols (Equiv.sumComm n n)]
  2. Swapping the row blocks of the anti-diagonal matrix yields the block diagonal matrix with diagonal blocks C and B.

    By matrix extensionality, we compare entries across the four combinations of row and column blocks (Sum.inl and Sum.inr). In each of the four cases, unfolding the definition of Matrix.fromBlocks verifies that swapping the row blocks via Equiv.sumComm moves block C to the top-left and block B to the bottom-right, while the off-diagonal blocks become 0.

    lines 8–10

    uses Matrix.fromBlocks

      have h2 : (Matrix.fromBlocks (0 : Matrix n n R) B C 0).submatrix (Equiv.sumComm n n) id =
          Matrix.fromBlocks C 0 0 B := by
        ext (i | i) (j | j) <;> simp [Matrix.fromBlocks]
  3. The permanent of the anti-diagonal block matrix equals the product of the permanents of B and C.

    Rewriting by the two previous equalities replaces the permanent of the anti-diagonal matrix with the permanent of the block matrix with diagonal blocks C and B (and upper-right block 0). By matrix_permanent_from_blocks_zero_one_two, this permanent equals perm(C) * perm(B), which equals perm(B) * perm(C) by commutativity of multiplication (mul_comm).

    line 11

    uses matrix_permanent_from_blocks_zero_one_two, mul_comm

      rw [h1, h2, matrix_permanent_from_blocks_zero_one_two, mul_comm]
Matrix.permanent_permute_cols
Permuting the rows of a square matrix by an equivalence σ via submatrix σ id preserves its permanent.
Matrix.fromBlocks
Forms a block matrix from four submatrices indexed by sum types of rows and columns.
matrix_permanent_from_blocks_zero_one_two
The permanent of a block matrix with a zero upper-right block equals the product of the permanents of its diagonal blocks: perm (fromBlocks A 0 C D) = perm(A) * perm(D).
mul_comm
Multiplication is commutative: a * b = b * a.

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

/-- The permanent of a block anti-diagonal matrix with square blocks equals the product of the permanents of the off-diagonal blocks. -/theorem matrix_permanent_from_blocks_anti_diagonal {n : Type*} [DecidableEq n] [Fintype n]    {R : Type*} [CommSemiring R] (B C : Matrix n n R) :    (Matrix.fromBlocks (0 : Matrix n n R) B C 0).permanent = B.permanent * C.permanent := by  have h1 : (Matrix.fromBlocks (0 : Matrix n n R) B C 0).permanent =      ((Matrix.fromBlocks (0 : Matrix n n R) B C 0).submatrix (Equiv.sumComm n n) id).permanent := by    rw [Matrix.permanent_permute_cols (Equiv.sumComm n n)]  have h2 : (Matrix.fromBlocks (0 : Matrix n n R) B C 0).submatrix (Equiv.sumComm n n) id =      Matrix.fromBlocks C 0 0 B := by    ext (i | i) (j | j) <;> simp [Matrix.fromBlocks]  rw [h1, h2, matrix_permanent_from_blocks_zero_one_two, mul_comm]
See it in the graphDiscuss this resultChallenge it