tournament_reverse_arc_laplacian_diff
Reversing an arc u → v of a tournament updates the out-degree Laplacian by an explicit rank-one matrix (e_u + e_v)(e_v - e_u)^T.
Statement
theorem tournament_reverse_arc_laplacian_diff {n : ℕ} (T : Digraph (Fin n)) [DecidableRel T.Adj] (hT : digraph_is_tournament T) (u v : Fin n) (huv : T.Adj u v) : digraph_out_laplacian (digraph_reverse_arc T u v) - digraph_out_laplacian T = Matrix.of (fun i j => (if i = u ∨ i = v then (1 : ℝ) else 0) * (if j = v then (1 : ℝ) else if j = u then -1 else 0))
- Source
- step towards tournament_reverse_arc_arborescence_count_lt
- Verified
- 01 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- digraph_reverse_arcThe digraph obtained from D by reversing the arc between u and v: the two vertices exchange which of them points to the other, and every…
- digraph_is_tournamentA digraph is a tournament when it has no loops and between any two distinct vertices there is exactly one arc.
- digraph_out_laplacianThe out-degree Laplacian L_D of a digraph D on Fin n over ℝ: its diagonal entries are the out-degrees and its off-diagonal (i,j) entry is…
- digraph_out_countThe out-degree of the vertex v of a digraph on Fin n.
The proof, explained
The out-degree Laplacian is defined as $L(D) = D_{\mathrm{out}} - A(D)$, the diagonal matrix of out-degrees minus the adjacency matrix. Reversing a single arc $u \to v$ in a tournament replaces $u \to v$ by $v \to u$ while leaving all other arcs unchanged; this decreases the out-degree of $u$ by 1, increases that of $v$ by 1, and leaves all other out-degrees intact. The proof verifies by matrix extensionality and case analysis on vertex indices $(i, j)$ that the resulting difference $\Delta L = \Delta D_{\mathrm{out}} - \Delta A$ matches the rank-one update matrix $(e_u + e_v)(e_v - e_u)^T$, which is non-zero only on the $2 \times 2$ block indexed by $\{u, v\}$.
It suffices to verify entrywise that for all indices $i$ and $j$, the $(i, j)$ entry of the Laplacian difference equals $([i = u \lor i = v])([j = v] - [j = u])$.
Applying matrix extensionality (`ext i j`) reduces matrix equality to showing that the entries match at every pair $(i, j)$. Rewriting with `Matrix.of_apply` unpacks the definition of the target matrix on the right-hand side.
uses
Matrix.of_applyext i j rw [Matrix.of_apply]
Vertices $u$ and $v$ are distinct ($u \neq v$), and there is no directed arc $v \to u$ in $T$.
Since tournaments have no self-loops ($T$ is irreflexive), the existence of an arc $u \to v$ forces $u \neq v$. Furthermore, the tournament axiom guarantees that for distinct vertices $u$ and $v$, exactly one of $u \to v$ or $v \to u$ holds; hence $u \to v$ implies $\neg(v \to u)$.
have unev : u ≠ v := by rintro rfl exact hT.1 u huv have unev' : v ≠ u := unev.symm have hvu : ¬ T.Adj v u := by intro h exact (hT.2 u v unev).mp huv h
In the reversed tournament, the out-degree of vertex $u$ is $d_{\mathrm{out}}(u) - 1$.
The out-neighborhood of $u$ in the reversed digraph is obtained by removing $v$ from its original out-neighborhood in $T$, as verified by set extensionality (`h_filter`). Because $v$ was an out-neighbor of $u$ (`hmem`), removing it decreases the finset cardinality by 1 (`Finset.card_erase_of_mem`). Since the set contains $v$, its size is at least 1 (`Finset.card_pos.mpr`), so the subtraction casts correctly to $\mathbb{R}$.
uses
Finset.mem_filter,Finset.mem_univ,true_and,Finset.mem_erase,Finset.card_erase_of_mem,Finset.card_pos.mprhave out_u : (digraph_out_count (digraph_reverse_arc T u v) u : ℝ) = (digraph_out_count T u : ℝ) - 1 := by have h_filter : Finset.filter (fun w => (digraph_reverse_arc T u v).Adj u w) Finset.univ = (Finset.filter (fun w => T.Adj u w) Finset.univ).erase v := by ext w simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_erase] by_cases hw : w = v · subst hw; simp [unev, hvu] · simp [hw, unev] unfold digraph_out_count rw [h_filter] have hmem : v ∈ Finset.filter (fun w => T.Adj u w) Finset.univ := by simp [huv] rw [Finset.card_erase_of_mem hmem] have hpos : 1 ≤ (Finset.filter (fun w => T.Adj u w) Finset.univ).card := Finset.card_pos.mpr ⟨v, hmem⟩ push_cast [hpos] rfl
In the reversed tournament, the out-degree of vertex $v$ is $d_{\mathrm{out}}(v) + 1$.
The out-neighborhood of $v$ in the reversed digraph is obtained by inserting $u$ into the original out-neighborhood in $T$ (`h_filter`). Since $u$ was not an out-neighbor of $v$ (`hnmem`), inserting it increases the cardinality by 1 (`Finset.card_insert_of_notMem`), which casts directly to $\mathbb{R}$.
uses
Finset.mem_filter,Finset.mem_univ,true_and,Finset.mem_insert,Finset.card_insert_of_notMemhave out_v : (digraph_out_count (digraph_reverse_arc T u v) v : ℝ) = (digraph_out_count T v : ℝ) + 1 := by have h_filter : Finset.filter (fun w => (digraph_reverse_arc T u v).Adj v w) Finset.univ = insert u (Finset.filter (fun w => T.Adj v w) Finset.univ) := by ext w simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_insert] by_cases hw : w = u · subst hw; simp [unev', huv] · simp [hw, unev'] unfold digraph_out_count rw [h_filter] have hnmem : u ∉ Finset.filter (fun w => T.Adj v w) Finset.univ := by simp [hvu] rw [Finset.card_insert_of_notMem hnmem] push_cast rfl
For any vertex $k \notin \{u, v\}$, the out-degree is unchanged.
Reversing the arc between $u$ and $v$ only modifies adjacency between $u$ and $v$. For any vertex $k$ distinct from both $u$ and $v$, the condition for having an outgoing arc to $w$ in the reversed graph is logically equivalent to that in $T$, so its out-neighborhood and cardinality remain the same.
uses
Finset.mem_filter,Finset.mem_univ,true_andhave out_other : ∀ k, k ≠ u → k ≠ v → (digraph_out_count (digraph_reverse_arc T u v) k : ℝ) = (digraph_out_count T k : ℝ) := by intro k hku hkv have h : digraph_out_count (digraph_reverse_arc T u v) k = digraph_out_count T k := by unfold digraph_out_count congr 1 ext w simp only [Finset.mem_filter, Finset.mem_univ, true_and] have h1 : ¬ (k = u ∧ w = v) := fun h => hku h.1 have h2 : ¬ (k = v ∧ w = u) := fun h => hkv h.1 show (if (k = u ∧ w = v) ∨ (k = v ∧ w = u) then T.Adj w k else T.Adj k w) ↔ T.Adj k w simp [h1, h2] rw [h]
The $(i, j)$ entry of the Laplacian difference is expanded in terms of diagonal out-degree changes and off-diagonal adjacency changes.
Rewriting with `Matrix.sub_apply`, unfolding `digraph_out_laplacian`, and simplifying with `Matrix.diagonal_apply` and `Matrix.of_apply` writes the difference entry as $(\delta_{i j} d'_{\mathrm{out}}(i) - [i \to' j]) - (\delta_{i j} d_{\mathrm{out}}(i) - [i \to j])$. The absence of self-loops in $T$ (`hTloop`) is also noted.
uses
Matrix.sub_apply,Matrix.diagonal_apply,Matrix.of_applyrw [Matrix.sub_apply] unfold digraph_out_laplacian simp only [Matrix.sub_apply, Matrix.diagonal_apply, Matrix.of_apply] have hTloop : ∀ x, ¬ T.Adj x x := hT.1
The matrix equality holds across row $u$ ($i = u$).
Substituting $i = u$ uses the degree relation $d'_{\mathrm{out}}(u) = d_{\mathrm{out}}(u) - 1$. A case split on $j$ evaluates the entries: if $j = v$, the diagonal term is 0 since $u \neq v$, while the adjacency change is $-(0) - (-1) = 1$, matching $1 \times 1 = 1$; if $j = u$, self-loops vanish and the diagonal degree drops by 1, yielding $-1$, matching $1 \times (-1) = -1$; and if $j \notin \{u, v\}$, the non-diagonal, unmodified edges cancel out to 0.
uses
Ne.symmby_cases hiu : i = u · subst i rw [out_u] by_cases hjv : j = v · subst j simp [unev, unev', huv, hvu] · by_cases hju : j = u · subst j simp [unev, hTloop u] · simp [unev, hjv, hju, Ne.symm hju]
The matrix equality holds across row $v$ ($i = v$).
Substituting $i = v$ (with $i \neq u$) uses $d'_{\mathrm{out}}(v) = d_{\mathrm{out}}(v) + 1$. Case analysis on $j$ yields: if $j = v$, the diagonal degree increases by 1, giving 1, matching $1 \times 1 = 1$; if $j = u$, the diagonal term is 0 and the adjacency change is $-(1) - (0) = -1$, matching $1 \times (-1) = -1$; and if $j \notin \{u, v\}$, both sides evaluate to 0.
uses
Ne.symm· by_cases hiv : i = v · subst i rw [out_v] by_cases hjv : j = v · subst j simp [unev', hTloop v] · by_cases hju : j = u · subst j simp [unev, unev', huv, hvu] · simp [unev', hjv, Ne.symm hjv, hju]
The matrix equality holds for all other rows ($i \notin \{u, v\}$).
When $i \neq u$ and $i \neq v$, `out_other` shows that out-degrees do not change, and no edges incident to $i$ were altered. The left-hand side reduces to 0, matching the right-hand side where the row indicator $[i = u \lor i = v]$ is zero.
· rw [out_other i hiu hiv] simp [hiu, hiv]
Matrix.of_apply- The $(i, j)$ entry of a matrix constructed from a function $f$ equals $f(i, j)$.
Finset.mem_filter- An element belongs to `Finset.filter p s` if and only if it belongs to $s$ and satisfies $p$.
Finset.mem_univ- Every element of a finite type belongs to the universal finset `Finset.univ`.
true_and- The proposition $\text{True} \land p$ is logically equivalent to $p$.
Finset.mem_erase- An element $a$ belongs to $s \setminus \{b\}$ if and only if $a \neq b$ and $a \in s$.
Finset.card_erase_of_mem- If $a \in s$, the cardinality of $s \setminus \{a\}$ is $|s| - 1$.
Finset.card_pos.mpr- A finset has strictly positive cardinality if it is nonempty.
Finset.mem_insert- An element $a$ belongs to $\{b\} \cup s$ if and only if $a = b$ or $a \in s$.
Finset.card_insert_of_notMem- If $a \notin s$, the cardinality of $\{a\} \cup s$ is $|s| + 1$.
Matrix.sub_apply- The $(i, j)$ entry of the matrix difference $A - B$ is $A(i, j) - B(i, j)$.
Matrix.diagonal_apply- The $(i, j)$ entry of a diagonal matrix with diagonal $d$ is $d(i)$ if $i = j$ and $0$ otherwise.
Ne.symm- Inequality is symmetric: $a \neq b$ implies $b \neq a$.
- The rank-one update $(e_u + e_v)(e_v - e_u)^T$ is expressed entrywise as the scalar product $([i = u \lor i = v]) \cdot ([j = v] - [j = u])$ rather than via an explicit vector outer product.
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.
/-- Reversing an arc u → v of a tournament updates the out-degree Laplacian by the explicit rank-one matrix (e_u + e_v)(e_v - e_u)^T. -/theorem tournament_reverse_arc_laplacian_diff {n : ℕ} (T : Digraph (Fin n)) [DecidableRel T.Adj] (hT : digraph_is_tournament T) (u v : Fin n) (huv : T.Adj u v) : digraph_out_laplacian (digraph_reverse_arc T u v) - digraph_out_laplacian T = Matrix.of (fun i j => (if i = u ∨ i = v then (1 : ℝ) else 0) * (if j = v then (1 : ℝ) else if j = u then -1 else 0)) := by ext i j rw [Matrix.of_apply] have unev : u ≠ v := by rintro rfl exact hT.1 u huv have unev' : v ≠ u := unev.symm have hvu : ¬ T.Adj v u := by intro h exact (hT.2 u v unev).mp huv h have out_u : (digraph_out_count (digraph_reverse_arc T u v) u : ℝ) = (digraph_out_count T u : ℝ) - 1 := by have h_filter : Finset.filter (fun w => (digraph_reverse_arc T u v).Adj u w) Finset.univ = (Finset.filter (fun w => T.Adj u w) Finset.univ).erase v := by ext w simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_erase] by_cases hw : w = v · subst hw; simp [unev, hvu] · simp [hw, unev] unfold digraph_out_count rw [h_filter] have hmem : v ∈ Finset.filter (fun w => T.Adj u w) Finset.univ := by simp [huv] rw [Finset.card_erase_of_mem hmem] have hpos : 1 ≤ (Finset.filter (fun w => T.Adj u w) Finset.univ).card := Finset.card_pos.mpr ⟨v, hmem⟩ push_cast [hpos] rfl have out_v : (digraph_out_count (digraph_reverse_arc T u v) v : ℝ) = (digraph_out_count T v : ℝ) + 1 := by have h_filter : Finset.filter (fun w => (digraph_reverse_arc T u v).Adj v w) Finset.univ = insert u (Finset.filter (fun w => T.Adj v w) Finset.univ) := by ext w simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_insert] by_cases hw : w = u · subst hw; simp [unev', huv] · simp [hw, unev'] unfold digraph_out_count rw [h_filter] have hnmem : u ∉ Finset.filter (fun w => T.Adj v w) Finset.univ := by simp [hvu] rw [Finset.card_insert_of_notMem hnmem] push_cast rfl have out_other : ∀ k, k ≠ u → k ≠ v → (digraph_out_count (digraph_reverse_arc T u v) k : ℝ) = (digraph_out_count T k : ℝ) := by intro k hku hkv have h : digraph_out_count (digraph_reverse_arc T u v) k = digraph_out_count T k := by unfold digraph_out_count congr 1 ext w simp only [Finset.mem_filter, Finset.mem_univ, true_and] have h1 : ¬ (k = u ∧ w = v) := fun h => hku h.1 have h2 : ¬ (k = v ∧ w = u) := fun h => hkv h.1 show (if (k = u ∧ w = v) ∨ (k = v ∧ w = u) then T.Adj w k else T.Adj k w) ↔ T.Adj k w simp [h1, h2] rw [h] rw [Matrix.sub_apply] unfold digraph_out_laplacian simp only [Matrix.sub_apply, Matrix.diagonal_apply, Matrix.of_apply] have hTloop : ∀ x, ¬ T.Adj x x := hT.1 by_cases hiu : i = u · subst i rw [out_u] by_cases hjv : j = v · subst j simp [unev, unev', huv, hvu] · by_cases hju : j = u · subst j simp [unev, hTloop u] · simp [unev, hjv, hju, Ne.symm hju] · by_cases hiv : i = v · subst i rw [out_v] by_cases hjv : j = v · subst j simp [unev', hTloop v] · by_cases hju : j = u · subst j simp [unev, unev', huv, hvu] · simp [unev', hjv, Ne.symm hjv, hju] · rw [out_other i hiu hiv] simp [hiu, hiv]