6.1: Group Actions

Last updated
Save as PDF

Page ID: 700

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

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

$ \newcommand{\dsum}{\displaystyle\sum\limits} $

$ \newcommand{\dint}{\displaystyle\int\limits} $

$ \newcommand{\dlim}{\displaystyle\lim\limits} $

$ \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{\longvect}{\overrightarrow}$

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

$\newcommand{\ket}[1]{\left| #1 \right>}$
$\newcommand{\bra}[1]{\left< #1 \right|}$
$\newcommand{\braket}[2]{\left< #1 \vphantom{#2} \right| \left. #2 \vphantom{#1} \right>}$
$\newcommand{\braopket}[3]{\left< #1 \vphantom{#2}\vphantom{#3} \right| #2 \vphantom{#1}\vphantom{#3} \left| #3 \vphantom{#1}\vphantom{#2} \right>}$
$\newcommand{\qmvec}[1]{\mathbf{\vec{#1}}}$
$\newcommand{\op}[1]{\hat{\mathbf{#1}}}$
$\newcommand{\expect}[1]{\langle #1 \rangle}$
$\newcommand{\dfn}[1]{\emph{\textbf{#1}}}$

$\newcommand{\avec}{\mathbf a}$ $\newcommand{\bvec}{\mathbf b}$ $\newcommand{\cvec}{\mathbf c}$ $\newcommand{\dvec}{\mathbf d}$ $\newcommand{\dtil}{\widetilde{\mathbf d}}$ $\newcommand{\evec}{\mathbf e}$ $\newcommand{\fvec}{\mathbf f}$ $\newcommand{\nvec}{\mathbf n}$ $\newcommand{\pvec}{\mathbf p}$ $\newcommand{\qvec}{\mathbf q}$ $\newcommand{\svec}{\mathbf s}$ $\newcommand{\tvec}{\mathbf t}$ $\newcommand{\uvec}{\mathbf u}$ $\newcommand{\vvec}{\mathbf v}$ $\newcommand{\wvec}{\mathbf w}$ $\newcommand{\xvec}{\mathbf x}$ $\newcommand{\yvec}{\mathbf y}$ $\newcommand{\zvec}{\mathbf z}$ $\newcommand{\rvec}{\mathbf r}$ $\newcommand{\mvec}{\mathbf m}$ $\newcommand{\zerovec}{\mathbf 0}$ $\newcommand{\onevec}{\mathbf 1}$ $\newcommand{\real}{\mathbb R}$ $\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}$ $\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}$ $\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}$ $\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}$ $\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}$ $\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}$ $\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}$ $\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}$ $\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}$ $\newcommand{\laspan}[1]{\text{Span}\{#1\}}$ $\newcommand{\bcal}{\cal B}$ $\newcommand{\ccal}{\cal C}$ $\newcommand{\scal}{\cal S}$ $\newcommand{\wcal}{\cal W}$ $\newcommand{\ecal}{\cal E}$ $\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}$ $\newcommand{\gray}[1]{\color{gray}{#1}}$ $\newcommand{\lgray}[1]{\color{lightgray}{#1}}$ $\newcommand{\rank}{\operatorname{rank}}$ $\newcommand{\row}{\text{Row}}$ $\newcommand{\col}{\text{Col}}$ $\renewcommand{\row}{\text{Row}}$ $\newcommand{\nul}{\text{Nul}}$ $\newcommand{\var}{\text{Var}}$ $\newcommand{\corr}{\text{corr}}$ $\newcommand{\len}[1]{\left|#1\right|}$ $\newcommand{\bbar}{\overline{\bvec}}$ $\newcommand{\bhat}{\widehat{\bvec}}$ $\newcommand{\bperp}{\bvec^\perp}$ $\newcommand{\xhat}{\widehat{\xvec}}$ $\newcommand{\vhat}{\widehat{\vvec}}$ $\newcommand{\uhat}{\widehat{\uvec}}$ $\newcommand{\what}{\widehat{\wvec}}$ $\newcommand{\Sighat}{\widehat{\Sigma}}$ $\newcommand{\lt}{<}$ $\newcommand{\gt}{>}$ $\newcommand{\amp}{&}$ $\definecolor{fillinmathshade}{gray}{0.9}$

Group actions bring us back to our original view of groups as measures of symmetry. We begin with a definition.

Definition 6.0.1

Let $G$ be a group. A set $S$ is a (left) $G$-set if there is a function from $G\times S\rightarrow S$ (which we will write as $g\cdot s$ for $g\in G, s\in S$) satisfying:

Let $G$ be a group. A set $S$ is a (left) $G$-set if there is a function from $G\times S\rightarrow S$ (which we will write as $g\cdot s$ for $g\in G, s\in S$) satisfying:
1. $(gh)\cdot s = g\cdot (h\cdot s)$ for all $g, h\in G, s\in S$, and
2. $1\cdot s=s$ for all $s\in S$.

An analogous definition can be written for a right $G$-set; a right $G$-set has a function from $S\times G\rightarrow S$.

These conditions say, in plain language, that elements of $G$ move objects in the set to other objects, in a way which respects the group operation. (ie, it doesn't matter whether you perform the operation before or after applying the action.) Furthermore, the identity fixes every element of the set.

It's best to start with some easy combinatorial examples.

On the other hand, $S_{13}$ acts on the values of the cards while leaving the suits alone. For convenience, we write the action on values of cards on the right and the action on suits on the left. Let $\tau$ be the permutation in $S_{13}$ which sends $i$ to $i+1$, and $13$ to $1$. Then $4D\cdot \tau=5D$. Combining the left and right actions, we have $\sigma\cdot 4D\cdot \tau=5H$, for example.
And $S_n$ can act on sets with fewer than $n$ elements. Consider a coin, with a 'heads' side ($H$) and a 'tails' side ($T$). We can define an action of $S_n$ where $\sigma$ flips the coin if the sign of $\sigma$ is negative, and leaves the coin alone if the sign of $\sigma$ is positive. Here the set we're acting on is actually the set of states of the coin: $\{H, T\}$.

Just as we made Cayley graphs of groups, we can also make Cayley graphs of group actions. If our group $G$ has a generating set $\{g_1, g_2, \ldots, g_k\}$, then the Cayley graph has one vertex for each element of the set $S$ and colored edges from each $s$ to $g_i\cdot s$.

For the example of $S_n$ acting on a coin, the Cayley graph will just have two vertices, $H$ and $T$, and arrows according to the action of the generators. If we consider the generating set of simple transpositions (which, we'll recall, exchange $i$ and $i+1$ and leave everything else alone), the Cayley graph will have arrows from $H$ to $T$ and back for each simple transposition. (Because all simple transpositions have sign $-1$.)

$s4coinAction.gif$

Figure 6.1: Cayley graph for action of $S_4$ on a coin, with generators given by the simple transpositions.

$S_n$ has another generating set consisting of the transposition $[2,1,3,4,\ldots,n]$ and the rotation $[n,1,2,\ldots,n-1]$. Draw the Cayley graph of $S_n$ acting on the coin with these generators. (Note that the Cayley graph may be different for different $n$.)

Let's build a Cayley graph for the cards, but with a smaller set of cards to make things easier to draw. Imagine our deck only has two suits - Spades and Diamonds - and only numbers $1$ through $4$. Then let $S_4$ act on the left by permuting numbers. The Cayley graph is below.

$s4CardAction.gif$

Figure 6.2: Cayley diagram for $S_4$ acting on some cards numbered $1$ through $4$, whose suits are all either diamonds (D) or spades (S).

Notice that the action is broken up into two different connected pieces: Exchanging numbers will never allow us to change suits, but we can switch around numbers freely. As a result, the suits each form a 'block' from which the other blocks can't be reached. These blocks are called orbits; we'll study them intensively in the next section.

Contributors and Attributions

Tom Denton (Fields Institute/York University in Toronto)

Search

Text Color

Text Size

Margin Size

Font Type

\(S_n\) has another generating set consisting of the transposition \([2,1,3,4,\ldots,n]\) and the rotation \([n,1,2,\ldots,n-1]\). Draw the Cayley graph of \(S_n\) acting on the coin with these generators. (Note that the Cayley graph may be different for different \(n\).)