AFTD Auto-Formalizing Theoretical Domains

seidel_matrix

def

The Seidel matrix of a simple graph G is the matrix S with zero on the diagonal, -1 for adjacent pairs of vertices, and 1 for distinct nonadjacent pairs of vertices.

Statement

def seidel_matrix {V : Type*} [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] :
    Matrix V V ℤ
Defined in
arXiv:2610.36522 Section 2; Seidel (1968)
Verified
29 Oct 2026
Axioms
none listed
Used by 4
  • seidel_matrix_compl_codegree_eqFor any simple graph G on a finite vertex set V with Seidel matrix S and any pair of adjacent vertices u and v in the complement Gᶜ, four…
  • seidel_codegree_bounds_254For any simple graph G on 254 vertices with decidable adjacency whose Seidel matrix S has all row sums equal to 1 and (S^2)_{ij} ≤ 0 for…
  • seidel_matrix_codegree_eqFor any simple graph G on a finite vertex set V with Seidel matrix S and any pair of adjacent vertices u and v in G, four times the number…
  • seidel_matrix_row_sum_eq_degreeFor a finite simple graph G with decidable adjacency and any vertex i, the i-th Seidel row sum equals |V| - 1 - 2·deg(i), where deg(i) is…

Read back from the Lean

The definition seidel_matrix takes a type V with decidable equality and a simple graph G on V with a decidable adjacency relation, and defines a V × V matrix with integer entries whose (i, j)-entry is 0 if i = j, -1 if i ≠ j and i is adjacent to j in G, and 1 if i ≠ j and i is not adjacent to j in G.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- The Seidel matrix of a simple graph with decidable adjacency. -/
def seidel_matrix {V : Type*} [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] :
    Matrix V V ℤ :=
  Matrix.of fun i j => if i = j then 0 else if G.Adj i j then -1 else 1
See it in the graphDiscuss this resultChallenge it