Tag Archives: relations (math)

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.

A Bit on Graphs

I was never a big fan of the presentation of graphs as sets of vertices and edges (say V and E) such that elements of E had the form e_{x,y} with x,y\in V and e_{x,y}=e_{y,x}.  I prefer to use the language of relations.

Definition 1.  A graph on X is a symmetric binary relation E on X.  We then call X the set of vertices and E the set of edges.

Recall a binary relation on X is a subset of X^2.  They are equivalent notions, but in the latter, one simply has a set with a relation on it–rather than these two separate sets such that the second set backtracks to the first as a relation.

Example 2.  A complete graph (one in which any two vertices are adjoined by an edge) is thus simply a graph where every x\in X is almost surjective with respect to E, by which I mean if we let

\displaystyle (x,X-\{x\})=\{(x,y):x\neq y\in X\},

then (x,X-\{x\})\subseteq E for all x\in X.  In particular we hence have

\displaystyle E=\bigcup_{x\in X}(x,X-\{x\}).

When I say a vertex is surjective with respect to E, I mean it has an edge with all other vertices (where almost-surjective excludes an edge with itself).  Note the relation E is always a surjective relation if we assume every vertex has some edge connected to it (i.e. is left-total and hence surjective since domain=codomain).  But a surjective relation E of course does not imply every element is surjective with respect to E.

Example 3.  A connected graph is a graph such that for any distinct two x,y\in X, there is a sequence (or path) x=x_1,...,x_n=y such that (x_i,x_{i+1})\in E for all 1\leq i\leq n.

A tree is thus a connected graph such that paths between points are unique (note this definition of a tree is different from that of posets: where elements have a well-ordered set of predecessors).  And so on and so on….

In fact,  recall Abramenko and Brown used this algebraic approach in the construction of Coxeter complexes, although it was slightly more complicated since they were dealing with graphs whose vertices were cosets of the maximal standard subgroups of a Coxeter group G.  Lengths of paths between vertices in the sense I have described coincide with lengths of minimal galleries between chambers containing those vertices.  Also, be not confused that in that construction of Coxeter complexes, there was another implicit notion of a (di)graph where any simplex was a vertex, and a directed edge connected two simplices if one was the face of another.