matrix_permanent_from_blocks_zero_one_two
For 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 in the top-right, C in the bottom-left, and D in the bottom-right equals the permanent of A times the permanent of D.
Statement
theorem matrix_permanent_from_blocks_zero_one_two {m n R : Type*} [DecidableEq m] [DecidableEq n] [Fintype m] [Fintype n] [CommSemiring R] (A : Matrix m m R) (C : Matrix n m R) (D : Matrix n n R) : (Matrix.fromBlocks A 0 C D).permanent = A.permanent * D.permanent
- Related work
- Mathlib.LinearAlgebra.Matrix.Block
- Verified
- 20 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 2
- matrix_permanent_from_blocks_anti_diagonalFor 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…
- latin_double_three_tail_permanent_of_profileA filling with the canonical column profile has exactly four legal permutations for a new top row of length k+1.
Read back from the Lean
For all types $m$, $n$, and $R$ such that $m$ and $n$ have decidable equality and are finite types, and $R$ is a commutative semiring, and for any matrices $A : \mathrm{Matrix}\ m\ m\ R$, $C : \mathrm{Matrix}\ n\ m\ R$, and $D : \mathrm{Matrix}\ n\ n\ R$, the permanent of the lower block-triangular matrix $\begin{pmatrix} A & 0 \\ C & D \end{pmatrix}$ (formed by Matrix.fromBlocks A 0 C D with row and column index type $m \oplus n$) is equal to the product of the permanent of $A$ and the permanent of $D$.
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 is proved by first establishing that the permanent of a block upper-triangular matrix with zero in the bottom-left position equals the product of the permanents of its diagonal blocks, and then deducing the lower-triangular case by transposition. For the upper-triangular case, the sum over all permutations of m ⊕ n reduces to the subgroup of block-preserving permutations, because any permutation mapping an element of the first block into the second block encounters a zero entry in the bottom-left block. Evaluating the product on these block-preserving permutations splits each term into independent products over the two diagonal blocks.
The permanent of the block upper-triangular matrix equals the sum of entry products over the subgroup of permutations preserving the block structure.
Unfolding the definition of the permanent (`Matrix.permanent`), the permanent of the block matrix is the sum over all permutations of m ⊕ n. By `Finset.sum_subset`, since the subgroup of block-preserving permutations (the image of `Equiv.Perm.sumCongrHom`) is contained in all permutations, it suffices to prove two subgoals: first, that the sum over this subgroup equals the product of permanents, and second, that all permutations outside the subgroup have product zero.
uses
Matrix.permanent,Eq.symm,Finset.sum_subset,Finset.subset_univ,Equiv.Perm.sumCongrHomclassical simp_rw [Matrix.permanent] convert! Eq.symm <| Finset.sum_subset (M := R) (Finset.subset_univ ((Equiv.Perm.sumCongrHom m n).range : Set (Equiv.Perm (m ⊕ n))).toFinset) ?_The product of the permanents of A and D is rewritten as a sum over pairs of permutations, mapped into the block-preserving permutations.
We expand the product of sums `perm(A) * perm(D)` into a single sum over pairs (σ₁, σ₂) ∈ Sₘ × Sₙ via `Finset.sum_mul_sum`, `Finset.sum_product'`, and `Finset.univ_product_univ`. We then apply `Finset.sum_nbij` with the direct sum map (σ₁, σ₂) ↦ σ₁ ⊕ σ₂, showing first that this map lands in the range of `sumCongrHom`.
uses
Finset.sum_mul_sum,Finset.sum_product',Finset.univ_product_univ,Finset.sum_nbij,Set.mem_toFinset· simp_rw [Finset.sum_mul_sum, ← Finset.sum_product', Finset.univ_product_univ] refine Finset.sum_nbij (fun σ ↦ σ.fst.sumCongr σ.snd) ?_ ?_ ?_ ?_ · intro σ₁₂ _ rw [Set.mem_toFinset] exact ⟨σ₁₂, rfl⟩The direct sum map from pairs of permutations into permutations of m ⊕ n is injective.
If σ₁ ⊕ σ₂ = τ₁ ⊕ τ₂, then evaluating both sides on left injections `Sum.inl` implies σ₁ = τ₁, and evaluating on right injections `Sum.inr` implies σ₂ = τ₂. Equality of the pairs follows by extensionality.
uses
DFunLike.congr_fun,Sum.map_inr,Sum.map_inl,Equiv.Perm.sumCongr_apply,Sum.forall,Sum.inl.injEq,Sum.inr.injEq· intro σ₁ _ σ₂ _ dsimp only intro h have h2 : ∀ x, Equiv.Perm.sumCongr σ₁.fst σ₁.snd x = Equiv.Perm.sumCongr σ₂.fst σ₂.snd x := DFunLike.congr_fun h simp only [Sum.map_inr, Sum.map_inl, Equiv.Perm.sumCongr_apply, Sum.forall, Sum.inl.injEq, Sum.inr.injEq] at h2 ext x · exact h2.left x · exact h2.right x
The direct sum map is surjective onto the range of `sumCongrHom`.
By definition of the range of the homomorphism `Equiv.Perm.sumCongrHom`, any permutation in the range is of the form σ₁ ⊕ σ₂ for some pair of permutations.
uses
Finset.mem_coe,Set.mem_toFinset· intro σ hσ rw [Finset.mem_coe, Set.mem_toFinset] at hσ obtain ⟨σ₁₂, hσ₁₂⟩ := hσ use σ₁₂ rw [← hσ₁₂] simp
For any pair of permutations (σ₁, σ₂), the product of entries of the block matrix under σ₁ ⊕ σ₂ equals the product of entries of A under σ₁ times the product of entries of D under σ₂.
The product over m ⊕ n factors into a product over m and a product over n by `Fintype.prod_sum_type`. Under the direct sum permutation, elements in m map to m with entries from the top-left block A (`Matrix.fromBlocks_apply₁₁`), and elements in n map to n with entries from the bottom-right block D (`Matrix.fromBlocks_apply₂₂`).
uses
forall_prop_of_true,Prod.forall,Finset.mem_univ,Fintype.prod_sum_type,Equiv.sumCongr_apply,Sum.map_inr,Sum.map_inl,Matrix.fromBlocks_apply₁₁,Matrix.fromBlocks_apply₂₂· simp only [forall_prop_of_true, Prod.forall, Finset.mem_univ] intro σ₁ σ₂ rw [Fintype.prod_sum_type] simp_rw [Equiv.sumCongr_apply, Sum.map_inr, Sum.map_inl, Matrix.fromBlocks_apply₁₁, Matrix.fromBlocks_apply₂₂]
Any permutation outside the image of `sumCongrHom` must map some element of m to an element of n.
By `Equiv.Perm.mem_sumCongrHom_range_of_perm_mapsTo_inl`, any permutation of m ⊕ n on finite types that maps the range of `Sum.inl` into itself must belong to the image of `sumCongrHom`. Taking the contrapositive via modus tollens (`mt`), a permutation outside this subgroup cannot preserve the range of `Sum.inl`.
uses
Set.mem_toFinset,Set.MapsTo,Set.mem_range,forall_exists_index,forall_apply_eq_imp_iff,mt,Equiv.Perm.mem_sumCongrHom_range_of_perm_mapsTo_inl· rintro σ - hσn have h1 : ¬∀ x, ∃ y, Sum.inl y = σ (Sum.inl x) := by rw [Set.mem_toFinset] at hσn simpa only [Set.MapsTo, Set.mem_range, forall_exists_index, forall_apply_eq_imp_iff] using mt Equiv.Perm.mem_sumCongrHom_range_of_perm_mapsTo_inl hσnAny permutation outside the image of `sumCongrHom` yields a product of zero.
Since σ does not preserve m, there exists an element a ∈ m whose image under σ is not in the range of `Sum.inl`, meaning σ(Sum.inl a) = Sum.inr b for some b ∈ n. At this position, the matrix entry comes from the bottom-left block, which is zero (`Matrix.fromBlocks_apply₂₁` and `Matrix.zero_apply`). Since one factor is zero, the entire product is zero by `Finset.prod_eq_zero`.
uses
not_forall.mp,not_exists.mp,absurd,Finset.prod_eq_zero,Finset.mem_univ,Matrix.fromBlocks_apply₂₁,Matrix.zero_applyobtain ⟨a, ha⟩ := not_forall.mp h1 rcases hx : σ (Sum.inl a) with a2 | b · have hn := (not_exists.mp ha) a2 exact absurd hx.symm hn · rw [Finset.prod_eq_zero (Finset.mem_univ (Sum.inl a))] rw [hx, Matrix.fromBlocks_apply₂₁, Matrix.zero_apply]
The permanent of a block lower-triangular matrix equals the product of the permanents of its diagonal blocks.
Transposing the block lower-triangular matrix yields a block upper-triangular matrix whose bottom-left block is zero (`Matrix.fromBlocks_transpose` and `Matrix.transpose_zero`). Since matrix transposition preserves the permanent (`Matrix.permanent_transpose`), applying `matrix_permanent_from_blocks_zero_one_two_zero_two_one` to the transposed matrix gives perm(Aᵀ) * perm(Dᵀ) = perm(A) * perm(D).
uses
Matrix.permanent_transpose,Matrix.fromBlocks_transpose,Matrix.transpose_zero,matrix_permanent_from_blocks_zero_one_two_zero_two_onerw [← Matrix.permanent_transpose, Matrix.fromBlocks_transpose, Matrix.transpose_zero, matrix_permanent_from_blocks_zero_one_two_zero_two_one, Matrix.permanent_transpose, Matrix.permanent_transpose]
absurd- From a contradiction (both a proposition and its negation), any proposition follows.
DFunLike.congr_fun- If two functions or permutations are equal, their values agree on every argument: f = g → ∀ x, f x = g x.
Eq.symm- Symmetry of equality: if a = b, then b = a.
Equiv.Perm.sumCongr_apply- The direct sum permutation σ₁ ⊕ σ₂ acts by applying σ₁ on left injections and σ₂ on right injections.
Equiv.Perm.sumCongrHom- The group homomorphism embedding Perm(α) × Perm(β) into Perm(α ⊕ β) by componentwise action.
Equiv.Perm.mem_sumCongrHom_range_of_perm_mapsTo_inl- On finite types, any permutation of α ⊕ β that maps the range of Sum.inl into itself lies in the image of sumCongrHom.
Equiv.sumCongr_apply- The direct sum of equivalences on a sum type acts componentwise via Sum.map.
Finset.mem_coe- An element belongs to the coercion of a finset to a set if and only if it belongs to the finset.
Finset.mem_univ- Every element of a finite type belongs to the universal finset Finset.univ.
Finset.prod_eq_zero- A finite product is zero if one of its factors is zero.
Finset.subset_univ- Every finset on a finite type is a subset of the universal finset Finset.univ.
Finset.sum_mul_sum- The product of two finite sums equals the double sum of pairwise products: (∑ i, f i) * (∑ j, g j) = ∑ i, ∑ j, f i * g j.
Finset.sum_nbij- Two sums over finite sets are equal if their index sets are in bijection and the bijection preserves the values of the summands.
Finset.sum_product'- A sum over a Cartesian product of finsets equals the iterated sum over each component finset.
Finset.sum_subset- A sum over a finset equals the sum over a subset if all terms outside the subset vanish.
Finset.univ_product_univ- The Cartesian product of two universal finsets is the universal finset of the product type.
Fintype.prod_sum_type- A product over a sum type α₁ ⊕ α₂ factors into the product over α₁ times the product over α₂.
Matrix.fromBlocks_apply₁₁- The (inl i, inl j) entry of a 2 × 2 block matrix is the (i, j) entry of the top-left block A.
Matrix.fromBlocks_apply₂₁- The (inr i, inl j) entry of a 2 × 2 block matrix is the (i, j) entry of the bottom-left block C.
Matrix.fromBlocks_apply₂₂- The (inr i, inr j) entry of a 2 × 2 block matrix is the (i, j) entry of the bottom-right block D.
Matrix.fromBlocks_transpose- The transpose of a 2 × 2 block matrix transposes each block and swaps the off-diagonal blocks.
Matrix.permanent- The permanent of a square matrix M, defined as the sum over all permutations σ of the product of entries ∏ i, M (σ i) i.
Matrix.permanent_transpose- Transposing a matrix preserves its permanent: perm(Mᵀ) = perm(M).
Matrix.transpose_zero- The transpose of the zero matrix is the zero matrix.
Matrix.zero_apply- Every entry of the zero matrix is zero: 0 i j = 0.
matrix_permanent_from_blocks_zero_one_two_zero_two_one- The permanent of a block upper-triangular matrix with zero in the bottom-left position equals the product of the permanents of the diagonal blocks.
mt- Modus tollens: from a → b and ¬b, infer ¬a.
not_exists.mp- If a property does not have a witness, it is false for all elements: (¬∃ x, p x) → ∀ x, ¬p x.
not_forall.mp- If a property does not hold for all elements, there exists a counterexample: (¬∀ x, p x) → ∃ x, ¬p x.
forall_prop_of_true- Universal quantification over a true proposition is equivalent to evaluating the proposition at that truth.
forall_apply_eq_imp_iff- Quantifying over values equal to an application reduces to evaluating the property at the application: (∀ b a, f a = b → p b) ↔ ∀ a, p (f a).
forall_exists_index- Quantifying over an existential hypothesis is equivalent to quantifying over the witness and the property.
Set.MapsTo- A function maps a set into a set: MapsTo f s t means ∀ x ∈ s, f x ∈ t.
Set.mem_range- An element belongs to the range of a function f if and only if it is the image of some argument.
Set.mem_toFinset- An element belongs to the finset of a set with finite type if and only if it belongs to the set.
Sum.forall- Universal quantification over a sum type α ⊕ β is equivalent to universal quantification over α and over β.
Sum.inl.injEq- The left inclusion Sum.inl is injective: Sum.inl x = Sum.inl y ↔ x = y.
Sum.inr.injEq- The right inclusion Sum.inr is injective: Sum.inr x = Sum.inr y ↔ x = y.
Sum.map_inl- Sum.map f g applied to a left injection Sum.inl x yields Sum.inl (f x).
Sum.map_inr- Sum.map f g applied to a right injection Sum.inr x yields Sum.inr (g x).
Prod.forall- Universal quantification over a product type α × β is equivalent to universal quantification over both components.
- The helper theorem `matrix_permanent_from_blocks_zero_one_two_zero_two_one` establishes the identity for block upper-triangular matrices with the zero block in the bottom-left position. The main theorem `matrix_permanent_from_blocks_zero_one_two` for block lower-triangular matrices is then proved directly in three lines using matrix transposition.
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_from_blocks_zero_one_two_zero_two_one {m n R : Type*} [DecidableEq m] [DecidableEq n] [Fintype m] [Fintype n] [CommSemiring R] (A : Matrix m m R) (B : Matrix m n R) (D : Matrix n n R) : (Matrix.fromBlocks A B 0 D).permanent = A.permanent * D.permanent := by classical simp_rw [Matrix.permanent] convert! Eq.symm <| Finset.sum_subset (M := R) (Finset.subset_univ ((Equiv.Perm.sumCongrHom m n).range : Set (Equiv.Perm (m ⊕ n))).toFinset) ?_ · simp_rw [Finset.sum_mul_sum, ← Finset.sum_product', Finset.univ_product_univ] refine Finset.sum_nbij (fun σ ↦ σ.fst.sumCongr σ.snd) ?_ ?_ ?_ ?_ · intro σ₁₂ _ rw [Set.mem_toFinset] exact ⟨σ₁₂, rfl⟩ · intro σ₁ _ σ₂ _ dsimp only intro h have h2 : ∀ x, Equiv.Perm.sumCongr σ₁.fst σ₁.snd x = Equiv.Perm.sumCongr σ₂.fst σ₂.snd x := DFunLike.congr_fun h simp only [Sum.map_inr, Sum.map_inl, Equiv.Perm.sumCongr_apply, Sum.forall, Sum.inl.injEq, Sum.inr.injEq] at h2 ext x · exact h2.left x · exact h2.right x · intro σ hσ rw [Finset.mem_coe, Set.mem_toFinset] at hσ obtain ⟨σ₁₂, hσ₁₂⟩ := hσ use σ₁₂ rw [← hσ₁₂] simp · simp only [forall_prop_of_true, Prod.forall, Finset.mem_univ] intro σ₁ σ₂ rw [Fintype.prod_sum_type] simp_rw [Equiv.sumCongr_apply, Sum.map_inr, Sum.map_inl, Matrix.fromBlocks_apply₁₁, Matrix.fromBlocks_apply₂₂] · rintro σ - hσn have h1 : ¬∀ x, ∃ y, Sum.inl y = σ (Sum.inl x) := by rw [Set.mem_toFinset] at hσn simpa only [Set.MapsTo, Set.mem_range, forall_exists_index, forall_apply_eq_imp_iff] using mt Equiv.Perm.mem_sumCongrHom_range_of_perm_mapsTo_inl hσn obtain ⟨a, ha⟩ := not_forall.mp h1 rcases hx : σ (Sum.inl a) with a2 | b · have hn := (not_exists.mp ha) a2 exact absurd hx.symm hn · rw [Finset.prod_eq_zero (Finset.mem_univ (Sum.inl a))] rw [hx, Matrix.fromBlocks_apply₂₁, Matrix.zero_apply]/-- The permanent of a block lower-triangular matrix is the product of the permanents of the diagonal blocks. -/theorem matrix_permanent_from_blocks_zero_one_two {m n R : Type*} [DecidableEq m] [DecidableEq n] [Fintype m] [Fintype n] [CommSemiring R] (A : Matrix m m R) (C : Matrix n m R) (D : Matrix n n R) : (Matrix.fromBlocks A 0 C D).permanent = A.permanent * D.permanent := by rw [← Matrix.permanent_transpose, Matrix.fromBlocks_transpose, Matrix.transpose_zero, matrix_permanent_from_blocks_zero_one_two_zero_two_one, Matrix.permanent_transpose, Matrix.permanent_transpose]