digraph_out_laplacian
def
The 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 -1 when i → j and 0 otherwise (equivalently L_D = diag(out-degree) - A_D).
Statement
noncomputable def digraph_out_laplacian {n : ℕ} (D : Digraph (Fin n)) [DecidableRel D.Adj] : Matrix (Fin n) (Fin n) ℝ
- Source
- step towards tournament_arborescence_hadamard_bound
- Verified
- 21 Oct 2026
- Axioms
- none listed
- Built on 1
- digraph_out_countThe out-degree of the vertex v of a digraph on Fin n.
- Used by 1
- tournament_reverse_arc_laplacian_diffReversing 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.
Lean source view module on GitHub
/-- The out-degree Laplacian of a digraph on `Fin n`: out-degrees on the diagonal, `-1` at each arc, `0` elsewhere. -/ noncomputable def digraph_out_laplacian {n : ℕ} (D : Digraph (Fin n)) [DecidableRel D.Adj] : Matrix (Fin n) (Fin n) ℝ := Matrix.diagonal (fun i => (digraph_out_count D i : ℝ)) - Matrix.of (fun i j => if D.Adj i j then (1 : ℝ) else 0)