matrix_permanent_from_blocks_anti_diagonal_of_ne_card
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.
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.
uses
Finset.prod_eq_zero,Finset.mem_univhave 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
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.
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⟩
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.
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
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|.
uses
Sum.inl_injective,Fintype.card_le_of_injectivelet 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
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|.
uses
Sum.inr_injective,Fintype.card_le_of_injectivelet 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
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.
uses
le_antisymmexact hm (le_antisymm h_le1 h_le2)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.
uses
Matrix.permanentsimp [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.
- The final simplification step uses `simp` to expand the definition of `Matrix.permanent` as a sum over permutations and simplify the sum of zeros to zero.
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 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]