Path homomorphisms #
Introduction #
In this section, we define a path homomorphism between two quivers \( \quiver{Q} \), \( \quiver{R} \). Path homomorphisms are the natural candidate for a notion of a "continuous map" between two quivers, although we will not concentrate on defining notions of continuity or topology just yet.
Maps between paths #
First, consider a map \( \function{ \gamma } \) sending paths in a quiver \( \quiver{Q} \) to paths in a quiver \( \quiver{R} \). We can see such a map as being between the path groupoids of \( \quiver{Q} \) and \( \quiver{R} \):
\[ \functionSignature{\function{ \gamma }}{\pathGroupoid{\quiver{Q}}}{\pathGroupoid{\quiver{R}}} \]A path homomorphism is such a map that also possesses the property of compatibility:
\[ \function{ \gamma }(\pathCompose{\path{P_1}}{\path{P_2}}) = \pathCompose{\function{ \gamma }(\path{P_1})}{\function{ \gamma }(\path{P_2})} \]This states that we can compose paths in \( \quiver{Q} \) and then apply \( \function{ \gamma } \), or we can apply \( \function{ \gamma } \) and then compose the resulting paths in \( \quiver{R} \), and we will obtain the same result. This is in fact equivalent to the statement that \( \function{ \gamma } \) is a groupoid homomorphism.
Properties #
Before seeing any examples, we can deduce some simple properties of a path homomorphism. Firstly, let us consider a path \( \path{P} \), and the empty path starting at its tail vertex, written \( \pathTail{\path{P}} \), and head vertex, written \( \pathHead{\path{P}} \):
\[ \begin{aligned} \path{P}&= \paren{\pathWord{\vert{x}}{\wordSymbol{W}}{\vert{y}}}\\ \pathTail{\path{P}}&= \paren{\pathWord{\vert{x}}{\emptyWord{}}{\vert{x}}}\\ \pathHead{\path{P}}&= \paren{\pathWord{\vert{y}}{\emptyWord{}}{\vert{y}}}\end{aligned} \]By definition, we have that \( \pathTail{\path{P}} \) and \( \pathHead{\path{P}} \) are the left and right units of \( \path{P} \) under path composition:
\[ \pathCompose{\pathTail{\path{P}}}{\path{P}} = \path{P} = \pathCompose{\path{P}}{\pathHead{\path{P}}} \]Applying a path homomorphism \( \function{ \gamma } \) to these equations, and using compatibility, we obtain:
\[ \begin{aligned} \function{ \gamma }(\pathCompose{\pathTail{\path{P}}}{\path{P}})&= \function{ \gamma }(\path{P})= \function{ \gamma }(\pathCompose{\path{P}}{\pathHead{\path{P}}})\\ \pathCompose{\function{ \gamma }(\pathTail{\path{P}})}{\function{ \gamma }(\path{P})}&= \function{ \gamma }(\path{P})= \pathCompose{\function{ \gamma }(\path{P})}{\function{ \gamma }(\pathHead{\path{P}})}\end{aligned} \]Therefore we have that \( \function{ \gamma }(\pathTail{\path{P}}) \) and \( \function{ \gamma }(\pathHead{\path{P}}) \) act like the left and right units for \( \function{ \gamma }(\path{P}) \). Since the only units are the empty paths, we can conclude that \( \graphHomomorphism{ \gamma } \) maps empty paths to empty paths, and we can write:
\[ \begin{aligned} \function{ \gamma }(\pathTail{\path{P}})&= \pathTail{\function{ \gamma }(\path{P})}\\ \function{ \gamma }(\pathHead{\path{P}})&= \pathHead{\function{ \gamma }(\path{P})}\end{aligned} \]We can leverage this fact to understand how \( \graphHomomorphism{ \gamma } \) interacts with path reversal (the inverse of the path groupoid), since \( \pathCompose{\path{P}}{\pathReverse{\path{P}}} = \pathTail{\path{P}} \).
\[ \begin{aligned} \pathCompose{\path{P}}{\pathReverse{\path{P}}}&= \pathTail{\path{P}}\\ \function{ \gamma }(\pathCompose{\path{P}}{\pathReverse{\path{P}}})&= \function{ \gamma }(\pathTail{\path{P}})\\ \pathCompose{\function{ \gamma }(\path{P})}{\function{ \gamma }(\pathReverse{\path{P}})}&= \pathTail{\function{ \gamma }(\path{P})}\end{aligned} \]Therefore \( \function{ \gamma }(\pathReverse{\path{P}}) \) behaves as the inverse of \( \function{ \gamma }(\path{P}) \), since it right-multiplies with it to produce the unit \( \pathTail{\function{ \gamma }(\path{P})} \). Therefore we can conclude that \( \function{ \gamma } \) preserves path reversal:
\[ \function{ \gamma }(\pathReverse{\path{P}}) = \pathReverse{\function{ \gamma }(\path{P})} \]Summary #
We can summarize the properties of a path homomorphism (strictly speaking the first property is merely the definition):
\[ \begin{aligned} \function{ \gamma }(\pathCompose{\path{P_1}}{\path{P_2}})&= \pathCompose{\function{ \gamma }(\path{P_1})}{\function{ \gamma }(\path{P_2})}&\quad \maTeFo{preserves composition}\\ \function{ \gamma }(\pathTail{\path{P}})&= \pathTail{\function{ \gamma }(\path{P})}&\quad \maTeFo{preserves left units}\\ \function{ \gamma }(\pathHead{\path{P}})&= \pathHead{\function{ \gamma }(\path{P})}&\quad \maTeFo{preserves right units}\\ \function{ \gamma }(\pathReverse{\path{P}})&= \pathReverse{\function{ \gamma }(\path{P})}&\quad \maTeFo{preserves reversal}\end{aligned} \]Examples #
To keep things simple, we'll start out by considering the special case take \( \quiver{R} = \quiver{Q} \), in other words, we will consider maps that sends path in \( \quiver{Q} \) to paths in \( \quiver{Q} \). We'll take \( \quiver{Q} \) to be the 2-line quiver \( \bindCards{\subSize{\lineQuiver }{2}}{\card{c}} \):
Non-example #
Imagine we try to define a path homomorphism \( \functionSignature{\function{ \gamma }}{\pathGroupoid{\quiver{Q}}}{\pathGroupoid{\quiver{R}}} \), where we initially define its behavior on two particular paths \( \orFo{\path{P_1}},\piFo{\path{P_2}} \) in \( \quiver{Q} \):
There is no path homomorphism that behaves like this, because while we can form the composition \( \pathCompose{\orFo{\path{P_1}}}{\piFo{\path{P_2}}} = \teFo{\path{P_3}} \), we cannot compose their images under \( \function{ \gamma } \): \( \pathCompose{\function{ \gamma }(\orFo{\path{P_1}})}{\function{ \gamma }(\piFo{\path{P_2}})} = \nullElement \), as the head of \( \function{ \gamma }(\orFo{\path{P_1}}) \) is not equal to the tail of \( \function{ \gamma }(\piFo{\path{P_2}}) \).
Example #
Now let us consider the map \( \functionSignature{\pathHomomorphism{ \rho }}{\pathGroupoid{\quiver{Q}}}{\pathGroupoid{\quiver{R}}} \), illustrated below for paths \( \orFo{\path{P_1}},\piFo{\path{P_2}},\teFo{\path{P_3}} \) as well as the empty paths \( \textcolor{#217f00}{\groupoidIdentityElement{1}{\vert{x}}} = \parenPathWord{\vert{x}}{\emptyWord{}}{\vert{x}},\textcolor{#165e9d}{\groupoidIdentityElement{1}{\vert{y}}} = \parenPathWord{\vert{y}}{\emptyWord{}}{\vert{y}},\textcolor{#b50700}{\groupoidIdentityElement{1}{\vert{z}}} = \parenPathWord{\vert{z}}{\emptyWord{}}{\vert{z}} \).
This map does satisfy compatibility, making it a path homomorphism. Intuitively, \( \graphHomomorphism{ \gamma } \) "reflects paths in the left-right axis" of the line quiver.
Path tables #
We can also visualize the behavior of above map as a path table showing the pairing of \( \path{P} \) and \( \function{ \gamma }(\path{P}) \) for several paths \( \elemOf{\path{P}}{\pathList(\quiver{Q})} \):
To avoid having to illustrate \( \graphHomomorphism{ \gamma } \) on every possible path, we can exploit the fact that \( \graphHomomorphism{ \gamma } \) must preserve path reversal. The (undepicted) value of \( \function{ \gamma }(\pathWord{\vert{z}}{\word{\ncard{c}}{\ncard{c}}}{\vert{x}}) \) is implied by the (depicted) value \( \function{ \gamma }(\pathWord{\vert{x}}{\word{\card{c}}{\card{c}}}{\vert{z}}) \):
\[ \begin{aligned} \function{ \gamma }(\pathReverse{\path{P}})&= \pathReverse{\function{ \gamma }(\path{P})}\\ \function{ \gamma }(\pathWord{\vert{z}}{\word{\ncard{c}}{\ncard{c}}}{\vert{x}})&= \pathReverse{\paren{\function{ \gamma }(\pathWord{\vert{x}}{\word{\card{c}}{\card{c}}}{\vert{z}})}}\\ &= \pathReverse{\paren{\pathWord{\vert{z}}{\word{\ncard{c}}{\ncard{c}}}{\vert{x}}}}\\ &= \pathWord{\vert{x}}{\word{\card{c}}{\card{c}}}{\vert{z}}\end{aligned} \]This symmetry implies the remaining paths:
Since these pairs are implied, we need not show these mappings in path tables.
Example: zero homomorphisms #
Here we provide another example of a homomorphism, a zero homomorphism that sends every path to an empty path:
There are three such possible zero homomorphisms, because we can choose to send paths to the empty path on any of the three vertices in \( \quiver{Q} \).
Example: partial zero homomorphisms #
We can also construct path homomorphisms that "zero" some paths but not all paths. For example, we can zero the portion of any path that is "left" of the central vertex, \( \vert{y} \):
Example: maps between two different quivers #
So far, we've considered path represents from a single quiver to itself. Now let's consider a path homomorphism \( \functionSignature{\function{ \gamma }}{\pathGroupoid{\quiver{Q}}}{\pathGroupoid{\quiver{R}}} \) between a line quiver \( \quiver{Q} = \bindCards{\subSize{\lineQuiver }{2}}{\reFo{\card{r}}} \), and a different quiver \( \quiver{R} \) on cardinals \( \grFo{\card{g}},\blFo{\card{b}} \):
Here we show the path table for \( \function{ \gamma } \):
Images of edges #
Let us consider the full path table for the homomorphism we just defined:
This path table is obviously highly redundant, since many of the rows are implied by others:
-
Rows 7, 8, and 9 are implied by 4, 5, and 6 via path reversal: \( \function{ \gamma }(\pathReverse{\path{P}}) = \pathReverse{\function{ \gamma }(\path{P})} \).
-
Rows 1, 2, and 3, which describe where to send empty paths on vertices \( \vert{x},\vert{y},\vert{z} \), can be extracted from the heads (or tails) of the images of any paths that start (or end) at these vertices, e.g. rows 4 and 5.
-
Row 6 depicts the image of path \( \paren{\pathWord{\vert{x}}{\word{\reFo{\card{r}}}{\reFo{\card{r}}}}{\vert{z}}} \), but this path can be represented as the composition \( \pathCompose{\paren{\pathWord{\vert{x}}{\word{\reFo{\card{r}}}}{\vert{y}}}}{\paren{\pathWord{\vert{y}}{\word{\reFo{\card{r}}}}{\vert{z}}}} \), and hence is determined by rows 4 and 5 (and compatibility).
All in all, only rows 4 and 5 are necessary to fully describe the behavior of \( \function{ \gamma } \):
But these are just the images of the edges of \( \quiver{Q} \)!
Summary #
We can see that the behavior of a path homomorphism \( \functionSignature{\function{ \gamma }}{\pathGroupoid{\quiver{Q}}}{\pathGroupoid{\quiver{R}}} \) is uniquely determined by a choice of path \( \elemOf{\function{ \gamma }(\pathWord{\vert{x}}{\word{\card{c}}}{\vert{y}})}{\pathList(\quiver{Q})} \) for every edge \( \elemOf{\tde{\vert{x}}{\vert{y}}{\card{c}}}{\edgeList(\quiver{Q})} \). The behavior of \( \function{ \gamma } \) on longer paths in \( \quiver{Q} \) is then determined by composing the images of the sequence of edges in the path:
\[ \function{ \gamma }(\pathWord{\vert{x}}{\word{\card{c_1}}{\card{c_2}}{\card{\elSy}}{\card{c_{\sym{n}}}}}{\vert{z}}) = \pathCompose{\function{ \gamma }(\pathWord{\vert{x}}{\word{\card{c_1}}}{\blSy})}{\function{ \gamma }(\pathWord{\blSy}{\word{\card{c_2}}}{\blSy})}{\elSy}{\function{ \gamma }(\pathWord{\blSy}{\word{\card{c_{\sym{n}}}}}{\vert{z}})} \]The only requirement we must impose on these choices for individual edges is that the images of the edges can be composed in \( \quiver{R} \) when two edges are head-to-tail in \( \quiver{Q} \):
\[ \pathCompose{\function{ \gamma }(\pathWord{\vert{x}}{\word{\card{c}}}{\vert{y}})}{\function{ \gamma }(\pathWord{\vert{y}}{\word{\card{d}}}{\vert{z}})} \neq \nullElement \]Lengthening and shortening #
To get a further feeling for what kind of homomorphisms are possible, consider the following two graphs \( \quiver{Q} = \bindCards{\subSize{\lineQuiver }{3}}{\reFo{\card{r}}} \) and \( \path{R} = \bindCards{\subSize{\lineQuiver }{4}}{\reFo{\card{r}}} \):
Lengthening #
Our path homomorphism \( \functionSignature{\function{ \gamma }}{\pathGroupoid{\quiver{Q}}}{\pathGroupoid{\quiver{R}}} \) is defined by the following path table:
Our homomorphism \( \function{ \gamma } \) does a "jump" when traversing the middle edge in \( \quiver{Q} \). We say it is a path lengthening, because there is at least one path whose image under \( \function{ \gamma } \) is longer than the path:
\[ \existsForm{\path{P}}{\length(\pathHomomorphism{ \gamma }(\path{P}))>\length(\path{P})} \]This is equivalent to there being at least one edge that is sent to a path longer than 1:
\[ \existsForm{\elemOf{\edge{e}}{\edgeList(\quiver{Q})}}{\length(\pathHomomorphism{ \gamma }(\edge{e}))>1} \]We say a path homomorphism \( \function{ \gamma } \) is \( \sym{k} \)-Lipschitz if the lengths of images of edges under \( \function{ \gamma } \) are bounded above by \( \sym{k} \):
\[ \forAllForm{\elemOf{\edge{e}}{\edgeList(\quiver{Q})}}{\length(\pathHomomorphism{ \gamma }(\edge{e})) \le \sym{k}} \]Shortening #
Let us now consider a path homomorphism \( \functionSignature{\function{ \gamma }}{\pathGroupoid{\quiver{R}}}{\pathGroupoid{\quiver{Q}}} \) with the opposite feature:
Our homomorphism \( \pathHomomorphism{ \rho } \) now "shortens" a particular edge, namely \( \paren{\pathWord{\vert{w}}{\word{\reFo{\card{r}}}}{\vert{x}}} \), sending it to \( \pathHomomorphism{ \rho }(\pathWord{\vert{w}}{\word{\reFo{\card{r}}}}{\vert{x}}) = \paren{\pathWord{\vert{b}}{\emptyWord{}}{\vert{b}}} \). Any longer paths that pass through this edge will similarly be shortened.
We say \( \pathHomomorphism{ \rho } \) is a path shortening, because there is at least one path whose image under \( \function{ \gamma } \) is shorter than the path:
\[ \existsForm{\path{P}}{\length(\pathHomomorphism{ \gamma }(\path{P}))<\length(\path{P})} \]This is equivalent to there being at least one edge that is sent to the empty path:
\[ \existsForm{\elemOf{\edge{e}}{\edgeList(\quiver{Q})}}{\length(\pathHomomorphism{ \gamma }(\edge{e})) = 0} \]Composition #
We can of course compose these path homomorphisms, in either order.
First, let's examine \( \functionSignature{\function{\paren{\functionComposition{\pathHomomorphism{ \rho }\functionCompositionSymbol \pathHomomorphism{ \gamma }}}}}{\quiver{Q}}{\quiver{Q}} \), which is \( \functionSignature{\pathHomomorphism{ \rho }}{\quiver{R}}{\quiver{Q}} \) applied to the result of \( \functionSignature{\pathHomomorphism{ \gamma }}{\quiver{Q}}{\quiver{R}} \).
This is the identity path homomorphism on \( \quiver{Q} \).
Now let's examine \( \functionSignature{\function{\paren{\functionComposition{\pathHomomorphism{ \gamma }\functionCompositionSymbol \pathHomomorphism{ \rho }}}}}{\quiver{R}}{\quiver{R}} \), which is \( \functionSignature{\pathHomomorphism{ \gamma }}{\quiver{Q}}{\quiver{R}} \) applied to the result of \( \functionSignature{\pathHomomorphism{ \rho }}{\quiver{R}}{\quiver{Q}} \):
This is certainly not the identity path homomorphism, and is both a shortening and a lengthening.
Length preserving #
We say a path homomorphism \( \function{ \gamma } \) is length preserving if it is neither a shortening or a lengthening. This is equivalent to saying that the length of the image of every edge edge is exactly 1:
\[ \forAllForm{\elemOf{\edge{e}}{\edgeList(\quiver{Q})}}{\length(\pathHomomorphism{ \gamma }(\edge{e})) = 1} \]A length preserving homomorphism \( \functionSignature{\function{ \gamma }}{\pathGroupoid{\quiver{Q}}}{\pathGroupoid{\quiver{R}}} \) map edges of \( \quiver{Q} \) to oriented edges of \( \quiver{R} \): a directed edge of \( \quiver{Q} \) can be sent to a directed edge of \( \quiver{R} \), but in a sense opposite to its ordinary orientation. The "horizontal reflection" homomorphism on \( \bindCards{\subSize{\lineQuiver }{2}}{\reFo{\card{r}}} \) we considered previously was of such a type.
Path homomorphisms into the line quiver #
For any quiver \( \quiver{Q} \) there is a particular family of path homomorphisms that is particularly easy to characterize: the path homomorphisms onto the line quiver \( \subSize{\lineQuiver }{ \infty } \).
To construct these, let us first define an integer vertex field to be a function \( \functionSignature{\function{f}}{\vertexList(\quiver{Q})}{\mathbb{Z}} \) that assigns to each vertex of \( \quiver{Q} \) an integer.
Below we show an example integer vertex field on the quiver \( \quiver{Q} = \subSize{\squareQuiver }{2} \), where the values of \( \function{f} \) are displayed beside each vertex:
We will now interpret the value \( \function{f}(\vert{v}) \) as determining a vertex of the line quiver \( \bindCards{\subSize{\lineQuiver }{ \infty }}{\grFo{\card{g}}} \):
Therefore, \( \function{f} \) induces part of the behavior of a path homomorphism \( \pathHomomorphism{ \rho } \), specifically, the behavior of the empty paths of \( \quiver{Q} \):
\[ \pathHomomorphism{ \rho }(\pathWord{\vert{v}}{\emptyWord{}}{\vert{v}})\defEqualSymbol \pathWord{\function{f}(\vert{v})}{\emptyWord{}}{\function{f}(\vert{v})} \]We now need only define \( \pathHomomorphism{ \rho } \) on the edges of \( \quiver{Q} \). To do this, we note that for any edge \( \elemOf{\tde{\vert{u}}{\vert{v}}{\card{c}}}{\edgeList(\quiver{Q})} \), we are forced by compatibility to send the corresponding path \( \paren{\pathWord{\vert{u}}{\word{\card{c}}}{\vert{v}}} \) to some path in \( \subSize{\lineQuiver }{ \infty } \) with tail vertex \( \function{f}(\vert{u}) \) and head vertex \( \function{f}(\vert{v}) \). However, there is only one path in \( \subSize{\lineQuiver }{ \infty } \)between any two given vertices, and hence we have no choice in defining the remaining behavior of \( \pathHomomorphism{ \rho } \).
The formal definition of \( \pathHomomorphism{ \rho } \) then is as follows:
\[ \pathHomomorphism{ \rho }(\pathWord{\vert{u}}{\word{\card{c}}}{\vert{v}})\defEqualSymbol \parenPathWord{\function{f}(\vert{u})}{\repeatedPower{\word{\grFo{\card{g}}}}{\function{f}(\vert{v}) - \function{f}(\vert{u})}}{\function{f}(\vert{v})} \]We show part of the path table to make the idea clear:
Notice how the image of each edge under \( \pathHomomorphism{ \rho } \) encodes the value of \( \function{f} \) at the head and tail of the edge, and the cardinal content of the path encodes the difference between these values.
The converse direction is trivially true: any path homomorphism into the line quiver gives us an integer vertex field, by simply numbering the vertices of the line quiver and taking pre-images of empty paths.
Therefore, we have that there is a bijection between integer vertex fields and path homomorphisms into the line quiver.
Connected quivers #
We have just seen that a function \( \functionSignature{\function{f}}{\vertexList(\quiver{Q})}{\vertexList(\subSize{\lineQuiver }{ \infty })} \) induces a unique path homomorphism \( \functionSignature{\pathHomomorphism{ \rho }}{\quiver{Q}}{\subSize{\lineQuiver }{ \infty }} \), defining \( \pathHomomorphism{ \rho }(\de{\vert{u}}{\vert{v}}) \) to be the unique path in \( \subSize{\lineQuiver }{ \infty } \) between vertices \( \function{f}(\vert{u}) \) and \( \function{f}(\vert{v}) \).
We can quite easily generalize this construction, replacing the \( \subSize{\lineQuiver }{ \infty } \) with an arbitrary connected quiver \( \quiver{R} \). However, for a given function \( \functionSignature{\function{f}}{\vertexList(\quiver{Q})}{\vertexList(\quiver{R})} \) there may be more than one path between \( \function{f}(\vert{u}) \) and \( \function{f}(\vert{v}) \); we may in fact pick any path in \( \pathList(\path{R},\function{f}(\vert{u}),\function{f}(\vert{v})) \) to define the behavior of the path homomorphism on an edge \( \pathHomomorphism{ \rho }(\de{\vert{u}}{\vert{v}}) \). Hence, we no longer have a bijection -- typically there will be an infinite number of homomorphisms corresponding to a choice of function \( \function{f} \).
Endomorphisms and automorphisms #
Endomorphisms #
A special role is played by the set of path homomorphisms \( \functionSignature{\pathHomomorphism{ \alpha }}{\pathGroupoid{\quiver{Q}}}{\pathGroupoid{\quiver{Q}}} \) from a quiver \( \quiver{Q} \) to itself. We'll write this set as \( \endomorphisms(\quiver{Q}) \). We will now attach the structure of a semigroup to this set. That is to say, we will define an associative binary operation that corresponds to the composition of homomorphisms.
Like all function compositions, path homomorphism composition is associative. But is the composition of two homomorphisms \( \functionComposition{\pathHomomorphism{ \alpha }\functionCompositionSymbol \pathHomomorphism{ \beta }} \) itself a homomorphism? This is easily seen to be true:
\[ \begin{aligned} \function{\paren{\functionComposition{\pathHomomorphism{ \alpha }\functionCompositionSymbol \pathHomomorphism{ \beta }}}}(\pathCompose{\path{P_1}}{\path{P_2}})&= \pathHomomorphism{ \alpha }(\pathHomomorphism{ \beta }(\pathCompose{\path{P_1}}{\path{P_2}}))\\ &= \pathHomomorphism{ \alpha }(\pathCompose{\pathHomomorphism{ \beta }(\path{P_1})}{\pathHomomorphism{ \beta }(\path{P_2})})\\ &= \pathCompose{\pathHomomorphism{ \alpha }(\pathHomomorphism{ \beta }(\path{P_1}))}{\pathHomomorphism{ \alpha }(\pathHomomorphism{ \beta }(\path{P_2}))}\\ &= \pathCompose{\function{\paren{\functionComposition{\pathHomomorphism{ \alpha }\functionCompositionSymbol \pathHomomorphism{ \beta }}}}(\path{P_1})}{\function{\paren{\functionComposition{\pathHomomorphism{ \alpha }\functionCompositionSymbol \pathHomomorphism{ \beta }}}}(\path{P_2})}\end{aligned} \]Therefore, the set \( \endomorphisms(\quiver{Q}) \) is a semigroup. It would further be a group if path homomorphisms were invertible, but we have seen examples of path homomorphisms that, for example, send all paths to the empty path on a particular vertex.
Automorphisms #
So how can we constrain path homomorphisms to be invertible? It will turn out to be enough to ask that they are merely surjective, so that every possible path is the image of at least one other path:
\[ \forAllForm{\path{P}}{\existsForm{\quiver{R}}{\pathHomomorphism{ \alpha }(\quiver{R}) = \path{P}}} \]Why does surjectivity imply injectivity? We prove this by contradiction. Assume that a surjective path homomorphism \( \pathHomomorphism{ \alpha } \) is not injective, so that:
\[ \existsForm{\path{P},\path{\primed{P}},\path{P} \neq \path{\primed{P}}}{\pathHomomorphism{ \alpha }(\path{P}) = \pathHomomorphism{ \alpha }(\path{\primed{P}})} \]If we decompose \( \path{P} \) and \( \primed{\path{P}} \) into sequences of individual 1-paths, we must obtain at least one pair \( \paren{\pathWord{\vert{u}}{\word{\card{c}}}{\vert{v}}},\paren{\pathWord{\vert{u}}{\word{\card{\primed{c}}}}{\primed{\vert{v}}}} \) such that \( \pathHomomorphism{ \alpha }(\pathWord{\vert{u}}{\word{\card{c}}}{\vert{v}}) = \pathHomomorphism{ \alpha }(\pathWord{\vert{u}}{\word{\card{\primed{c}}}}{\primed{\vert{v}}}) \) but \( \vert{v} \neq \primed{\vert{v}} \).
Affine path homomorphisms #
You may have noticed that the discussion of path homomorphisms of quivers has not relied in any way on the cardinal structure of the quivers. In fact, everything we have said is applicable also to ordinary directed graphs and their path groupoids.
Word automorphisms #
Recall that word group \( \wordGroup{\quiver{Q}} \) is the free group on the cardinals of \( \quiver{Q} \).
We now consider a group homomorphism \( \functionSignature{\groupHomomorphism{ \phi }}{\wordGroupSymbol }{\wordGroupSymbol } \), or automorphism as such homomorphisms are called. We can think of such a homomorphism \( \groupHomomorphism{ \phi } \) as a way of "rewriting" words as other words, cardinal-by-cardinal.
Let's consider an example homomorphism on a quiver with cardinals \( \cardinalList(\quiver{Q}) = \list{\reFo{\card{r}},\grFo{\card{g}},\blFo{\card{b}}} \). We define \( \groupHomomorphism{ \phi } \) as:
\[ \groupHomomorphism{ \phi } = \groupWordRewriting{\rewritingRule{\word{\reFo{\card{r}}}}{\word{\grFo{\card{g}}}{\reFo{\card{r}}}},\rewritingRule{\word{\grFo{\card{g}}}}{\word{1}},\rewritingRule{\word{\blFo{\card{b}}}}{\word{\reFo{\ncard{r}}}}} \]The empty word has no letters to rewrite, so it remains the empty word:
\[ \pathHomomorphism{ \phi }(\card{1}) = \card{1} \]The words with one cardinal are rewritten as given in the definition of \( \groupHomomorphism{ \phi } \). Because \( \groupHomomorphism{ \phi } \) is a group homomorphism, it must replace the inverses of these cardinals with the inverses of the corresponding right-hand-sides:
\[ \begin{csarray}{rclrcl}{accicc} \pathHomomorphism{ \phi }(\reFo{\card{r}}) & = & \word{\grFo{\card{g}}}{\reFo{\card{r}}} & \pathHomomorphism{ \phi }(\reFo{\inverted{\card{r}}}) & = & \word{\reFo{\ncard{r}}}{\grFo{\ncard{g}}}\\ \pathHomomorphism{ \phi }(\grFo{\card{g}}) & = & \card{1} & \pathHomomorphism{ \phi }(\grFo{\inverted{\card{g}}}) & = & \card{1}\\ \pathHomomorphism{ \phi }(\blFo{\card{b}}) & = & \reFo{\inverted{\card{r}}} & \pathHomomorphism{ \phi }(\blFo{\inverted{\card{b}}}) & = & \reFo{\card{r}} \end{csarray} \]Longer words are rewritten left-to-right, since this is how a group homomorphism to \( \wordGroupSymbol \) must work. Here we show a few examples of rewriting of longer words:
\[ \begin{array}{rclcl} \pathHomomorphism{ \phi }(\word{\reFo{\card{r}}}{\reFo{\card{r}}}) & = & \pathHomomorphism{ \phi }(\reFo{\card{r}})\iGmult \pathHomomorphism{ \phi }(\reFo{\card{r}}) & = & \word{\grFo{\card{g}}}{\reFo{\card{r}}}{\grFo{\card{g}}}{\reFo{\card{r}}}\\ \pathHomomorphism{ \phi }(\word{\reFo{\ncard{r}}}{\reFo{\ncard{r}}}) & = & \pathHomomorphism{ \phi }(\reFo{\inverted{\card{r}}})\iGmult \pathHomomorphism{ \phi }(\reFo{\inverted{\card{r}}}) & = & \word{\reFo{\ncard{r}}}{\grFo{\ncard{g}}}{\reFo{\ncard{r}}}{\grFo{\ncard{g}}}\\ \pathHomomorphism{ \phi }(\word{\grFo{\card{g}}}{\grFo{\card{g}}}) & = & \pathHomomorphism{ \phi }(\grFo{\card{g}})\iGmult \pathHomomorphism{ \phi }(\grFo{\card{g}}) = \concat{\card{1}\,\card{1}} & = & \card{1}\\ \pathHomomorphism{ \phi }(\word{\blFo{\card{b}}}{\blFo{\card{b}}}) & = & \pathHomomorphism{ \phi }(\blFo{\card{b}})\iGmult \pathHomomorphism{ \phi }(\blFo{\card{b}}) & = & \word{\reFo{\ncard{r}}}{\reFo{\ncard{r}}}\\ \pathHomomorphism{ \phi }(\word{\reFo{\card{r}}}{\blFo{\card{b}}}) & = & \pathHomomorphism{ \phi }(\reFo{\card{r}})\iGmult \pathHomomorphism{ \phi }(\blFo{\card{b}}) = \concat{\word{\grFo{\card{g}}}{\reFo{\card{r}}}\,\reFo{\inverted{\card{r}}}} & = & \grFo{\card{g}}\\ \pathHomomorphism{ \phi }(\word{\reFo{\card{r}}}{\grFo{\card{g}}}{\blFo{\card{b}}}) & = & \pathHomomorphism{ \phi }(\reFo{\card{r}})\iGmult \pathHomomorphism{ \phi }(\grFo{\card{g}})\iGmult \pathHomomorphism{ \phi }(\blFo{\card{b}}) = \concat{\word{\grFo{\card{g}}}{\reFo{\card{r}}}\,\card{1}\,\reFo{\inverted{\card{r}}}} & = & \grFo{\card{g}}\\ \pathHomomorphism{ \phi }(\word{\reFo{\card{r}}}{\grFo{\card{g}}}{\blFo{\ncard{b}}}) & = & \pathHomomorphism{ \phi }(\reFo{\card{r}})\iGmult \pathHomomorphism{ \phi }(\grFo{\card{g}})\iGmult \pathHomomorphism{ \phi }(\blFo{\inverted{\card{b}}}) = \concat{\word{\grFo{\card{g}}}{\reFo{\card{r}}}\,\card{1}\,\reFo{\card{r}}} & = & \word{\grFo{\card{g}}}{\reFo{\card{r}}}{\reFo{\card{r}}} \end{array} \]Repeating the story of the composition of path homomorphisms, we can now form the endomorphism semigroup \( \endomorphisms(\wordGroupSymbol ) \) of word homomorphisms.
Automorphism group #
If we want the group \( \automorphisms(\wordGroupSymbol ) \) rather than the semigroup \( \endomorphisms(\wordGroupSymbol ) \), we need to limit ourselves to invertible word homomorphisms.
As a first step to characterizing these, observe that any signed permutation of the set of cardinals gives an invertible homomorphism. Signed permutations are permutations that can additionally invert each element. Since the number of permutations of \( \sym{n} \) elements is \( \factorial{\sym{n}} \), and the number of inverse patterns is \( \power{2}{\sym{n}} \), there are \( \factorial{\sym{n}} \, \power{2}{\sym{n}} \) signed permutations.
For example, the 8 possible signed permutations on \( \list{\reFo{\card{r}},\blFo{\card{b}}} \) are \( \list{\TuFo{\reFo{\card{r}}, \blFo{\card{b}}},\TuFo{\inverted{\reFo{\card{r}}}, \blFo{\card{b}}},\TuFo{\reFo{\card{r}}, \inverted{\blFo{\card{b}}}},\TuFo{\inverted{\reFo{\card{r}}}, \inverted{\blFo{\card{b}}}},\TuFo{\blFo{\card{b}}, \reFo{\card{r}}},\TuFo{\inverted{\blFo{\card{b}}}, \reFo{\card{r}}},\TuFo{\blFo{\card{b}}, \inverted{\reFo{\card{r}}}},\TuFo{\inverted{\blFo{\card{b}}}, \inverted{\reFo{\card{r}}}}} \), yielding the following word automorphisms:
\[ \begin{nsarray}{c} \groupWordRewriting{\rewritingRule{\reFo{\card{r}}}{\reFo{\card{r}}},\rewritingRule{\blFo{\card{b}}}{\blFo{\card{b}}}}\\ \groupWordRewriting{\rewritingRule{\reFo{\card{r}}}{\reFo{\inverted{\card{r}}}},\rewritingRule{\blFo{\card{b}}}{\blFo{\card{b}}}}\\ \groupWordRewriting{\rewritingRule{\reFo{\card{r}}}{\reFo{\card{r}}},\rewritingRule{\blFo{\card{b}}}{\blFo{\inverted{\card{b}}}}}\\ \groupWordRewriting{\rewritingRule{\reFo{\card{r}}}{\reFo{\inverted{\card{r}}}},\rewritingRule{\blFo{\card{b}}}{\blFo{\inverted{\card{b}}}}}\\ \groupWordRewriting{\rewritingRule{\reFo{\card{r}}}{\blFo{\card{b}}},\rewritingRule{\blFo{\card{b}}}{\reFo{\card{r}}}}\\ \groupWordRewriting{\rewritingRule{\reFo{\card{r}}}{\blFo{\inverted{\card{b}}}},\rewritingRule{\blFo{\card{b}}}{\reFo{\card{r}}}}\\ \groupWordRewriting{\rewritingRule{\reFo{\card{r}}}{\blFo{\card{b}}},\rewritingRule{\blFo{\card{b}}}{\reFo{\inverted{\card{r}}}}}\\ \groupWordRewriting{\rewritingRule{\reFo{\card{r}}}{\blFo{\inverted{\card{b}}}},\rewritingRule{\blFo{\card{b}}}{\reFo{\inverted{\card{r}}}}} \end{nsarray} \]Moving to the set \( \list{\reFo{\card{r}},\grFo{\card{g}},\blFo{\card{b}}} \) yields 48 signed permutations: \( \TuFo{\reFo{\card{r}}, \grFo{\card{g}}, \blFo{\card{b}}},\TuFo{\inverted{\reFo{\card{r}}}, \grFo{\card{g}}, \blFo{\card{b}}},\TuFo{\reFo{\card{r}}, \inverted{\grFo{\card{g}}}, \blFo{\card{b}}},\TuFo{\reFo{\card{r}}, \grFo{\card{g}}, \inverted{\blFo{\card{b}}}} \), \( \elSy \), \( \TuFo{\inverted{\blFo{\card{b}}}, \inverted{\grFo{\card{g}}}, \reFo{\card{r}}},\TuFo{\inverted{\blFo{\card{b}}}, \grFo{\card{g}}, \inverted{\reFo{\card{r}}}},\TuFo{\blFo{\card{b}}, \inverted{\grFo{\card{g}}}, \inverted{\reFo{\card{r}}}},\TuFo{\inverted{\blFo{\card{b}}}, \inverted{\grFo{\card{g}}}, \inverted{\reFo{\card{r}}}} \), yielding 48 word automorphisms:
\[ \begin{array}{c} \groupWordRewriting{\rewritingRule{\reFo{\card{r}}}{\reFo{\card{r}}},\rewritingRule{\grFo{\card{g}}}{\grFo{\card{g}}},\rewritingRule{\blFo{\card{b}}}{\blFo{\card{b}}}}\\ \groupWordRewriting{\rewritingRule{\reFo{\card{r}}}{\reFo{\inverted{\card{r}}}},\rewritingRule{\grFo{\card{g}}}{\grFo{\card{g}}},\rewritingRule{\blFo{\card{b}}}{\blFo{\card{b}}}}\\ \groupWordRewriting{\rewritingRule{\reFo{\card{r}}}{\reFo{\card{r}}},\rewritingRule{\grFo{\card{g}}}{\grFo{\inverted{\card{g}}}},\rewritingRule{\blFo{\card{b}}}{\blFo{\card{b}}}}\\ \groupWordRewriting{\rewritingRule{\reFo{\card{r}}}{\reFo{\card{r}}},\rewritingRule{\grFo{\card{g}}}{\grFo{\card{g}}},\rewritingRule{\blFo{\card{b}}}{\blFo{\inverted{\card{b}}}}}\\ \veElSy\\ \groupWordRewriting{\rewritingRule{\reFo{\card{r}}}{\blFo{\inverted{\card{b}}}},\rewritingRule{\grFo{\card{g}}}{\grFo{\inverted{\card{g}}}},\rewritingRule{\blFo{\card{b}}}{\reFo{\card{r}}}}\\ \groupWordRewriting{\rewritingRule{\reFo{\card{r}}}{\blFo{\inverted{\card{b}}}},\rewritingRule{\grFo{\card{g}}}{\grFo{\card{g}}},\rewritingRule{\blFo{\card{b}}}{\reFo{\inverted{\card{r}}}}}\\ \groupWordRewriting{\rewritingRule{\reFo{\card{r}}}{\blFo{\card{b}}},\rewritingRule{\grFo{\card{g}}}{\grFo{\inverted{\card{g}}}},\rewritingRule{\blFo{\card{b}}}{\reFo{\inverted{\card{r}}}}}\\ \groupWordRewriting{\rewritingRule{\reFo{\card{r}}}{\blFo{\inverted{\card{b}}}},\rewritingRule{\grFo{\card{g}}}{\grFo{\inverted{\card{g}}}},\rewritingRule{\blFo{\card{b}}}{\reFo{\inverted{\card{r}}}}} \end{array} \]Being obviously invertible, the signed permutations on \( \sym{n} \) cardinals form a group. This group is known as the Coxeter group \( \group{B_{\sym{n}}} \).
Lengthening automorphisms #
This exhausts the word automorphisms that do not lengthen words. But it is not immediately obvious that they can lengthen word while still remaining invertible. Here we demonstrate one particular example and explain why it is invertible:
\[ \pathHomomorphism{ \phi } = \groupWordRewriting{\rewritingRule{\word{\reFo{\card{r}}}}{\word{\reFo{\card{r}}}{\grFo{\ncard{g}}}},\rewritingRule{\word{\grFo{\card{g}}}}{\word{\grFo{\card{g}}}{\blFo{\ncard{b}}}},\rewritingRule{\word{\blFo{\card{b}}}}{\word{\blFo{\card{b}}}}} \]To show invertibility, we need to explicitly construct words (of any length) that map to the single-cardinal words \( \list{\reFo{\card{r}},\grFo{\card{g}},\blFo{\card{b}}} \). Inverses of longer words can then be formed by composing these primitive inverses. To find these primitive inverses, we observe that:
\[ \begin{array}{rcccccl} \reFo{\card{r}} & = & \concat{\word{\reFo{\card{r}}}{\grFo{\ncard{g}}}\,\word{\grFo{\card{g}}}{\blFo{\ncard{b}}}\,\blFo{\card{b}}} & = & \concat{\pathHomomorphism{ \phi }(\reFo{\card{r}})\,\pathHomomorphism{ \phi }(\grFo{\card{g}})\,\pathHomomorphism{ \phi }(\blFo{\card{b}})} & = & \pathHomomorphism{ \phi }(\word{\reFo{\card{r}}}{\grFo{\card{g}}}{\blFo{\card{b}}})\\ \grFo{\card{g}} & = & \concat{\word{\grFo{\card{g}}}{\blFo{\ncard{b}}}\,\blFo{\card{b}}} & = & \concat{\pathHomomorphism{ \phi }(\grFo{\card{g}})\,\pathHomomorphism{ \phi }(\blFo{\card{b}})} & = & \pathHomomorphism{ \phi }(\word{\grFo{\card{g}}}{\blFo{\card{b}}})\\ \blFo{\card{b}} & = & & & & = & \pathHomomorphism{ \phi }(\blFo{\card{b}}) \end{array} \]Hence we have that \( \inverse{\groupHomomorphism{ \phi }} = \groupWordRewriting{\rewritingRule{\word{\reFo{\card{r}}}}{\word{\reFo{\card{r}}}{\grFo{\card{g}}}{\blFo{\card{b}}}},\rewritingRule{\word{\grFo{\card{g}}}}{\word{\grFo{\card{g}}}{\blFo{\card{b}}}},\rewritingRule{\word{\blFo{\card{b}}}}{\word{\blFo{\card{b}}}}} \).
More generally, characterizing the group structure of the automorphism group of the free group is tricky, with the most famous result being a presentation in terms of so-called Nielsen transformations, which we will not go into here.
Abelian word group #
If we temporarily imagine the word group to be Abelian, in other words, if \( \word{\reFo{\card{r}}}{\grFo{\card{g}}} = \word{\grFo{\card{g}}}{\reFo{\card{r}}},\word{\grFo{\card{g}}}{\blFo{\card{b}}} = \word{\blFo{\card{b}}}{\grFo{\card{g}}} \), etc., things become much easier. In this setting, we can represent a word homomorphism \( \groupHomomorphism{ \phi } \) on \( \sym{n} \) cardinals as an \( \sym{n}\times \sym{n} \) integral matrix \( \matrix{M_{\groupHomomorphism{ \phi }}} \) by choosing an ordering of the cardinals to serve as the basis . Here we depict four examples:
\[ \begin{csarray}{cccc}{aama} \pathHomomorphism{ \phi } & \matrix{M_{\pathHomomorphism{ \phi }}} & \pathHomomorphism{ \phi } & \matrix{M_{\pathHomomorphism{ \phi }}}\\ & & & \\ \begin{nsarray}{l} \langle \kern{2pt}\rewritingRule{\word{\reFo{\card{r}}}}{\word{\reFo{\card{r}}}},\\ \phantom{ \langle \kern{2pt}}\rewritingRule{\word{\grFo{\card{g}}}}{\word{\grFo{\card{g}}}},\\ \phantom{ \langle \kern{2pt}}\rewritingRule{\word{\blFo{\card{b}}}}{\word{\blFo{\card{b}}}}\kern{2pt} \rangle \end{nsarray} & {\begin{pmatrix}1&0&0\\0&1&0\\0&0&1\end{pmatrix}} & \begin{nsarray}{l} \langle \kern{2pt}\rewritingRule{\word{\reFo{\card{r}}}}{\word{\reFo{\card{r}}}{\grFo{\card{g}}}{\blFo{\card{b}}}},\\ \phantom{ \langle \kern{2pt}}\rewritingRule{\word{\grFo{\card{g}}}}{\word{\grFo{\card{g}}}{\blFo{\card{b}}}},\\ \phantom{ \langle \kern{2pt}}\rewritingRule{\word{\blFo{\card{b}}}}{\word{\blFo{\card{b}}}}\kern{2pt} \rangle \end{nsarray} & {\begin{pmatrix}1&1&1\\0&1&1\\0&0&1\end{pmatrix}}\\ & & & \\ \begin{nsarray}{l} \langle \kern{2pt}\rewritingRule{\word{\reFo{\card{r}}}}{\word{\card{1}}},\\ \phantom{ \langle \kern{2pt}}\rewritingRule{\word{\grFo{\card{g}}}}{\word{\grFo{\card{g}}}},\\ \phantom{ \langle \kern{2pt}}\rewritingRule{\word{\blFo{\card{b}}}}{\word{\blFo{\card{b}}}}\kern{2pt} \rangle \end{nsarray} & {\begin{pmatrix}0&0&0\\0&1&0\\0&0&1\end{pmatrix}} & \begin{nsarray}{l} \langle \kern{2pt}\rewritingRule{\word{\reFo{\card{r}}}}{\word{\reFo{\ncard{r}}}},\\ \phantom{ \langle \kern{2pt}}\rewritingRule{\word{\grFo{\card{g}}}}{\word{\blFo{\card{b}}}},\\ \phantom{ \langle \kern{2pt}}\rewritingRule{\word{\blFo{\card{b}}}}{\word{\grFo{\card{g}}}}\kern{2pt} \rangle \end{nsarray} & {\begin{pmatrix}-1&0&0\\0&0&1\\0&1&0\end{pmatrix}} \end{csarray} \]Finding the inverse homomorphism is equivalent to inverting its integral matrix:
\[ \matrix{M_{\inverse{\pathHomomorphism{ \phi }}}} = \inverse{\matrix{M_{\pathHomomorphism{ \phi }}}} \]Even better, it is easily checked that an integral matrix is only invertible if its determinant is \( \pm 1 \), allowing us to characterize the automorphism group of Abelian word homomorphisms as the integral orthogonal group \( \orthogonalGroup{\sym{n}}{\ring{\mathbb{Z}}} \).
Visualization #
We can visualize the action of various word homomorphisms on some familiar transitive quivers to gain intuition for their behavior.