petrial_block_diagonal_rank
Over a field, the rank of a block diagonal matrix with square finite blocks A and D equals the sum of the ranks of A and D.
Statement
theorem petrial_block_diagonal_rank {K m n : Type*} [Field K] [Fintype m] [Fintype n] [DecidableEq m] [DecidableEq n] (A : Matrix m m K) (D : Matrix n n K) : (Matrix.fromBlocks A 0 0 D).rank = A.rank + D.rank
- Source
- Matrix-rank helper for the disjoint-cut product in OP-1239.
- Verified
- 16 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- petrial_rank_schur_invertibleFor square finite block matrices over a field, if the upper-left block is invertible, the rank of the whole block matrix is the size of…
- Used by 1
- petrial_nullity_poly_mul_of_cutIf no edge of G joins a vertex of s to a vertex outside s, then the nullity generating polynomial of G is the product of the nullity…
The proof, explained
The theorem is proved by applying the rank-nullity theorem to the block diagonal matrix and to each of its diagonal blocks A and D. The core step is constructing an explicit linear equivalence between the kernel of the block matrix and the direct product ker(A) × ker(D), which shows that the nullity of the block matrix is the sum of the nullities of A and D. Since the domain dimension also splits as |m| + |n|, subtracting the nullities from the domain dimensions yields rank(fromBlocks A 0 0 D) = rank(A) + rank(D).
The kernel of the block diagonal matrix is linearly isomorphic to the direct product of the kernels of its diagonal blocks: ker(fromBlocks A 0 0 D) ≃ₗ ker(A) × ker(D).
We define an explicit linear equivalence e. The forward map splits any vector x in the kernel of the block diagonal matrix into its components on the index sets m and n. By block matrix multiplication (Matrix.fromBlocks_mulVec, Function.comp_def, congrFun), each component is annihilated by A and D respectively, so it belongs to ker(A) × ker(D). Conversely, the inverse map combines a pair (p₁, p₂) from ker(A) × ker(D) into a single vector via Sum.elim, which by the same block multiplication rule lies in the kernel of the block matrix. The two maps are inverses and preserve addition and scalar multiplication, as verified componentwise (Subtype.ext, Prod.ext).
uses
Matrix.fromBlocks_mulVec,Function.comp_def,congrFun,Subtype.ext,Prod.extclassical let e : LinearMap.ker (Matrix.mulVecLin (Matrix.fromBlocks A 0 0 D)) ≃ₗ[K] (LinearMap.ker A.mulVecLin × LinearMap.ker D.mulVecLin) := { toFun := fun x => (⟨fun i => x.1 (Sum.inl i), by have hx := x.2 change Matrix.mulVec (Matrix.fromBlocks A 0 0 D) x.1 = 0 at hx change A.mulVec (fun i => x.1 (Sum.inl i)) = 0 funext i have hi := congrFun hx (Sum.inl i) simpa [Matrix.fromBlocks_mulVec, Function.comp_def] using hi⟩, ⟨fun i => x.1 (Sum.inr i), by have hx := x.2 change Matrix.mulVec (Matrix.fromBlocks A 0 0 D) x.1 = 0 at hx change D.mulVec (fun i => x.1 (Sum.inr i)) = 0 funext i have hi := congrFun hx (Sum.inr i) simpa [Matrix.fromBlocks_mulVec, Function.comp_def] using hi⟩) invFun := fun p => ⟨Sum.elim p.1.1 p.2.1, by have hA := p.1.2 have hD := p.2.2 change A.mulVec p.1.1 = 0 at hA change D.mulVec p.2.1 = 0 at hD change Matrix.mulVec (Matrix.fromBlocks A 0 0 D) (Sum.elim p.1.1 p.2.1) = 0 funext i cases i with | inl i => simpa [Matrix.fromBlocks_mulVec, Function.comp_def] using congrFun hA i | inr i => simpa [Matrix.fromBlocks_mulVec, Function.comp_def] using congrFun hD i⟩ left_inv := fun x => by apply Subtype.ext funext i cases i <;> rfl right_inv := fun p => by apply Prod.ext <;> apply Subtype.ext <;> rfl map_add' := fun x y => by apply Prod.ext <;> apply Subtype.ext <;> rfl map_smul' := fun c x => by apply Prod.ext <;> apply Subtype.ext <;> rfl }
The nullity of the block diagonal matrix equals the sum of the nullities of A and D: dim ker(fromBlocks A 0 0 D) = dim ker(A) + dim ker(D).
Because e is a linear equivalence, the dimension of its domain equals the dimension of its codomain (e.finrank_eq). The dimension of a Cartesian product of finite-dimensional vector spaces is the sum of their dimensions, giving dim ker(fromBlocks A 0 0 D) = dim ker(A) + dim ker(D).
uses
e.finrank_eqhave he : Module.finrank K (LinearMap.ker (Matrix.mulVecLin (Matrix.fromBlocks A 0 0 D))) = Module.finrank K (LinearMap.ker A.mulVecLin) + Module.finrank K (LinearMap.ker D.mulVecLin) := by simpa using e.finrank_eq
The rank and nullity of the block matrix, of A, and of D each sum to the cardinality of the respective index set: rank(fromBlocks A 0 0 D) + nullity = |m| + |n|, rank(A) + nullity = |m|, and rank(D) + nullity = |n|.
We apply the rank-nullity theorem (finrank_range_add_finrank_ker) to the linear maps associated with the block matrix, A, and D. Since matrix rank is defined as the dimension of the range of the vector multiplication map, the range terms become the matrix ranks. The domain dimensions are evaluated as the cardinalities of the indexing types (Module.finrank_fintype_fun_eq_card), and the cardinality of m ⊕ n splits into |m| + |n| (Fintype.card_sum).
uses
finrank_range_add_finrank_ker,Module.finrank_fintype_fun_eq_card,Fintype.card_sumhave h := (Matrix.mulVecLin (Matrix.fromBlocks A 0 0 D)).finrank_range_add_finrank_ker have hA := A.mulVecLin.finrank_range_add_finrank_ker have hD := D.mulVecLin.finrank_range_add_finrank_ker change (Matrix.fromBlocks A 0 0 D).rank + _ = _ at h change A.rank + _ = _ at hA change D.rank + _ = _ at hD simp only [Module.finrank_fintype_fun_eq_card, Fintype.card_sum] at h hA hD
The rank of the block diagonal matrix equals the sum of the ranks of A and D: rank(fromBlocks A 0 0 D) = rank(A) + rank(D).
Combining the rank-nullity equation for the block matrix with the sum of the rank-nullity equations for A and D, and substituting the relation between their nullities (dim ker(block) = dim ker(A) + dim ker(D)), the kernel dimensions cancel out, leaving rank(fromBlocks A 0 0 D) = rank(A) + rank(D). Linear integer arithmetic closes the goal.
omega
Matrix.fromBlocks_mulVec- Multiplying a 2×2 block matrix by a partitioned vector applies the diagonal and off-diagonal blocks to the vector's components and sums the results.
Function.comp_def- The definition of function composition: (f ∘ g)(x) = f(g(x)).
congrFun- Equal functions take equal values at any argument: if f = g, then f(a) = g(a).
Subtype.ext- Two elements of a subtype are equal if their underlying values are equal.
Prod.ext- Two pairs are equal if their first components are equal and their second components are equal.
e.finrank_eq- Two vector spaces connected by a linear equivalence have the same finite dimension.
finrank_range_add_finrank_ker- For any linear map on a finite-dimensional space, the dimension of its range plus the dimension of its kernel equals the dimension of its domain (the rank-nullity theorem).
Module.finrank_fintype_fun_eq_card- The dimension of the vector space of functions from a finite set η to a field is the cardinality of η.
Fintype.card_sum- The cardinality of the disjoint sum (coproduct) of two finite types is the sum of their cardinalities.
- In Mathlib, the rank of a matrix is defined as the dimension of the range of its multiplication linear map Matrix.mulVecLin.
- The final step uses the decision procedure omega to solve the linear integer arithmetic relating the ranks, kernel dimensions, and domain cardinalities.
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.
open Matrixset_option maxRecDepth 10000set_option maxHeartbeats 0theorem petrial_block_diagonal_rank {K m n : Type*} [Field K] [Fintype m] [Fintype n] [DecidableEq m] [DecidableEq n] (A : Matrix m m K) (D : Matrix n n K) : (Matrix.fromBlocks A 0 0 D).rank = A.rank + D.rank := by classical let e : LinearMap.ker (Matrix.mulVecLin (Matrix.fromBlocks A 0 0 D)) ≃ₗ[K] (LinearMap.ker A.mulVecLin × LinearMap.ker D.mulVecLin) := { toFun := fun x => (⟨fun i => x.1 (Sum.inl i), by have hx := x.2 change Matrix.mulVec (Matrix.fromBlocks A 0 0 D) x.1 = 0 at hx change A.mulVec (fun i => x.1 (Sum.inl i)) = 0 funext i have hi := congrFun hx (Sum.inl i) simpa [Matrix.fromBlocks_mulVec, Function.comp_def] using hi⟩, ⟨fun i => x.1 (Sum.inr i), by have hx := x.2 change Matrix.mulVec (Matrix.fromBlocks A 0 0 D) x.1 = 0 at hx change D.mulVec (fun i => x.1 (Sum.inr i)) = 0 funext i have hi := congrFun hx (Sum.inr i) simpa [Matrix.fromBlocks_mulVec, Function.comp_def] using hi⟩) invFun := fun p => ⟨Sum.elim p.1.1 p.2.1, by have hA := p.1.2 have hD := p.2.2 change A.mulVec p.1.1 = 0 at hA change D.mulVec p.2.1 = 0 at hD change Matrix.mulVec (Matrix.fromBlocks A 0 0 D) (Sum.elim p.1.1 p.2.1) = 0 funext i cases i with | inl i => simpa [Matrix.fromBlocks_mulVec, Function.comp_def] using congrFun hA i | inr i => simpa [Matrix.fromBlocks_mulVec, Function.comp_def] using congrFun hD i⟩ left_inv := fun x => by apply Subtype.ext funext i cases i <;> rfl right_inv := fun p => by apply Prod.ext <;> apply Subtype.ext <;> rfl map_add' := fun x y => by apply Prod.ext <;> apply Subtype.ext <;> rfl map_smul' := fun c x => by apply Prod.ext <;> apply Subtype.ext <;> rfl } have he : Module.finrank K (LinearMap.ker (Matrix.mulVecLin (Matrix.fromBlocks A 0 0 D))) = Module.finrank K (LinearMap.ker A.mulVecLin) + Module.finrank K (LinearMap.ker D.mulVecLin) := by simpa using e.finrank_eq have h := (Matrix.mulVecLin (Matrix.fromBlocks A 0 0 D)).finrank_range_add_finrank_ker have hA := A.mulVecLin.finrank_range_add_finrank_ker have hD := D.mulVecLin.finrank_range_add_finrank_ker change (Matrix.fromBlocks A 0 0 D).rank + _ = _ at h change A.rank + _ = _ at hA change D.rank + _ = _ at hD simp only [Module.finrank_fintype_fun_eq_card, Fintype.card_sum] at h hA hD omega