Saltar al contenido principal
LibreTexts Español

3.2: Visualización de Grupos- Cayley Graph

  • Page ID
    111083
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

    \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

    \( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)

    ( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)

    \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)

    \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)

    \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)

    \( \newcommand{\Span}{\mathrm{span}}\)

    \( \newcommand{\id}{\mathrm{id}}\)

    \( \newcommand{\Span}{\mathrm{span}}\)

    \( \newcommand{\kernel}{\mathrm{null}\,}\)

    \( \newcommand{\range}{\mathrm{range}\,}\)

    \( \newcommand{\RealPart}{\mathrm{Re}}\)

    \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)

    \( \newcommand{\Argument}{\mathrm{Arg}}\)

    \( \newcommand{\norm}[1]{\| #1 \|}\)

    \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)

    \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    \( \newcommand{\vectorA}[1]{\vec{#1}}      % arrow\)

    \( \newcommand{\vectorAt}[1]{\vec{\text{#1}}}      % arrow\)

    \( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

    \( \newcommand{\vectorC}[1]{\textbf{#1}} \)

    \( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)

    \( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)

    \( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)

    \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

    \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

    Hasta ahora, hemos visto tres tipos diferentes de grupos: Grupos de simetrías (incluyendo el grupo diedro de simetrías de un polígono), los enteros módulo\(n\), and the permutation group, \(S_n\). We've seen Cayley graphs for the dihedral group; let's see some Cayley graphs for some others.

    Enteros Modulo\(n\)

    El módulo de enteros\(n\) only require a single generator to obtain the entire group. \(1\) is a nice choice of generator, as we know that every number \(k\) in \(\{0,1,2,\ldots n\}\) can be written as \(k\cdot 1\), which is to say, the sum of \(1\) with itself \(k\) times. The Cayley graph for this situation is simple: it's just \(n\) vertices, arranged in a loop with an arrow pointing from each number to the next. This creates a cycle! When \(n=8\), the cycle is this: \[0\rightarrow 1\rightarrow 2\rightarrow 3\rightarrow 4\rightarrow 5\rightarrow 6\rightarrow 7\rightarrow 0\]. Any group which is generated by a single element (including the usual integers!) is called a cyclic group. (This is yet another interpretation of \(\mathbb{Z}_n\)!)

    Podemos elegir otros números que\(1\) as the generator, though! Take \(n=8\), and consider the number \(3\). We can make our Cayley graph by drawing a vertex for each number in \(\{0,1,2,\ldots,8\}\) and an arrow from each \(x\) to \(x+3\). Then the cycle draws out as: [0\rightarrow 3\rightarrow 6\rightarrow 1\rightarrow 4\rightarrow 7\rightarrow 2\rightarrow 5\rightarrow 0].

    Aquí hay un gráfico de Cayley para\(\mathbb{Z}_7\) shown with three generators. Any one of the three generators would work just fine. The red vertex is the identity, \(0\). The green arrows are for the generator \(1\), blue for the generator \(2\), and green for the generator \(3\). What would happen if we included the generators \(4, 5,\) or \(6\)?

    z7cayley-3gens.jpg

    Figura 3.1: Gráfica de Cayley para\(\mathbb{Z}_7\) with three different generators. The identity is marked as the red dot.

    Not every number is a generator of \(\mathbb{Z}_n\). For example, in \(\mathbb{Z}_8\), if we choose \(4\), the cycle is just: \( 0\rightarrow 4\rightarrow 0\). Since the cycle doesn't contain every element of the group, we see that \(4\) doesn't generate the group on its own.

    Exercise 3.1.0

    Suppose \(k\in \mathbb{Z}_n\). Show that \(k\) generates \(\mathbb{Z}_n\) if and only if \(k\) is relatively prime to \(n\). (ie, the only common divisor of \(k\) and \(n\) is \(1\).)

    Exercise 3.1.1

    Suppose \(k\in \mathbb{Z}_n\) and \(k\) is not relatively prime to \(n\). Is it possible to find another umber \(m\) not relatively prime to \(n\) such that \(k\) and \(m\) together generate \(\mathbb{Z}_n\)? Try some examples! Explain why or why not

    Permutation Groups

    The permutation group \(S_n\) has a number of interesting generating sets. We'll show a few of these generating sets for \(n=3\) and \(n=4\) for easy comparison.

    The first generating set is a minimal set, using just two generators. The first generator is the 'rotation' with list notation \(r=[n,1,2,3,4,\ldots, n-1]\). The second is a flip, exchanging only the first two things, \(f=[2,1,3,4,\ldots,n]\).

    To check that these actually generate \(S_n\), we need to see that we can construct an arbitrary permutation using just these generators. So consider an arbitrary permutation \(\sigma\), written in list notation. If there are two adjacent entries that are out of order (big to the left of the small), we can apply rotations until the two things sit in the first two entries (suppose we use \(k\) rotations to do this). Then we apply the flip. And then we 'unrotate' \(k\) times to put the now-sorted numbers back. Then we find two more adjacent numbers and repeat. Once there are no adjacent numbers out of order, then we must be at the identity! Then the reverse of the sequence of moves we just made builds the permutation we wanted. Since the permutation was arbitrary, our two moves must generate the group.

    s4cayley.png

    Figura 3.2: Un gráfico de Cayley para\(S_4\), generated by the rotation \([4,1,2,3]\) (in red) and reflection \([2,1,3,4]) (cyan).

    Un segundo conjunto de generadores viene dado por el conjunto de todas las transposiciones. Estas son todas las permutaciones que tienen dos cosas cambiadas y todo lo demás en orden. Por ejemplo,\([4,2,3,1]\) and \([1,2,6,4,5,3]\) are transpositions. Modifying the above argument, you can see that the set of all transpositions are a generating set. There are more than 2 transpositions, so this isn't a minimal generating set. But it is an interesting set of generators when studying the permutation group more closely.

    Ejercicio 3.1.2

    ¿Cuántas transposiciones hay en\(S_n\)?

     

    Sin embargo, un tercer conjunto de generadores viene dado por las simples transposiciones. Este es el conjunto de transposiciones\(\{s_i\}\) that just exchange \(i\) and \(i+1\) while leaving everything else alone. There are \(n-1\) simple transpositions. This is a very important set of generators in the further study of permutations! But it shows up in one simple context, as well.

    s4Diagram.gif

    Figura 3.1.3: Gráfica de Cayley para

    Template:ContribDenton


    This page titled 3.2: Visualización de Grupos- Cayley Graph is shared under a not declared license and was authored, remixed, and/or curated by Tom Denton.