AFTD Auto-Formalizing Theoretical Domains

petrial_leaf_one_pivot

theoremverified

If 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 graph with v removed, where the perturbation is restricted and membership of u is toggled.

Statement

theorem petrial_leaf_one_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 = 1 + (petrial_matrix (G.induce ({v}ᶜ : Set V)) (petrial_leaf_flip v u F)).rank
Source
One-vertex pivot case in the leaf-elimination recurrence for OP-1239.
Verified
16 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • petrial_leaf_flipFor vertices v and u and a vertex subset F, restrict F to the complement of v and toggle membership of u.
  • 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 rank of the petrial matrix is determined by partitioning the vertices into the leaf singleton {v} and its complement V \ {v}, reindexing the matrix as a 2 × 2 block matrix. Because v belongs to the perturbation set F and simple graphs contain no self-loops, the 1 × 1 pivot block at v is the identity matrix [1]. Applying the Schur complement rank formula shows that the matrix rank equals 1 plus the rank of its Schur complement. Since u is the unique neighbor of v, the rank-one update subtracted in the Schur complement is non-zero only at the (u, u) diagonal entry, where it toggles the perturbation status of u in ℤ/2ℤ while leaving all other entries identical to the petrial matrix of the graph with v removed.

  1. The vertex set V is partitioned into P = {v} and Pᶜ = V \ {v}, reindexing the petrial matrix as a 2 × 2 block matrix M with P being a singleton type.

    We define the singleton set P = {v} and the canonical equivalence e : P ⊕ Pᶜ ≃ V via Equiv.Set.sumCompl. Reindexing the petrial matrix along e yields the block matrix M. We record that u ≠ v (since they are adjacent in G) and equip P with a Unique instance showing v is its only element via Subtype.ext.

    lines 2–10

    uses Equiv.Set.sumCompl, Subtype.ext

      classical
      let P : Set V := {v}
      let e := Equiv.Set.sumCompl P
      let M := (petrial_matrix G F).submatrix e e
      have hn : u ≠ v := (G.ne_of_adj hu).symm
      letI : Unique P := {
        default := ⟨v, by simp [P]⟩
        uniq := by intro x; apply Subtype.ext; exact x.2
      }
  2. The top-left block M₁₁ is the 1 × 1 identity matrix.

    By extensionality on indices i, j ∈ P, since P has a unique element (Subsingleton.elim), we have i = j with underlying vertex v. By Matrix.one_apply_eq, the entry of the identity matrix is 1. The corresponding entry of the petrial matrix is A(G)ᵥᵥ + [v ∈ F]. Because simple graphs have no self-loops, A(G)ᵥᵥ = 0, and since v ∈ F by hypothesis, this diagonal entry is 1.

    lines 11–20

    uses Subsingleton.elim, Matrix.one_apply_eq

      have hA : M.toBlocks₁₁ = 1 := by
        ext i j
        have hi : (i : V) = v := i.2
        have hj : (j : V) = v := j.2
        have hij : i = j := Subsingleton.elim _ _
        subst j
        simp only [Matrix.one_apply_eq]
        change (petrial_matrix G F) i.1 i.1 = 1
        rw [hi]
        simp [petrial_matrix, hF]
  3. The rank of M equals 1 + rank(M₂₂ - M₂₁ * M₁₂).

    Because M₁₁ = 1 is invertible (invertibleOne), we apply the Schur complement rank formula (petrial_rank_schur_invertible). Using card(P) = 1 (Fintype.card_unique), ⅟1 = 1 (invOf_one), M₂₁ * 1 = M₂₁ (Matrix.mul_one), and reconstructing M from its blocks (Matrix.fromBlocks_toBlocks), the rank of M is 1 plus the rank of its Schur complement M₂₂ - M₂₁ * M₁₂.

    lines 21–24

    uses invertibleOne, petrial_rank_schur_invertible, invOf_one, Matrix.mul_one, Fintype.card_unique, Matrix.fromBlocks_toBlocks

      letI : Invertible (1 : Matrix P P (ZMod 2)) := invertibleOne
      have hschur := petrial_rank_schur_invertible (1 : Matrix P P (ZMod 2)) M.toBlocks₁₂ M.toBlocks₂₁ M.toBlocks₂₂
      simp only [invOf_one, Matrix.mul_one, Fintype.card_unique] at hschur
      rw [← hA, Matrix.fromBlocks_toBlocks] at hschur
  4. The Schur complement M₂₂ - M₂₁ * M₁₂ equals the petrial matrix of the induced subgraph G[V \ {v}] with perturbation set toggled at u.

    We verify entrywise equality at indices (i, j) ∈ Pᶜ × Pᶜ. Expanding matrix subtraction and multiplication (Matrix.sub_apply, Matrix.mul_apply), the product (M₂₁ * M₁₂)ᵢⱼ sums over the unique element v of P (Fintype.sum_unique), yielding Mᵢᵥ * Mᵥⱼ. Because i, j ≠ v, the diagonal perturbation contributes 0 to Mᵢᵥ and Mᵥⱼ. Since u is the unique neighbor of v, G.Adj i v ↔ i = u and G.Adj v j ↔ j = u. Thus Mᵢᵥ * Mᵥⱼ is 1 if i = j = u and 0 otherwise. When i ≠ j, this product is 0, leaving the off-diagonal adjacency entry unchanged, which matches the induced subgraph adjacency (SimpleGraph.induce_adj). When i = j ≠ u, the product is 0, leaving the diagonal perturbation unchanged. When i = j = u, subtracting 1 in ℤ/2ℤ flips the diagonal entry between 0 and 1, which corresponds precisely to toggling whether u belongs to the perturbation set (Finset.mem_filter).

    lines 25–54

    uses Matrix.sub_apply, Matrix.mul_apply, Fintype.sum_unique, Matrix.add_apply, SimpleGraph.adjMatrix_apply, Matrix.diagonal_apply, Finset.mem_filter, Finset.mem_univ, true_and, SimpleGraph.induce_adj, Ne.symm, if_false, Subtype.ext

      have hmat : M.toBlocks₂₂ - M.toBlocks₂₁ * M.toBlocks₁₂ =
          petrial_matrix (G.induce ({v}ᶜ : Set V)) (petrial_leaf_flip v u F) := by
        ext i j
        simp only [Matrix.sub_apply, Matrix.mul_apply, Fintype.sum_unique]
        change (petrial_matrix G F) i.1 j.1 - (petrial_matrix G F) i.1 v *
          (petrial_matrix G F) v j.1 = _
        simp only [petrial_matrix, Matrix.add_apply, SimpleGraph.adjMatrix_apply,
          Matrix.diagonal_apply, Finset.mem_filter, Finset.mem_univ, true_and,
          petrial_leaf_flip, SimpleGraph.induce_adj]
        have hiv : (i : V) ≠ v := i.2
        have hjv : (j : V) ≠ v := j.2
        have ha : G.Adj (i : V) v ↔ (i : V) = u := by
          constructor
          · intro h; exact huniq _ h.symm
          · intro h; rw [h]; exact hu.symm
        have hb : G.Adj v (j : V) ↔ (j : V) = u := by
          constructor
          · exact huniq _
          · intro h; rw [h]; exact hu
        simp only [hiv, Ne.symm hjv, if_false, ha, hb, Finset.mem_filter,
          Finset.mem_univ, true_and]
        by_cases hij : i = j
        · subst j
          by_cases hiu : (i : V) = u <;> by_cases hf : (i : V) ∈ F <;>
            simp_all <;> try ring_nf
        · have hijv : (i : V) ≠ (j : V) := fun h => hij (Subtype.ext h)
          by_cases hiu : (i : V) = u
          · have hju : (j : V) ≠ u := fun h => hijv (hiu.trans h.symm)
            simp [hij, hijv, hiu, hju, Ne.symm hju]
          · simp [hij, hijv, hiu]
  5. The rank of the original petrial matrix on G equals 1 plus the rank of the petrial matrix on G[V \ {v}] with the perturbation at u toggled.

    Rewriting with the Schur complement identity hmat replaces M₂₂ - M₂₁ * M₁₂ in hschur with the petrial matrix of the induced subgraph. The tactic simpa unfolds M, using the fact that reindexing along an equivalence of types preserves matrix rank to complete the proof.

    lines 55–56

      rw [hmat] at hschur
      simpa [M] using hschur
Equiv.Set.sumCompl
Canonical equivalence between the disjoint sum s ⊕ sᶜ and the ambient type α.
Finset.mem_filter
An element a belongs to Finset.filter p s if and only if a ∈ s and p(a) holds.
Finset.mem_univ
Every element of a finite type belongs to the universal finset Finset.univ.
Fintype.card_unique
A finite type with a unique element has cardinality 1.
Fintype.sum_unique
The sum of a function over a type with a unique element is the value of the function at that default element.
if_false
The conditional expression (if False then t else e) evaluates to e.
invOf_one
The inverse ⅟1 of the identity element 1 is 1.
invertibleOne
The identity element 1 in a monoid is invertible.
Matrix.add_apply
The (i, j) entry of the sum of two matrices A + B is A i j + B i j.
Matrix.diagonal_apply
Entry (i, j) of a diagonal matrix is d(i) if i = j and 0 otherwise.
Matrix.fromBlocks_toBlocks
Reconstructing a block matrix from its four constituent blocks recovers the original block matrix.
Matrix.mul_apply
The (i, k) entry of the product M * N is the sum ∑ j, M i j * N j k.
Matrix.mul_one
Multiplying a matrix on the right by the identity matrix leaves it unchanged: M * 1 = M.
Matrix.one_apply_eq
The diagonal entry (i, i) of the identity matrix 1 is 1.
Matrix.sub_apply
The (i, j) entry of the difference of two matrices A - B is A i j - B i j.
Ne.symm
Inequality is symmetric: if a ≠ b, then b ≠ a.
petrial_rank_schur_invertible
The rank of a block matrix with invertible top-left block A equals the size of A plus the rank of the Schur complement D - C * ⅟A * B.
SimpleGraph.adjMatrix_apply
Entry (v, w) of the adjacency matrix of a simple graph is 1 if v is adjacent to w, and 0 otherwise.
SimpleGraph.induce_adj
Two vertices in an induced subgraph are adjacent if and only if they are adjacent in the ambient graph.
Subsingleton.elim
Any two elements of a subsingleton type are equal.
Subtype.ext
Two elements of a subtype are equal if and only if their underlying values are equal.
true_and
The conjunction True ∧ p is equivalent to p.

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_one_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 = 1 + (petrial_matrix (G.induce ({v}ᶜ : Set V)) (petrial_leaf_flip v u F)).rank := by  classical  let P : Set V := {v}  let e := Equiv.Set.sumCompl P  let M := (petrial_matrix G F).submatrix e e  have hn : u ≠ v := (G.ne_of_adj hu).symm  letI : Unique P := {    default := ⟨v, by simp [P]⟩    uniq := by intro x; apply Subtype.ext; exact x.2  }  have hA : M.toBlocks₁₁ = 1 := by    ext i j    have hi : (i : V) = v := i.2    have hj : (j : V) = v := j.2    have hij : i = j := Subsingleton.elim _ _    subst j    simp only [Matrix.one_apply_eq]    change (petrial_matrix G F) i.1 i.1 = 1    rw [hi]    simp [petrial_matrix, hF]  letI : Invertible (1 : Matrix P P (ZMod 2)) := invertibleOne  have hschur := petrial_rank_schur_invertible (1 : Matrix P P (ZMod 2)) M.toBlocks₁₂ M.toBlocks₂₁ M.toBlocks₂₂  simp only [invOf_one, Matrix.mul_one, Fintype.card_unique] at hschur  rw [← hA, Matrix.fromBlocks_toBlocks] at hschur  have hmat : M.toBlocks₂₂ - M.toBlocks₂₁ * M.toBlocks₁₂ =      petrial_matrix (G.induce ({v}ᶜ : Set V)) (petrial_leaf_flip v u F) := by    ext i j    simp only [Matrix.sub_apply, Matrix.mul_apply, Fintype.sum_unique]    change (petrial_matrix G F) i.1 j.1 - (petrial_matrix G F) i.1 v *      (petrial_matrix G F) v j.1 = _    simp only [petrial_matrix, Matrix.add_apply, SimpleGraph.adjMatrix_apply,      Matrix.diagonal_apply, Finset.mem_filter, Finset.mem_univ, true_and,      petrial_leaf_flip, SimpleGraph.induce_adj]    have hiv : (i : V) ≠ v := i.2    have hjv : (j : V) ≠ v := j.2    have ha : G.Adj (i : V) v ↔ (i : V) = u := by      constructor      · intro h; exact huniq _ h.symm      · intro h; rw [h]; exact hu.symm    have hb : G.Adj v (j : V) ↔ (j : V) = u := by      constructor      · exact huniq _      · intro h; rw [h]; exact hu    simp only [hiv, Ne.symm hjv, if_false, ha, hb, Finset.mem_filter,      Finset.mem_univ, true_and]    by_cases hij : i = j    · subst j      by_cases hiu : (i : V) = u <;> by_cases hf : (i : V) ∈ F <;>        simp_all <;> try ring_nf    · have hijv : (i : V) ≠ (j : V) := fun h => hij (Subtype.ext h)      by_cases hiu : (i : V) = u      · have hju : (j : V) ≠ u := fun h => hijv (hiu.trans h.symm)        simp [hij, hijv, hiu, hju, Ne.symm hju]      · simp [hij, hijv, hiu]  rw [hmat] at hschur  simpa [M] using hschur
See it in the graphDiscuss this resultChallenge it