Please Login to access more options.

Problem 8 (Automorphisms Of A Directed Square)

Consider the directed graph $\mathcal{G} = (V,A)$ shown below with vertex set $V = \{1,2,3,4\}$ and arrows (directed edges) $$A = \{(1,2),(2,3),(3,4),(4,1)\}.$$

  1. How would you define an automorphism of a directed graph?
  2. List all the automorphisms of this directed graph. You should have 4.
  3. Is there is an automorphism $a\in \aut(\mathcal{G})$ such that $a^2=a\circ a$ (the composition) is the identity automorphism, but $a$ is not the identity?
  4. Is there is an $a\in \aut(\mathcal{G})$ such that $a^3=a\circ a\circ a$ is the identity but $a$ is not the identity?
  5. Is there is an $a\in \aut(\mathcal{G})$ such that every other $b\in \aut(\mathcal{G})$ is of the form $b=a^n$ for some $n$?
  6. For every $a,b\in \aut(\mathcal{G})$, do we have $a\circ b = b\circ a$?

Solution

1. An automorphism of a directed graph $\mathcal{G}=(V,A)$ is a function $\sigma:V\to V$ such that $(v_1,v_2)\in A$ if and only if $(\sigma(v_1), \sigma(v_2))\in A$.

2. The automorphisms of the digraph $\mathcal{G}$ are $$ \begin{align} \sigma_0 &= \begin{bmatrix}1 & 2 & 3 & 4 \\ 1 & 2 & 3 & 4 \end{bmatrix}, \\ \sigma_1 &= \begin{bmatrix}1 & 2 & 3 & 4 \\ 2 & 3 & 4 & 1 \end{bmatrix}, \\ \sigma_2 &= \begin{bmatrix}1 & 2 & 3 & 4 \\ 3 & 4 & 1 & 2 \end{bmatrix}, \;\text{and} \\ \sigma_3 &= \begin{bmatrix}1 & 2 & 3 & 4 \\ 4 & 1 & 2 & 3 \end{bmatrix} , \end{align} $$ where the automorphisms $\sigma_i$ for $i \in \{ 0, 1, 2, 3 \}$ correspond to $i$ repeated $90^{\circ}$ counter clockwise rotations of $\mathcal{G}$. Note that $\sigma_0$ equal the identity on $V$.

3. Yes, there is in fact an automorphism $a \in Aut( \mathcal{G} )$ such that $a^2 = a \circ a = \sigma_0$, but $a$ is not the identity. By inspection we see that the automorphism $\sigma_2$ is such an automorphism. To show this is true we simply compute $\sigma_2( \sigma_2( v ) ) = v$ for each $v \in V$. For $v=1$, we have $\sigma_2( \sigma_2( 1 ) ) = \sigma_2( 3 ) = 1$. The reader can check the remaining 3. This shows $\sigma_{2}^2$ is the identity automorphism.

4. No, there is not an $a \in Aut( \mathcal{G} )$ such that $a^3 = a \circ a \circ a = \sigma_0$ where $a \neq \sigma_0$. This can be shown via "brute force" by taking all of the $a \in Aut( \mathcal{G} )$ and composing them three times with themselves.

5. Yes there is an $a \in Aut( \mathcal{G} )$ such that every other $b \in Aut( \mathcal{G} )$ is of the form $b = a^n$ for some $n \in \{ 2, 3, 4 \}$. This can be shown using the automorphism $\sigma_1$. Since $\sigma_1$ corresponds to a $90^{\circ}$ ccw rotation automorphism it stands to reason that $2, 3, $ or $4$ ninety degree rotations will correspond in turn to each of the other automorphisms.

6. Yes it can be shown that for every $a, b \in Aut( \mathcal{G} )$ we have $a \circ b = b \circ a$. Every possible automorphism can be shown via a symmetric Cayley table, as seen below, where each row $i$ corresponds to $\sigma_i$ and each column $j$ corresponds to $\sigma_j$, and each entry in the table corresponds to $\sigma_i \circ \sigma_j $.

$$\begin{array}{c|cccc} \circ & \sigma_0 & \sigma_1 & \sigma_2 & \sigma_3 \\\hline \sigma_0 & \sigma_0 & \sigma_1 & \sigma_2 & \sigma_3 \\ \sigma_1 & \sigma_1 & \sigma_2 & \sigma_3 & \sigma_0 \\ \sigma_2 & \sigma_2 & \sigma_3 & \sigma_0 & \sigma_1 \\ \sigma_3 & \sigma_3 & \sigma_0 & \sigma_1 & \sigma_2 \\ \end{array}$$

Tags
  • When you are ready to submit this written work for grading, add the phrase [[!Submit]] to your page. This will tell me that you have completed the page (it's past rough draft form, and you believe it is in final draft form). Don't type [[!Submit]] on a rough draft.
  • If I put [[!NeedsWork]] on your page, then your job is to review what I've written, address any comments made, and then delete all the comments I made. When you have finished reviewing your work, leave [[!NeedsWork]] on your page and type [[!Submit]]. (Both tags will show up). This tells me you have addressed the comments.
  • I'll mark your work with [[!Complete]] after you have made appropriate revisions.