petrial_rank_schur_invertible
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.
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.
uses
Matrix.fromBlocks_mulVec,Subtype.extlet 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
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).
uses
petrial_kernel_block_identity,Module.finrank_fintype_fun_eq_card,Fintype.card_sumhave 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
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.
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
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).
uses
Matrix.rank_mul_eq_left_of_isUnit_det,Matrix.rank_mul_eq_right_of_isUnit_det,petrial_rank_block_identityrw [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)
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.
uses
Matrix.det_fromBlocks_zero₁₂,Matrix.isUnit_det_of_invertible,Matrix.fromBlocks_multiply,Matrix.mul_assoclet 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]
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.
uses
Matrix.rank_mul_eq_right_of_isUnit_det,Matrix.mul_assoc,petrial_rank_schur_identityrw [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
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.
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