AFTD Auto-Formalizing Theoretical Domains

petrial_rank_schur_invertible

theoremverified

For 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 that block plus the rank of its Schur complement.

Statement

theorem petrial_rank_schur_invertible {K m n : Type*} [Field K] [Fintype m] [Fintype n] [DecidableEq m] [DecidableEq n] (A : Matrix m m K) [Invertible A] (B : Matrix m n K) (C : Matrix n m K) (D : Matrix n n K) : (Matrix.fromBlocks A B C D).rank = Fintype.card m + (D - C * ⅟A * B).rank
Source
Block elimination for the leaf recurrence in OP-1239.
Verified
16 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 3
  • petrial_leaf_one_pivotIf v is a leaf with unique neighbor u and the diagonal perturbation includes v, the perturbed matrix rank is one plus the rank on the…
  • petrial_leaf_zero_pivotFor a graph with a leaf v and unique neighbor u, if v is absent from the perturbation then its matrix rank is two plus the rank on the…
  • petrial_block_diagonal_rankOver 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.

The proof, explained

To compute the rank of a block matrix with an invertible leading block A, the matrix is factored as the product of a block diagonal matrix T with diagonal blocks A and I, and a block matrix N whose leading block is the identity matrix I. Because A is invertible, T has an invertible determinant and multiplication by T preserves rank, reducing the computation to finding the rank of N. For block matrices with an identity leading block, a Schur complement decomposition into unit block-triangular factors and a block diagonal matrix reduces the rank to that of the block diagonal Schur complement, whose rank is its block size plus the rank of D - C * ⅟A * B by the rank-nullity theorem.

  1. The kernel of the block diagonal matrix with identity leading block has the same dimension as the kernel of the lower-right block D.

    An explicit linear equivalence e is constructed between the kernel of the block diagonal matrix and the kernel of D. The forward map sends a vector (x₁, x₂) in the block kernel to its second component x₂; applying Matrix.fromBlocks_mulVec shows that I x₁ + 0 = 0 (hence x₁ = 0) and D x₂ = 0, so x₂ belongs to the kernel of D. The inverse map sends y in the kernel of D to (0, y), which satisfies the block system since I · 0 + 0 = 0 and D y = 0. These two maps are mutually inverse and linear, which proves via e.finrank_eq that the two kernel submodules have equal dimension.

    lines 9–43

    uses Matrix.fromBlocks_mulVec, Subtype.ext

      let e : LinearMap.ker (Matrix.mulVecLin (Matrix.fromBlocks (1 : Matrix m m K) 0 0 D)) ≃ₗ[K]
          LinearMap.ker D.mulVecLin := {
        toFun := fun x => ⟨fun i => x.1 (Sum.inr i), by
          have hx := x.2
          change Matrix.mulVec (Matrix.fromBlocks (1 : Matrix m m K) 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)
          change (D.mulVec (x.1 ∘ Sum.inr)) i = 0
          simpa [Matrix.fromBlocks_mulVec] using hi⟩
        invFun := fun y => ⟨Sum.elim (fun _ => 0) y.1, by
          have hy := y.2
          change D.mulVec y.1 = 0 at hy
          change Matrix.mulVec (Matrix.fromBlocks (1 : Matrix m m K) 0 0 D) (Sum.elim (fun _ => 0) y.1) = 0
          funext i
          cases i with
          | inl i => simp [Matrix.fromBlocks_mulVec]
          | inr i =>
            have hi := congrFun hy i
            simpa [Matrix.fromBlocks_mulVec] using hi⟩
        left_inv := fun x => by
          apply Subtype.ext
          funext i
          cases i with
          | inl i =>
            have hx := x.2
            change Matrix.mulVec (Matrix.fromBlocks (1 : Matrix m m K) 0 0 D) x.1 = 0 at hx
            have hi := congrFun hx (Sum.inl i)
            simpa [Matrix.fromBlocks_mulVec] using hi.symm
          | inr i => rfl
        right_inv := fun y => by apply Subtype.ext; rfl
        map_add' := fun x y => by apply Subtype.ext; rfl
        map_smul' := fun c x => by apply Subtype.ext; rfl
      }
      exact e.finrank_eq
  2. The rank of the block diagonal matrix with identity leading block is |m| + rank(D).

    By the rank-nullity theorem, the rank of a matrix plus its nullity equals the dimension of its domain. The domain of the block diagonal matrix has dimension |m| + |n| by Module.finrank_fintype_fun_eq_card and Fintype.card_sum, while the domain of D has dimension |n|. Since both matrices have equal nullity by petrial_kernel_block_identity, Presburger linear arithmetic (omega) determines that the rank of the block diagonal matrix is |m| + rank(D).

    lines 47–53

    uses petrial_kernel_block_identity, Module.finrank_fintype_fun_eq_card, Fintype.card_sum

      have he := petrial_kernel_block_identity (m := m) D
      have h₁ := (Matrix.mulVecLin (Matrix.fromBlocks (1 : Matrix m m K) 0 0 D)).finrank_range_add_finrank_ker
      have h₂ := D.mulVecLin.finrank_range_add_finrank_ker
      change (Matrix.fromBlocks (1 : Matrix m m K) 0 0 D).rank + _ = _ at h₁
      change D.rank + _ = _ at h₂
      simp only [Module.finrank_fintype_fun_eq_card, Fintype.card_sum] at h₁ h₂
      omega
  3. The block matrix with identity leading block decomposes as L * M * R, where L and R are block triangular matrices with unit determinants and M is the block diagonal Schur complement matrix.

    Define the block triangular factors L and R and the block diagonal matrix M whose lower-right block is the Schur complement D - C * B. By Matrix.det_fromBlocks_zero₁₂ and Matrix.det_fromBlocks_zero₂₁, the determinants of L and R both equal det(1) * det(1) = 1, which are units. Because the identity matrix is invertible (invertibleOne), Matrix.fromBlocks_eq_of_invertible₁₁ yields the factorization of the block matrix into L * M * R.

    lines 58–71

    uses Matrix.det_fromBlocks_zero₁₂, Matrix.det_fromBlocks_zero₂₁, invertibleOne, Matrix.fromBlocks_eq_of_invertible₁₁

      let L : Matrix (m ⊕ n) (m ⊕ n) K := Matrix.fromBlocks 1 0 C 1
      let R : Matrix (m ⊕ n) (m ⊕ n) K := Matrix.fromBlocks 1 B 0 1
      let M : Matrix (m ⊕ n) (m ⊕ n) K := Matrix.fromBlocks 1 0 0 (D - C * B)
      have hL : IsUnit L.det := by
        dsimp [L]
        rw [Matrix.det_fromBlocks_zero₁₂]
        simp
      have hR : IsUnit R.det := by
        dsimp [R]
        rw [Matrix.det_fromBlocks_zero₂₁]
        simp
      letI : Invertible (1 : Matrix m m K) := invertibleOne
      have hdec : Matrix.fromBlocks (1 : Matrix m m K) B C D = L * M * R := by
        simpa [L, M, R] using Matrix.fromBlocks_eq_of_invertible₁₁ (1 : Matrix m m K) B C D
  4. The rank of a block matrix with identity leading block is |m| + rank(D - C * B).

    Because L and R have unit determinants, multiplying by them preserves rank (Matrix.rank_mul_eq_left_of_isUnit_det and Matrix.rank_mul_eq_right_of_isUnit_det), so the rank of L * M * R reduces to the rank of M. Since M is block diagonal with an identity leading block, applying petrial_rank_block_identity gives the rank as |m| + rank(D - C * B).

    lines 72–74

    uses Matrix.rank_mul_eq_left_of_isUnit_det, Matrix.rank_mul_eq_right_of_isUnit_det, petrial_rank_block_identity

      rw [hdec, Matrix.rank_mul_eq_left_of_isUnit_det R (L * M) hR,
        Matrix.rank_mul_eq_right_of_isUnit_det L M hL]
      exact petrial_rank_block_identity (D - C * B)
  5. The general block matrix factors as T * N, where T is block diagonal with leading block A and determinant a unit, and N has an identity leading block.

    Define T with diagonal blocks A and 1, and N with leading block 1 and upper-right block ⅟A * B. By Matrix.det_fromBlocks_zero₁₂, det(T) = det(A) * det(1) = det(A), which is a unit by Matrix.isUnit_det_of_invertible because A is invertible. Performing block multiplication with Matrix.fromBlocks_multiply and Matrix.mul_assoc shows that T * N equals the original block matrix.

    lines 84–91

    uses Matrix.det_fromBlocks_zero₁₂, Matrix.isUnit_det_of_invertible, Matrix.fromBlocks_multiply, Matrix.mul_assoc

      let T : Matrix (m ⊕ n) (m ⊕ n) K := Matrix.fromBlocks A 0 0 1
      let N : Matrix (m ⊕ n) (m ⊕ n) K := Matrix.fromBlocks 1 (⅟A * B) C D
      have hT : IsUnit T.det := by
        dsimp [T]
        rw [Matrix.det_fromBlocks_zero₁₂]
        simpa using Matrix.isUnit_det_of_invertible A
      have hmul : Matrix.fromBlocks A B C D = T * N := by
        simp [T, N, Matrix.fromBlocks_multiply, Matrix.mul_assoc]
  6. The rank of the block matrix is |m| + rank(D - C * ⅟A * B).

    Because det(T) is a unit, left multiplication by T preserves rank (Matrix.rank_mul_eq_right_of_isUnit_det), so the rank of the block matrix equals the rank of N. Since N has the identity matrix as its leading block, petrial_rank_schur_identity applies to compute its rank as |m| + rank(D - C * ⅟A * B), with Matrix.mul_assoc handling the grouping of products.

    lines 92–93

    uses Matrix.rank_mul_eq_right_of_isUnit_det, Matrix.mul_assoc, petrial_rank_schur_identity

      rw [hmul, Matrix.rank_mul_eq_right_of_isUnit_det T N hT]
      simpa [N, Matrix.mul_assoc] using petrial_rank_schur_identity (⅟A * B) C D
Matrix.fromBlocks_mulVec
Multiplying a block matrix by a partitioned vector yields the block-multiplied components: the upper component is A u + B v and the lower component is C u + D v.
Subtype.ext
Two elements of a subtype are equal if and only if their underlying values are equal.
petrial_kernel_block_identity
The nullity (dimension of the kernel) of the block diagonal matrix with identity leading block is equal to the nullity of the lower-right block D.
Module.finrank_fintype_fun_eq_card
The dimension of the space of functions from a finite index type η to a field R is the cardinality of η.
Fintype.card_sum
The cardinality of the disjoint union type α ⊕ β is the sum of the cardinalities of α and β.
Matrix.det_fromBlocks_zero₁₂
The determinant of a block lower-triangular matrix with zero upper-right block is the product of the determinants of the diagonal blocks.
Matrix.det_fromBlocks_zero₂₁
The determinant of a block upper-triangular matrix with zero lower-left block is the product of the determinants of the diagonal blocks.
invertibleOne
The identity matrix is invertible.
Matrix.fromBlocks_eq_of_invertible₁₁
When the leading block A is invertible, a block matrix decomposes as the product of a unit lower-triangular block matrix, a block diagonal Schur complement matrix, and a unit upper-triangular block matrix.
Matrix.rank_mul_eq_left_of_isUnit_det
Right multiplication by a square matrix with unit determinant preserves the rank of a matrix.
Matrix.rank_mul_eq_right_of_isUnit_det
Left multiplication by a square matrix with unit determinant preserves the rank of a matrix.
petrial_rank_block_identity
The rank of a block diagonal matrix with an identity leading block of size m is the cardinality of m plus the rank of the lower-right block D.
Matrix.isUnit_det_of_invertible
An invertible matrix has an invertible determinant (a unit in the scalar ring).
Matrix.fromBlocks_multiply
Block matrix multiplication follows the standard row-by-column block product formula.
Matrix.mul_assoc
Matrix multiplication is associative.
petrial_rank_schur_identity
For a block matrix whose upper-left block is the identity matrix of size m, its rank is the cardinality of m plus the rank of its Schur complement D - C * B.

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

namespace Op1239Schuropen Matrixsectionvariable {K m n : Type*} [Field K] [Fintype m] [Fintype n] [DecidableEq m] [DecidableEq n]theorem petrial_kernel_block_identity (D : Matrix n n K) :    Module.finrank K (LinearMap.ker (Matrix.mulVecLin (Matrix.fromBlocks (1 : Matrix m m K) 0 0 D))) =      Module.finrank K (LinearMap.ker D.mulVecLin) := by  let e : LinearMap.ker (Matrix.mulVecLin (Matrix.fromBlocks (1 : Matrix m m K) 0 0 D)) ≃ₗ[K]      LinearMap.ker D.mulVecLin := {    toFun := fun x => ⟨fun i => x.1 (Sum.inr i), by      have hx := x.2      change Matrix.mulVec (Matrix.fromBlocks (1 : Matrix m m K) 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)      change (D.mulVec (x.1 ∘ Sum.inr)) i = 0      simpa [Matrix.fromBlocks_mulVec] using hi⟩    invFun := fun y => ⟨Sum.elim (fun _ => 0) y.1, by      have hy := y.2      change D.mulVec y.1 = 0 at hy      change Matrix.mulVec (Matrix.fromBlocks (1 : Matrix m m K) 0 0 D) (Sum.elim (fun _ => 0) y.1) = 0      funext i      cases i with      | inl i => simp [Matrix.fromBlocks_mulVec]      | inr i =>        have hi := congrFun hy i        simpa [Matrix.fromBlocks_mulVec] using hi⟩    left_inv := fun x => by      apply Subtype.ext      funext i      cases i with      | inl i =>        have hx := x.2        change Matrix.mulVec (Matrix.fromBlocks (1 : Matrix m m K) 0 0 D) x.1 = 0 at hx        have hi := congrFun hx (Sum.inl i)        simpa [Matrix.fromBlocks_mulVec] using hi.symm      | inr i => rfl    right_inv := fun y => by apply Subtype.ext; rfl    map_add' := fun x y => by apply Subtype.ext; rfl    map_smul' := fun c x => by apply Subtype.ext; rfl  }  exact e.finrank_eqtheorem petrial_rank_block_identity (D : Matrix n n K) :    (Matrix.fromBlocks (1 : Matrix m m K) 0 0 D).rank = Fintype.card m + D.rank := by  have he := petrial_kernel_block_identity (m := m) D  have h₁ := (Matrix.mulVecLin (Matrix.fromBlocks (1 : Matrix m m K) 0 0 D)).finrank_range_add_finrank_ker  have h₂ := D.mulVecLin.finrank_range_add_finrank_ker  change (Matrix.fromBlocks (1 : Matrix m m K) 0 0 D).rank + _ = _ at h₁  change D.rank + _ = _ at h₂  simp only [Module.finrank_fintype_fun_eq_card, Fintype.card_sum] at h₁ h₂  omegatheorem petrial_rank_schur_identity (B : Matrix m n K) (C : Matrix n m K) (D : Matrix n n K) :    (Matrix.fromBlocks (1 : Matrix m m K) B C D).rank = Fintype.card m + (D - C * B).rank := by  let L : Matrix (m ⊕ n) (m ⊕ n) K := Matrix.fromBlocks 1 0 C 1  let R : Matrix (m ⊕ n) (m ⊕ n) K := Matrix.fromBlocks 1 B 0 1  let M : Matrix (m ⊕ n) (m ⊕ n) K := Matrix.fromBlocks 1 0 0 (D - C * B)  have hL : IsUnit L.det := by    dsimp [L]    rw [Matrix.det_fromBlocks_zero₁₂]    simp  have hR : IsUnit R.det := by    dsimp [R]    rw [Matrix.det_fromBlocks_zero₂₁]    simp  letI : Invertible (1 : Matrix m m K) := invertibleOne  have hdec : Matrix.fromBlocks (1 : Matrix m m K) B C D = L * M * R := by    simpa [L, M, R] using Matrix.fromBlocks_eq_of_invertible₁₁ (1 : Matrix m m K) B C D  rw [hdec, Matrix.rank_mul_eq_left_of_isUnit_det R (L * M) hR,    Matrix.rank_mul_eq_right_of_isUnit_det L M hL]  exact petrial_rank_block_identity (D - C * B)endend Op1239Schuropen Op1239Schur/-- Rank reduction by an invertible leading block, used for the one- and two-vertex elimination cases. -/theorem petrial_rank_schur_invertible {K m n : Type*} [Field K] [Fintype m] [Fintype n] [DecidableEq m] [DecidableEq n] (A : Matrix m m K) [Invertible A] (B : Matrix m n K) (C : Matrix n m K) (D : Matrix n n K) : (Matrix.fromBlocks A B C D).rank = Fintype.card m + (D - C * ⅟A * B).rank := by  let T : Matrix (m ⊕ n) (m ⊕ n) K := Matrix.fromBlocks A 0 0 1  let N : Matrix (m ⊕ n) (m ⊕ n) K := Matrix.fromBlocks 1 (⅟A * B) C D  have hT : IsUnit T.det := by    dsimp [T]    rw [Matrix.det_fromBlocks_zero₁₂]    simpa using Matrix.isUnit_det_of_invertible A  have hmul : Matrix.fromBlocks A B C D = T * N := by    simp [T, N, Matrix.fromBlocks_multiply, Matrix.mul_assoc]  rw [hmul, Matrix.rank_mul_eq_right_of_isUnit_det T N hT]  simpa [N, Matrix.mul_assoc] using petrial_rank_schur_identity (⅟A * B) C D
See it in the graphDiscuss this resultChallenge it