AFTD Auto-Formalizing Theoretical Domains

matrix_permanent_from_blocks_anti_diagonal_of_ne_card

theoremverifiedformalization

For any commutative semiring R, any finite types m and n with decidable equality such that the cardinality of m does not equal the cardinality of n, and any matrices B : Matrix m n R and C : Matrix n m R, the permanent of the block matrix Matrix.fromBlocks (0 : Matrix m m R) B C 0 equals 0.

Statement

theorem matrix_permanent_from_blocks_anti_diagonal_of_ne_card {m n R : Type*}
    [DecidableEq m] [DecidableEq n] [Fintype m] [Fintype n] [CommSemiring R]
    (hm : Fintype.card m ≠ Fintype.card n) (B : Matrix m n R) (C : Matrix n m R) :
    (Matrix.fromBlocks (0 : Matrix m m R) B C 0).permanent = 0
Formalizes
Minc, Permanents (1978); Valiant, Completeness classes in algebra (1979)
Verified
08 Oct 2026
Axioms
Classical.choiceQuot.soundpropext

Read back from the Lean

For all types m, n, and R such that m and n have decidable equality and are finite, and R is a commutative semiring: if the cardinalities of m and n are unequal (Fintype.card m ≠ Fintype.card n), then for any m × n matrix B over R and any n × m matrix C over R, the permanent of the block matrix $\begin{pmatrix} 0 & B \\ C & 0 \end{pmatrix}$ (indexed by m ⊕ n) is equal to 0.

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 proceeds by showing that every term in the sum defining the permanent of the block matrix is zero. For any permutation σ of the disjoint union m ⊕ n, if the product of matrix entries along σ were non-zero, no entry could lie in the zero diagonal blocks. This forces σ to map all indices of m into n and all indices of n into m, yielding injections between m and n in both directions and implying |m| = |n|. Since the cardinalities of m and n are assumed unequal, every permutation yields a zero product, and thus the permanent vanishes.

  1. Assuming for contradiction that the product along a permutation σ does not vanish, no entry along σ can be zero.

    To establish that ∏ i, M (σ i) i = 0 for every permutation σ, we assume for contradiction that the product is non-zero. If any single factor in the product over m ⊕ n were zero, the entire product would vanish by Finset.prod_eq_zero. Thus, every factor M (σ x) x must be non-zero.

    lines 6–12

    uses Finset.prod_eq_zero, Finset.mem_univ

      have h_prod (σ : Equiv.Perm (m ⊕ n)) :
          ∏ i : m ⊕ n, (Matrix.fromBlocks (0 : Matrix m m R) B C 0) (σ i) i = 0 := by
        by_contra h_ne
        have h_none : ∀ x, (Matrix.fromBlocks (0 : Matrix m m R) B C 0) (σ x) x ≠ 0 := by
          intro x hx
          apply h_ne
          exact Finset.prod_eq_zero (Finset.mem_univ x) hx
  2. The permutation σ maps every index in m to an index in n.

    For any index i ∈ m, we check whether σ(i) falls in m or n. If σ(i) were in m, the entry M (σ(i)) i would lie in the top-left block of the block matrix, which is the zero matrix 0_{m × m} by Matrix.fromBlocks_apply₁₁. This would make the entry zero, contradicting the fact that no factor along σ can be zero. Hence σ(i) must fall in n.

    lines 13–23

    uses Matrix.fromBlocks_apply₁₁

        have h1 : ∀ i : m, ∃ b : n, σ (Sum.inl i) = Sum.inr b := by
          intro i
          cases h_case : σ (Sum.inl i) with
          | inl a =>
            exfalso
            have h_zero : (Matrix.fromBlocks (0 : Matrix m m R) B C 0) (σ (Sum.inl i)) (Sum.inl i) = 0 := by
              rw [h_case, Matrix.fromBlocks_apply₁₁]
              rfl
            exact h_none (Sum.inl i) h_zero
          | inr b =>
            exact ⟨b, rfl⟩
  3. The permutation σ maps every index in n to an index in m.

    Similarly, for any index j ∈ n, we check whether σ(j) falls in m or n. If σ(j) were in n, the entry M (σ(j)) j would lie in the bottom-right block, which is 0_{n × n} by Matrix.fromBlocks_apply₂₂. That would again produce a zero entry, contradicting the non-vanishing assumption. Therefore, σ(j) must fall in m.

    lines 24–34

    uses Matrix.fromBlocks_apply₂₂

        have h2 : ∀ j : n, ∃ a : m, σ (Sum.inr j) = Sum.inl a := by
          intro j
          cases h_case : σ (Sum.inr j) with
          | inl a =>
            exact ⟨a, rfl⟩
          | inr b =>
            exfalso
            have h_zero : (Matrix.fromBlocks (0 : Matrix m m R) B C 0) (σ (Sum.inr j)) (Sum.inr j) = 0 := by
              rw [h_case, Matrix.fromBlocks_apply₂₂]
              rfl
            exact h_none (Sum.inr j) h_zero
  4. The cardinality of m is at most the cardinality of n.

    Define a function f : m → n sending each i ∈ m to the component in n given by σ(i). Because σ is a permutation (hence injective) and the inclusion of m into m ⊕ n is injective by Sum.inl_injective, f is an injective function. By Fintype.card_le_of_injective, this implies |m| ≤ |n|.

    lines 35–41

    uses Sum.inl_injective, Fintype.card_le_of_injective

        let f : m → n := fun i => (h1 i).choose
        have hf : ∀ i, σ (Sum.inl i) = Sum.inr (f i) := fun i => (h1 i).choose_spec
        have h_inj_f : Function.Injective f := by
          intro i₁ i₂ h_eq
          have : σ (Sum.inl i₁) = σ (Sum.inl i₂) := by rw [hf, hf, h_eq]
          exact Sum.inl_injective (σ.injective this)
        have h_le1 : Fintype.card m ≤ Fintype.card n := Fintype.card_le_of_injective f h_inj_f
  5. The cardinality of n is at most the cardinality of m.

    Symmetrically, define g : n → m sending each j ∈ n to the component in m given by σ(j). Because σ and the inclusion of n into m ⊕ n are injective (the latter by Sum.inr_injective), g is injective. By Fintype.card_le_of_injective, this implies |n| ≤ |m|.

    lines 42–48

    uses Sum.inr_injective, Fintype.card_le_of_injective

        let g : n → m := fun j => (h2 j).choose
        have hg : ∀ j, σ (Sum.inr j) = Sum.inl (g j) := fun j => (h2 j).choose_spec
        have h_inj_g : Function.Injective g := by
          intro j₁ j₂ h_eq
          have : σ (Sum.inr j₁) = σ (Sum.inr j₂) := by rw [hg, hg, h_eq]
          exact Sum.inr_injective (σ.injective this)
        have h_le2 : Fintype.card n ≤ Fintype.card m := Fintype.card_le_of_injective g h_inj_g
  6. For every permutation σ of m ⊕ n, the product of the matrix entries along σ is zero.

    The two inequalities |m| ≤ |n| and |n| ≤ |m| imply |m| = |n| by antisymmetry (le_antisymm). This contradicts the theorem's hypothesis that |m| ≠ |n|. The contradiction refutes the assumption that the product was non-zero, concluding that the product along any permutation σ vanishes.

    line 49

    uses le_antisymm

        exact hm (le_antisymm h_le1 h_le2)
  7. The permanent of the block matrix is 0.

    The permanent of a matrix is defined by Matrix.permanent as the sum over all permutations σ of the product of the entries chosen by σ. Since every term in this sum is zero by the previous step, the entire sum evaluates to 0.

    line 50

    uses Matrix.permanent

      simp [Matrix.permanent, h_prod]
Finset.prod_eq_zero
If an element of a finite set evaluates to zero under a function, then the product of the function values over that set is zero.
Finset.mem_univ
Every element of a finite type belongs to its universal finset.
Matrix.fromBlocks_apply₁₁
Evaluating a block matrix at row and column indices that both lie in the top-left block gives the corresponding entry of the top-left block.
Matrix.fromBlocks_apply₂₂
Evaluating a block matrix at row and column indices that both lie in the bottom-right block gives the corresponding entry of the bottom-right block.
Sum.inl_injective
The canonical left inclusion into a disjoint sum is injective.
Sum.inr_injective
The canonical right inclusion into a disjoint sum is injective.
Fintype.card_le_of_injective
If there exists an injection from a finite type to another, the cardinality of the domain is at most the cardinality of the codomain.
le_antisymm
If a ≤ b and b ≤ a in a partial order, then a = b.
Matrix.permanent
The permanent of a square matrix, defined as the sum over all permutations of the product of matrix entries indexed by the permutation.

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 zero diagonal blocks of unequal dimensions vanishes. -/theorem matrix_permanent_from_blocks_anti_diagonal_of_ne_card {m n R : Type*}    [DecidableEq m] [DecidableEq n] [Fintype m] [Fintype n] [CommSemiring R]    (hm : Fintype.card m ≠ Fintype.card n) (B : Matrix m n R) (C : Matrix n m R) :    (Matrix.fromBlocks (0 : Matrix m m R) B C 0).permanent = 0 := by  have h_prod (σ : Equiv.Perm (m ⊕ n)) :      ∏ i : m ⊕ n, (Matrix.fromBlocks (0 : Matrix m m R) B C 0) (σ i) i = 0 := by    by_contra h_ne    have h_none : ∀ x, (Matrix.fromBlocks (0 : Matrix m m R) B C 0) (σ x) x ≠ 0 := by      intro x hx      apply h_ne      exact Finset.prod_eq_zero (Finset.mem_univ x) hx    have h1 : ∀ i : m, ∃ b : n, σ (Sum.inl i) = Sum.inr b := by      intro i      cases h_case : σ (Sum.inl i) with      | inl a =>        exfalso        have h_zero : (Matrix.fromBlocks (0 : Matrix m m R) B C 0) (σ (Sum.inl i)) (Sum.inl i) = 0 := by          rw [h_case, Matrix.fromBlocks_apply₁₁]          rfl        exact h_none (Sum.inl i) h_zero      | inr b =>        exact ⟨b, rfl⟩    have h2 : ∀ j : n, ∃ a : m, σ (Sum.inr j) = Sum.inl a := by      intro j      cases h_case : σ (Sum.inr j) with      | inl a =>        exact ⟨a, rfl⟩      | inr b =>        exfalso        have h_zero : (Matrix.fromBlocks (0 : Matrix m m R) B C 0) (σ (Sum.inr j)) (Sum.inr j) = 0 := by          rw [h_case, Matrix.fromBlocks_apply₂₂]          rfl        exact h_none (Sum.inr j) h_zero    let f : m → n := fun i => (h1 i).choose    have hf : ∀ i, σ (Sum.inl i) = Sum.inr (f i) := fun i => (h1 i).choose_spec    have h_inj_f : Function.Injective f := by      intro i₁ i₂ h_eq      have : σ (Sum.inl i₁) = σ (Sum.inl i₂) := by rw [hf, hf, h_eq]      exact Sum.inl_injective (σ.injective this)    have h_le1 : Fintype.card m ≤ Fintype.card n := Fintype.card_le_of_injective f h_inj_f    let g : n → m := fun j => (h2 j).choose    have hg : ∀ j, σ (Sum.inr j) = Sum.inl (g j) := fun j => (h2 j).choose_spec    have h_inj_g : Function.Injective g := by      intro j₁ j₂ h_eq      have : σ (Sum.inr j₁) = σ (Sum.inr j₂) := by rw [hg, hg, h_eq]      exact Sum.inr_injective (σ.injective this)    have h_le2 : Fintype.card n ≤ Fintype.card m := Fintype.card_le_of_injective g h_inj_g    exact hm (le_antisymm h_le1 h_le2)  simp [Matrix.permanent, h_prod]
See it in the graphDiscuss this resultChallenge it