digraph_flip_by_matrix
def
Given 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 and keeping the others.
Statement
def digraph_flip_by_matrix {V : Type*} (D : Digraph V) (M : Matrix V V (ZMod 2)) : Digraph V
- Defined in
- arXiv:2610.13798 (On the failure of additivity of inversion numbers for dijoins), Sec. 2.2 (decycling matrix: flipping all arcs uv with M_uv = 1).
- Verified
- 13 Oct 2026
- Axioms
- none listed
- Used by 7
- tournament_exists_decycling_matrixEvery finite tournament has a symmetric decycling matrix over F₂ (so its minimum rank is attained).
- tournament_min_rankThe tournament minimum rank tmr(D): the least F₂-rank of a symmetric matrix M over F₂ that decycles D, i.e. such that reversing every arc…
- tournament_min_rank_le_dijoinFor finite tournaments D₁, D₂: tmr(D₁ → D₂) ≥ max(tmr(D₁), tmr(D₂)) (hence ≥ (tmr(D₁) + tmr(D₂))/2), because the principal submatrix of a…
- tournament_min_rank_le_inversion_numberFor a finite tournament D: tmr(D) ≤ inv(D).
- digraph_flip_by_matrix_zeroFlipping by the zero matrix changes nothing.
- tournament_min_rank_eq_zero_of_is_acyclicAn acyclic digraph has tournament minimum rank 0 (the zero matrix decycles it).
- tournament_min_rank_dijoin_le_of_symm_invLet B be an invertible symmetric n × n matrix over F₂, L the lower triangular all-ones matrix, and A = L B⁻¹ Lᵀ. Then the tournaments D₁ =…
Lean source view module on GitHub
/-- Reverse every arc `u v` of `D` with `M u v = 1`, keep the others. -/ def digraph_flip_by_matrix {V : Type*} (D : Digraph V) (M : Matrix V V (ZMod 2)) : Digraph V where Adj x y := (M x y = 1 ∧ D.Adj y x) ∨ (M x y ≠ 1 ∧ D.Adj x y)