digraph_flip_by_matrix_zero
Flipping by the zero matrix changes nothing.
Statement
theorem digraph_flip_by_matrix_zero {V : Type*} (D : Digraph V) : digraph_flip_by_matrix D 0 = D
- Source
- Sanity lemma for digraph_flip_by_matrix (arXiv:2610.13798, Sec. 2.2).
- Verified
- 13 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- digraph_flip_by_matrixGiven a digraph D and a (symmetric) matrix M over F₂ indexed by its vertices, the digraph obtained by reversing every arc uv with M_uv = 1…
- Used by 1
- tournament_min_rank_eq_zero_of_is_acyclicAn acyclic digraph has tournament minimum rank 0 (the zero matrix decycles it).
The proof, explained
The proof establishes that flipping a directed graph D by the zero matrix returns D by checking equality on all edges. Unfolding the definition of `digraph_flip_by_matrix` with matrix 0, every matrix entry is 0 ≠ 1 in ℤ/2ℤ, so no edges are reversed and the adjacency relation is unchanged.
To prove the two directed graphs are equal, it suffices to show they have identical adjacency relations on all pairs of vertices x and y.
By extensionality for directed graphs (`ext x y`), two graphs are equal if and only if for every pair of vertices x, y ∈ V, there is an edge from x to y in the first graph if and only if there is an edge from x to y in the second graph.
ext x yFor any vertices x and y, the flipped graph has an edge from x to y if and only if the original graph D has an edge from x to y.
Unfolding the definition of `digraph_flip_by_matrix`, the adjacency condition for the zero matrix is (0 x y = 1 ∧ D.Adj y x) ∨ (0 x y ≠ 1 ∧ D.Adj x y). In ℤ/2ℤ, the entry 0 is not equal to 1, making the first clause false and the second clause equivalent to D.Adj x y; the simplifier discharges the equivalence.
uses
digraph_flip_by_matrixsimp [digraph_flip_by_matrix]
digraph_flip_by_matrix- The operation that modifies a directed graph according to a matrix over ℤ/2ℤ, keeping the edge direction (x → y) where the matrix entry is 0 and reversing it (to y → x) where the entry is 1.
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 digraph_flip_by_matrix_zero {V : Type*} (D : Digraph V) : digraph_flip_by_matrix D 0 = D := by ext x y simp [digraph_flip_by_matrix]