AFTD Auto-Formalizing Theoretical Domains

petrial_block_diagonal_rank

theoremverified

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

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

    lines 9–46

    uses Matrix.fromBlocks_mulVec, Function.comp_def, congrFun, Subtype.ext, Prod.ext

      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
      }
  2. 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).

    lines 47–49

    uses e.finrank_eq

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

    lines 50–56

    uses finrank_range_add_finrank_ker, Module.finrank_fintype_fun_eq_card, Fintype.card_sum

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

    line 57

      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.

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

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