# Matrices and Graphs

Recall in the post “Canonical Representation of Finitely Presented Coxeter Groups” we defined the Coxeter matrix of a Coxeter group $G$ by $a_{ij}=m_{ij}$ where $(r_ir_j)^{m_{ij}}=1$ with $r_i,r_j$ as the generators of the group.  We can also define the Coxeter graph of a Coxeter group $G$ whose vertices are the generators of the group.  Then since $m_{ij}\geq 2$ for $i\neq j,$ we will define edges between two generators iff $m_{i,j}\geq 3,$ and label the edge with $m_{ij}$ when $m_{ij}\geq 4.$

In a generic graph (recall our presentation with $V$ a set and $E$ a symmetric relation on $V^2$), we can define a $|V|\times |E|$ matrix, called the incidence matrix of $E$, denoted $[E],$ where

$a_{i,(j,k)}=\left\{\begin{array}{lcl}1&\mbox{if}&i=j \mbox{~or~} i=k\\ 0&\mbox{otherwise}&\end{array}\right .$

So $a_{i,(j,k)}$ is $1$ iff the vertex $i$ is a vertex on the edge $(j,k).$  This assumes some ordering of $V.$  So if we assume irreflexivity of $E,$ then every column, indexed by $(i,j),$ will have precisely two entries that are $1,$ specifically in the $i$th and $j$th row.

In the case of the incidence matrix of a Coxeter graph, the nonzero rows thus coincide with generators $r_i$ such that $m_{ij}\geq 3$ for some $j.$

We can remove the symmetric requirement of $E$; so $E$ is just a subset of $V^2.$  We can then use “binary relation” synonymously with “digraph“.  From here on we will assume a digraph on $V$ is an irreflexive binary relation on $V,$ and that a graph on $V$ is an irreflexive symmetric binary relation on $V.$

Definition 1.  Let $E_1$ and $E_2$ be digraphs on $V_1$ and $V_2$ respectively.  A map $\varphi:V_1\to V_2$ is an $(E_1,E_2)$-digraph homomorphism if $(x,y)\in E_1\Rightarrow$$(\varphi(x),\varphi(y))\in E_2.$  An $(E_1,E_2)$isomorphism of digraphs is a bijective $(E_1,E_2)$-homomorphism of digraphs.

Definition 2.  Let $E$ be a digraph on $V.$  We define the adjacency matrix of $E$, denoted $(E),$ as the $|V|\times |V|$ matrix where $a_{x,y}$ is the number of paths from $x$ to $y.$

So an entry $a_{i,(j,k)}\in [E]$ being $1$ means one of the entries $a_{i,j}$ or $a_{j,i}$ is $1$ in $(E)$ 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 $E_1$ and $E_2$ be digraphs on $V.$  There is an $(E_1,E_2)$-automorphism of $V$ iff there is a permutation matrix $P$ such that

$\displaystyle P^\top(E_1)P=(E_2).$

[1]  Godsil, Chris and Gordon Royle.  Algebraic Graph Theory.  Graduate Texts in Mathematics.  Vol. 207.  Springer Science and Business Media.  2004.