tournament_of_symm_matrix_is_tournament
T(G) is a tournament for every matrix G over F₂ (only the entries above the diagonal are read).
Statement
theorem tournament_of_symm_matrix_is_tournament {n : ℕ} (G : Matrix (Fin n) (Fin n) (ZMod 2)) :
digraph_is_tournament (tournament_of_symm_matrix G)- Source
- Sanity lemma for tournament_of_symm_matrix (arXiv:2610.13798).
- Verified
- 13 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- tournament_of_symm_matrixThe tournament T(G) of a symmetric n × n matrix G over F₂, on vertices 1, …, n: for i < j the arc goes i → j if G_ij = 0 and j → i if G_ij…
- digraph_is_tournamentA digraph is a tournament when it has no loops and between any two distinct vertices there is exactly one arc.
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
The proof, explained
To show that the graph defined by G is a tournament, the proof checks that there are no self-loops and that between any two distinct vertices exactly one directed edge is present. The absence of self-loops holds because adjacency requires a strict inequality between vertex indices, which is impossible for a vertex and itself. For distinct vertices i ≠ j, trichotomy divides into the cases i < j and j < i; in each case, whether the corresponding matrix entry is 0 or 1 uniquely determines which of the two directed edges is present.
Every element of ℤ/2ℤ is either 0 or 1.
Since ℤ/2ℤ has only two elements, the disjunction a = 0 ∨ a = 1 holds for all elements by finite exhaustion, verified by decide.
have two : ∀ a : ZMod 2, a = 0 ∨ a = 1 := by decide
To show that the constructed graph is a tournament, it suffices to prove that it has no self-loops and that between any two distinct vertices there is a directed edge in exactly one direction.
By definition, a directed graph is a tournament (digraph_is_tournament) if no vertex has a self-loop (∀ i, ¬ Adj i i) and for all distinct pairs i ≠ j, having an edge from i to j is equivalent to not having an edge from j to i (Adj i j ↔ ¬ Adj j i). We split the proof into these two independent goals.
refine ⟨fun i => ?_, fun i j hij => ?_⟩
The graph contains no self-loops.
By definition of tournament_of_symm_matrix, an edge from i to j requires either i < j or j < i. When i = j, the strict inequality i < i is false in both disjuncts, so ¬ Adj i i holds immediately.
· simp [tournament_of_symm_matrix]For distinct vertices i ≠ j, it suffices to consider separately the cases i < j and j < i.
Unfolding the definition of adjacency between i and j, we must show that (i < j ∧ G i j = 0 ∨ j < i ∧ G j i = 1) is equivalent to ¬ (j < i ∧ G j i = 0 ∨ i < j ∧ G i j = 1). Since i ≠ j, totality of the linear order on Fin n gives either i < j or j < i.
uses
lt_or_gt_of_ne· simp only [tournament_of_symm_matrix] rcases lt_or_gt_of_ne hij with h | h
When i < j, exactly one directed edge connects i and j.
Since i < j, the reverse inequality j < i is false (by not_lt_of_gt). The matrix entry G i j must be either 0 or 1: if G i j = 0, then the directed edge (i, j) exists and (j, i) does not; if G i j = 1, then (i, j) does not exist and (j, i) does. In both cases, the equivalence holds.
uses
not_lt_of_gt· rcases two (G i j) with h0 | h0 <;> simp [h, h0, not_lt_of_gt h]
When j < i, exactly one directed edge connects i and j.
Symmetrically, since j < i, the reverse inequality i < j is false (by not_lt_of_gt). The matrix entry G j i is either 0 or 1: if G j i = 0, the edge (j, i) exists and (i, j) does not; if G j i = 1, the edge (i, j) exists and (j, i) does not. In both cases, the equivalence holds.
uses
not_lt_of_gt· rcases two (G j i) with h0 | h0 <;> simp [h, h0, not_lt_of_gt h]
lt_or_gt_of_ne- In a linear order, any two distinct elements satisfy a < b or b < a.
not_lt_of_gt- In a preorder, if a < b then b < a is false.
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 tournament_of_symm_matrix_is_tournament {n : ℕ} (G : Matrix (Fin n) (Fin n) (ZMod 2)) : digraph_is_tournament (tournament_of_symm_matrix G) := by have two : ∀ a : ZMod 2, a = 0 ∨ a = 1 := by decide refine ⟨fun i => ?_, fun i j hij => ?_⟩ · simp [tournament_of_symm_matrix] · simp only [tournament_of_symm_matrix] rcases lt_or_gt_of_ne hij with h | h · rcases two (G i j) with h0 | h0 <;> simp [h, h0, not_lt_of_gt h] · rcases two (G j i) with h0 | h0 <;> simp [h, h0, not_lt_of_gt h]