Recall in the post “Canonical Representation of Finitely Presented Coxeter Groups” we defined the Coxeter matrix of a Coxeter group by where with as the generators of the group. We can also define the Coxeter graph of a Coxeter group whose vertices are the generators of the group. Then since for we will define edges between two generators iff and label the edge with when
In a generic graph (recall our presentation with a set and a symmetric relation on ), we can define a matrix, called the incidence matrix of , denoted where
So is iff the vertex is a vertex on the edge This assumes some ordering of So if we assume irreflexivity of then every column, indexed by will have precisely two entries that are specifically in the th and th row.
In the case of the incidence matrix of a Coxeter graph, the nonzero rows thus coincide with generators such that for some
We can remove the symmetric requirement of ; so is just a subset of We can then use “binary relation” synonymously with “digraph“. From here on we will assume a digraph on is an irreflexive binary relation on and that a graph on is an irreflexive symmetric binary relation on
Definition 1. Let and be digraphs on and respectively. A map is an -digraph homomorphism if An –isomorphism of digraphs is a bijective -homomorphism of digraphs.
Definition 2. Let be a digraph on We define the adjacency matrix of , denoted as the matrix where is the number of paths from to
So an entry being means one of the entries or is in since being a vertex on an edge means there is a path to some other vertex (namely the other vertex on that edge).
Proposition 3. Let and be digraphs on There is an -automorphism of iff there is a permutation matrix such that
 Godsil, Chris and Gordon Royle. Algebraic Graph Theory. Graduate Texts in Mathematics. Vol. 207. Springer Science and Business Media. 2004.