AFTD Auto-Formalizing Theoretical Domains

petrial_leaf_zero_pivot

theoremverified

For 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 graph obtained by deleting u and v, with the perturbation restricted.

Statement

theorem petrial_leaf_zero_pivot {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) [DecidableRel G.Adj] (v u : V) (F : Finset V)
    (hF : v ∉ F) (hu : G.Adj v u) (huniq : ∀ w, G.Adj v w → w = u) :
    (petrial_matrix G F).rank =
      2 + (petrial_matrix (G.induce ({u, v}ᶜ : Set V)) (petrial_leaf_restriction v u F)).rank
Source
Helper for the partial Petrial leaf recurrence and OP-1239.
Verified
16 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • petrial_leaf_restrictionRestrict a finite vertex subset to the complement of vertices u and v.
  • petrial_matrixGiven a finite type V with decidable equality, a simple graph G on V with decidable adjacency, and a finite subset F : Finset V,…
  • 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 2

The proof, explained

The proof decomposes the petrial matrix into a 2 × 2 block structure corresponding to the pair {v, u} and the remaining vertices {u, v}ᶜ. Because v is not in the perturbation F and has u as its unique neighbor, the 2 × 2 pivot block A is invertible over ℤ/2ℤ with (A⁻¹)₁₁ = 0, while the off-diagonal blocks vanish along the index corresponding to v. Consequently, the Schur complement correction term M₂₁ A⁻¹ M₁₂ is identically zero, so by the Schur complement formula the matrix rank is 2 plus the rank on the induced subgraph on {u, v}ᶜ.

  1. The vertex set V decomposes as {v, u} ⊕ {u, v}ᶜ, giving a block matrix representation M of the petrial matrix.

    Because v and u are adjacent, v ≠ u. We define a bijection from Fin 2 to {u, v} sending 0 to v and 1 to u, which together with the complement {u, v}ᶜ yields an equivalence Fin 2 ⊕ {u, v}ᶜ ≃ V. Reindexing the petrial matrix by this equivalence gives the block matrix M.

    lines 6–21

    uses Subtype.ext, Equiv.ofBijective, Equiv.sumCongr, Equiv.refl, Equiv.Set.sumCompl

      classical
      have hvu : v ≠ u := G.ne_of_adj hu
      let P : Set V := {u, v}
      let f : Fin 2 → P := fun i => if i = 0 then ⟨v, by simp [P]⟩ else ⟨u, by simp [P]⟩
      have hf : Function.Bijective f := by
        constructor
        · intro i j h
          fin_cases i <;> fin_cases j <;> simp_all [f, Subtype.ext_iff]
        · intro x
          have hx : (x : V) = u ∨ (x : V) = v := x.2
          rcases hx with hx | hx
          · refine ⟨1, ?_⟩; apply Subtype.ext; simpa [f] using hx.symm
          · refine ⟨0, ?_⟩; apply Subtype.ext; simpa [f] using hx.symm
      let pe : Fin 2 ≃ P := Equiv.ofBijective f hf
      let e : Fin 2 ⊕ (Pᶜ : Set V) ≃ V := (Equiv.sumCongr pe (Equiv.refl _)).trans (Equiv.Set.sumCompl P)
      let M := (petrial_matrix G F).submatrix e e
  2. The top-left 2 × 2 block of M is A = !![0, 1; 1, d], where d = 1 if u ∈ F and 0 otherwise.

    By checking all four index pairs of Fin 2: the (v, v) entry is 0 because simple graphs have no self-loops and v ∉ F; the off-diagonal entries (v, u) and (u, v) are 1 because v and u are adjacent; and the (u, u) entry is d by definition of the perturbation.

    lines 22–28

    uses Matrix.diagonal_apply, Ne.symm

      let d : ZMod 2 := if u ∈ F then 1 else 0
      let A : Matrix (Fin 2) (Fin 2) (ZMod 2) := !![0, 1; 1, d]
      have hA : M.toBlocks₁₁ = A := by
        ext i j
        change (petrial_matrix G F) (pe i).1 (pe j).1 = A i j
        fin_cases i <;> fin_cases j <;>
          simp [pe, f, A, d, petrial_matrix, Matrix.diagonal_apply, hF, hu, hu.symm, hvu, Ne.symm hvu]
  3. The matrix A is invertible with determinant 1, and the (1, 1) entry of its inverse is zero: (⅟A) 1 1 = 0.

    The determinant of A is 0 · d - 1 · 1 = -1 ≡ 1 (mod 2), which is a unit, so A is invertible. Looking at the (0, 1) entry of A · ⅟A = I, the product formula gives A 0 0 * (⅟A) 0 1 + A 0 1 * (⅟A) 1 1 = 0 + 1 * (⅟A) 1 1 = (⅟A) 1 1. Since the identity matrix has 0 in entry (0, 1), we conclude (⅟A) 1 1 = 0.

    lines 29–37

    uses Matrix.det_fin_two, isUnit_one, Matrix.invertibleOfIsUnitDet, congrArg, mul_invOf_self, Matrix.mul_apply, Fin.sum_univ_two

      have hdet : IsUnit A.det := by
        have hd : A.det = 1 := by
          simp [A, Matrix.det_fin_two]
        rw [hd]
        exact isUnit_one
      letI : Invertible A := Matrix.invertibleOfIsUnitDet A hdet
      have hinv : (⅟A) 1 1 = 0 := by
        have h := congrArg (fun (X : Matrix (Fin 2) (Fin 2) (ZMod 2)) => X 0 1) (mul_invOf_self A)
        simpa [Matrix.mul_apply, Fin.sum_univ_two, A] using h
  4. The first column of the off-diagonal block M₂₁ and the first row of M₁₂ are both zero.

    Any vertex w in the complement {u, v}ᶜ satisfies w ≠ u and w ≠ v. Since u is the unique neighbor of v, w cannot be adjacent to v, nor can it equal v on the diagonal. Thus the (w, v) and (v, w) entries of the petrial matrix vanish.

    lines 38–65

    uses Matrix.diagonal_apply, Ne.symm

      have hcol (i : (Pᶜ : Set V)) : M.toBlocks₂₁ i 0 = 0 := by
        change (petrial_matrix G F) i.1 v = 0
        have hiu : (i : V) ≠ u := by
          intro h
          have hi : (i : V) ∉ P := i.2
          apply hi
          simp [P, h]
        have hiv : (i : V) ≠ v := by
          intro h
          have hi : (i : V) ∉ P := i.2
          apply hi
          simp [P, h]
        have hadj : ¬ G.Adj (i : V) v := fun h => hiu (huniq _ h.symm)
        simp [petrial_matrix, Matrix.diagonal_apply, hadj, hiv]
      have hrow (j : (Pᶜ : Set V)) : M.toBlocks₁₂ 0 j = 0 := by
        change (petrial_matrix G F) v j.1 = 0
        have hju : (j : V) ≠ u := by
          intro h
          have hj : (j : V) ∉ P := j.2
          apply hj
          simp [P, h]
        have hjv : (j : V) ≠ v := by
          intro h
          have hj : (j : V) ∉ P := j.2
          apply hj
          simp [P, h]
        have hadj : ¬ G.Adj v (j : V) := fun h => hju (huniq _ h)
        simp [petrial_matrix, Matrix.diagonal_apply, hadj, Ne.symm hjv]
  5. The Schur complement correction term vanishes: M₂₁ * ⅟A * M₁₂ = 0.

    Expanding the matrix product entrywise, the sum over intermediate indices in Fin 2 × Fin 2 vanishes: terms with first index 0 vanish because column 0 of M₂₁ is zero; terms with second index 0 vanish because row 0 of M₁₂ is zero; and the (1, 1) term vanishes because (⅟A) 1 1 = 0.

    lines 66–69

    uses Matrix.mul_apply, Fin.sum_univ_two, zero_mul, mul_zero, zero_add, add_zero, Matrix.zero_apply

      have hprod : M.toBlocks₂₁ * ⅟A * M.toBlocks₁₂ = 0 := by
        ext i j
        simp only [Matrix.mul_apply, Fin.sum_univ_two, hcol, hrow, hinv, zero_mul,
          mul_zero, zero_add, add_zero, Matrix.zero_apply]
  6. The bottom-right block M₂₂ is the petrial matrix of the induced subgraph on {u, v}ᶜ with the restricted perturbation.

    For pairs of vertices in {u, v}ᶜ, adjacency in the induced subgraph is identical to adjacency in G, and the diagonal perturbation matches the filtered subset of F on {u, v}ᶜ.

    lines 70–75

    uses Matrix.diagonal_apply, SimpleGraph.adjMatrix_apply, Subtype.ext_iff

      have hD : M.toBlocks₂₂ = petrial_matrix (G.induce ({u, v}ᶜ : Set V))
          (petrial_leaf_restriction v u F) := by
        ext i j
        change (petrial_matrix G F) i.1 j.1 = _
        simp [petrial_matrix, petrial_leaf_restriction, Matrix.diagonal_apply,
          SimpleGraph.adjMatrix_apply, Subtype.ext_iff]
  7. The rank of the petrial matrix is 2 plus the rank of the petrial matrix of the induced subgraph on {u, v}ᶜ.

    Reindexing by an equivalence preserves matrix rank. By the Schur complement rank formula for the 2 × 2 invertible pivot A, the rank is 2 + rank(M₂₂ - M₂₁ * ⅟A * M₁₂). Since the correction term is zero, this simplifies to 2 + rank(M₂₂), which is the desired formula.

    lines 76–83

    uses petrial_rank_schur_invertible, Matrix.rank_submatrix, sub_zero

      have hschur := petrial_rank_schur_invertible A M.toBlocks₁₂ M.toBlocks₂₁ M.toBlocks₂₂
      have hrank : M.rank = (Matrix.fromBlocks A M.toBlocks₁₂ M.toBlocks₂₁ M.toBlocks₂₂).rank := by
        conv_lhs => rw [← M.fromBlocks_toBlocks]
        rw [hA]
      rw [← Matrix.rank_submatrix (petrial_matrix G F) e e, ← show M.rank = _ from rfl,
        hrank, hschur]
      rw [hprod, sub_zero, hD]
      simp
Subtype.ext
Two elements of a subtype are equal if their underlying values are equal.
Subtype.ext_iff
Two elements of a subtype are equal if and only if their underlying values are equal.
Equiv.ofBijective
A bijective function between types induces an equivalence (bijection).
Equiv.sumCongr
Combines two equivalences into an equivalence between their direct sums.
Equiv.refl
The identity equivalence from any type to itself.
Equiv.Set.sumCompl
The sum of a subset and its complement is equivalent to the full type.
Matrix.diagonal_apply
The (i, j) entry of a diagonal matrix is d(i) if i = j and 0 otherwise.
Ne.symm
Inequality is symmetric: if a ≠ b, then b ≠ a.
Matrix.det_fin_two
The determinant of a 2 × 2 matrix is ad - bc.
isUnit_one
The element 1 in a monoid is a unit (invertible).
Matrix.invertibleOfIsUnitDet
A square matrix over a commutative ring is invertible if its determinant is a unit.
congrArg
Applying a function to equal arguments yields equal results.
mul_invOf_self
Multiplying an invertible element by its inverse yields 1.
Matrix.mul_apply
The (i, k) entry of the product of two matrices is the sum of products of corresponding entries.
Fin.sum_univ_two
A sum over Fin 2 equals the value at 0 plus the value at 1.
zero_mul
Zero multiplied on the left by any element is zero.
mul_zero
Zero multiplied on the right by any element is zero.
zero_add
Adding zero on the left leaves an element unchanged.
add_zero
Adding zero on the right leaves an element unchanged.
Matrix.zero_apply
Every entry of the zero matrix is zero.
SimpleGraph.adjMatrix_apply
The (v, w) entry of the adjacency matrix is 1 if v and w are adjacent, and 0 otherwise.
petrial_rank_schur_invertible
For a block matrix with invertible top-left block A, its rank is the number of rows of A plus the rank of its Schur complement D - C A⁻¹ B.
Matrix.rank_submatrix
Permuting the rows and columns of a matrix by equivalences preserves its rank.
sub_zero
Subtracting zero leaves an element unchanged.

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

theorem petrial_leaf_zero_pivot {V : Type*} [Fintype V] [DecidableEq V]    (G : SimpleGraph V) [DecidableRel G.Adj] (v u : V) (F : Finset V)    (hF : v ∉ F) (hu : G.Adj v u) (huniq : ∀ w, G.Adj v w → w = u) :    (petrial_matrix G F).rank =      2 + (petrial_matrix (G.induce ({u, v}ᶜ : Set V)) (petrial_leaf_restriction v u F)).rank := by  classical  have hvu : v ≠ u := G.ne_of_adj hu  let P : Set V := {u, v}  let f : Fin 2 → P := fun i => if i = 0 then ⟨v, by simp [P]⟩ else ⟨u, by simp [P]⟩  have hf : Function.Bijective f := by    constructor    · intro i j h      fin_cases i <;> fin_cases j <;> simp_all [f, Subtype.ext_iff]    · intro x      have hx : (x : V) = u ∨ (x : V) = v := x.2      rcases hx with hx | hx      · refine ⟨1, ?_⟩; apply Subtype.ext; simpa [f] using hx.symm      · refine ⟨0, ?_⟩; apply Subtype.ext; simpa [f] using hx.symm  let pe : Fin 2 ≃ P := Equiv.ofBijective f hf  let e : Fin 2 ⊕ (Pᶜ : Set V) ≃ V := (Equiv.sumCongr pe (Equiv.refl _)).trans (Equiv.Set.sumCompl P)  let M := (petrial_matrix G F).submatrix e e  let d : ZMod 2 := if u ∈ F then 1 else 0  let A : Matrix (Fin 2) (Fin 2) (ZMod 2) := !![0, 1; 1, d]  have hA : M.toBlocks₁₁ = A := by    ext i j    change (petrial_matrix G F) (pe i).1 (pe j).1 = A i j    fin_cases i <;> fin_cases j <;>      simp [pe, f, A, d, petrial_matrix, Matrix.diagonal_apply, hF, hu, hu.symm, hvu, Ne.symm hvu]  have hdet : IsUnit A.det := by    have hd : A.det = 1 := by      simp [A, Matrix.det_fin_two]    rw [hd]    exact isUnit_one  letI : Invertible A := Matrix.invertibleOfIsUnitDet A hdet  have hinv : (⅟A) 1 1 = 0 := by    have h := congrArg (fun (X : Matrix (Fin 2) (Fin 2) (ZMod 2)) => X 0 1) (mul_invOf_self A)    simpa [Matrix.mul_apply, Fin.sum_univ_two, A] using h  have hcol (i : (Pᶜ : Set V)) : M.toBlocks₂₁ i 0 = 0 := by    change (petrial_matrix G F) i.1 v = 0    have hiu : (i : V) ≠ u := by      intro h      have hi : (i : V) ∉ P := i.2      apply hi      simp [P, h]    have hiv : (i : V) ≠ v := by      intro h      have hi : (i : V) ∉ P := i.2      apply hi      simp [P, h]    have hadj : ¬ G.Adj (i : V) v := fun h => hiu (huniq _ h.symm)    simp [petrial_matrix, Matrix.diagonal_apply, hadj, hiv]  have hrow (j : (Pᶜ : Set V)) : M.toBlocks₁₂ 0 j = 0 := by    change (petrial_matrix G F) v j.1 = 0    have hju : (j : V) ≠ u := by      intro h      have hj : (j : V) ∉ P := j.2      apply hj      simp [P, h]    have hjv : (j : V) ≠ v := by      intro h      have hj : (j : V) ∉ P := j.2      apply hj      simp [P, h]    have hadj : ¬ G.Adj v (j : V) := fun h => hju (huniq _ h)    simp [petrial_matrix, Matrix.diagonal_apply, hadj, Ne.symm hjv]  have hprod : M.toBlocks₂₁ * ⅟A * M.toBlocks₁₂ = 0 := by    ext i j    simp only [Matrix.mul_apply, Fin.sum_univ_two, hcol, hrow, hinv, zero_mul,      mul_zero, zero_add, add_zero, Matrix.zero_apply]  have hD : M.toBlocks₂₂ = petrial_matrix (G.induce ({u, v}ᶜ : Set V))      (petrial_leaf_restriction v u F) := by    ext i j    change (petrial_matrix G F) i.1 j.1 = _    simp [petrial_matrix, petrial_leaf_restriction, Matrix.diagonal_apply,      SimpleGraph.adjMatrix_apply, Subtype.ext_iff]  have hschur := petrial_rank_schur_invertible A M.toBlocks₁₂ M.toBlocks₂₁ M.toBlocks₂₂  have hrank : M.rank = (Matrix.fromBlocks A M.toBlocks₁₂ M.toBlocks₂₁ M.toBlocks₂₂).rank := by    conv_lhs => rw [← M.fromBlocks_toBlocks]    rw [hA]  rw [← Matrix.rank_submatrix (petrial_matrix G F) e e, ← show M.rank = _ from rfl,    hrank, hschur]  rw [hprod, sub_zero, hD]  simp
See it in the graphDiscuss this resultChallenge it