matrix_permanent_from_blocks_anti_diagonal
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
- matrix_permanent_from_blocks_zero_one_twoFor any commutative semiring R and any square matrices A over m and D over n, the permanent of the block matrix with A in the top-left, 0…
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.
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.
uses
Matrix.permanent_permute_colshave 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)]
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.
uses
Matrix.fromBlockshave 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]
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).
uses
matrix_permanent_from_blocks_zero_one_two,mul_commrw [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.
- Despite its name, the lemma Matrix.permanent_permute_cols asserts that M.submatrix σ id has the same permanent as M; because the first index of submatrix acts on rows, this actually permutes row blocks rather than column blocks.
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.
/-- 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]