AFTD Auto-Formalizing Theoretical Domains

matrix_permanent_from_blocks_zero_one_two

theoremverifiedoriginal

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

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.

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

    lines 5–9

    uses Matrix.permanent, Eq.symm, Finset.sum_subset, Finset.subset_univ, Equiv.Perm.sumCongrHom

      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) ?_
  2. 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`.

    lines 10–14

    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⟩
  3. 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.

    lines 15–24

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

    lines 25–30

    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
  5. 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₂₂`).

    lines 31–35

    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₂₂]
  6. 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`.

    lines 36–40

    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σn
  7. Any 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`.

    lines 41–46

    uses not_forall.mp, not_exists.mp, absurd, Finset.prod_eq_zero, Finset.mem_univ, Matrix.fromBlocks_apply₂₁, Matrix.zero_apply

        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]
  8. 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).

    lines 50–52

    uses Matrix.permanent_transpose, Matrix.fromBlocks_transpose, Matrix.transpose_zero, matrix_permanent_from_blocks_zero_one_two_zero_two_one

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

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

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