AFTD Auto-Formalizing Theoretical Domains

tournament_reverse_arc_laplacian_diff

theoremverified

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\}$.

  1. 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.

    lines 8–9

    uses Matrix.of_apply

      ext i j
      rw [Matrix.of_apply]
  2. 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)$.

    lines 10–16

      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
  3. 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}$.

    lines 17–32

    uses Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_erase, Finset.card_erase_of_mem, Finset.card_pos.mpr

      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
  4. 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}$.

    lines 33–46

    uses Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_insert, Finset.card_insert_of_notMem

      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
  5. 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.

    lines 47–59

    uses Finset.mem_filter, Finset.mem_univ, true_and

      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]
  6. 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.

    lines 60–63

    uses Matrix.sub_apply, Matrix.diagonal_apply, Matrix.of_apply

      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
  7. 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.

    lines 64–73

    uses Ne.symm

      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]
  8. 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.

    lines 74–83

    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]
  9. 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.

    lines 84–85

        · 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$.

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

/-- 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]
See it in the graphDiscuss this resultChallenge it