petrial_leaf_one_pivot
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
- petrial_nullity_poly_leaf_recFor a finite graph G with a degree-one vertex v whose neighbour is u, the nullity generating polynomial of G equals the nullity generating…
- op_1239_candidate36_petrial_coefficientsThe partial Petrial coefficients of op_1239_candidate36 in ranks 27, 28, and 29 are respectively 256, 32640, and 4666944.
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.
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.
uses
Equiv.Set.sumCompl,Subtype.extclassical 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 }
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.
uses
Subsingleton.elim,Matrix.one_apply_eqhave 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]
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₁₂.
uses
invertibleOne,petrial_rank_schur_invertible,invOf_one,Matrix.mul_one,Fintype.card_unique,Matrix.fromBlocks_toBlocksletI : 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
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).
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.exthave 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]
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.
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.
- Reindexing the rows and columns of a matrix by an equivalence of index types (here e : P ⊕ Pᶜ ≃ V) preserves its rank; Lean's simplifier applies this automatically in the final step.
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.
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