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 ith and jth 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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: