# Visual Group Theory's Intuitive Proof - Cayley's Theorem - Nathan Carter pp. 85, Theorem 5.1

Theorem 5.1. Cayley's Theorem: Every group is isomorphic to a collection of permutations.

Figure 5.31. A multiplication table for the group $V_4$, with nodes numbered 1 through 4 to facilitate analyzing how the arrows permute the elements. The permutation for each arrow color is shown on the right. Figure 5.32. A multiplication table made up of the permutations created in Figure 5.31. Each cell highlights the destination to which the permutation sends 1, using the corresponding color from Figure 5.31, emphasizing what the colors of the arrows already showed: The two tables contain the same pattern.

This proof can be summarized as two steps: Create a permutation for each column in a group’s multiplication table, and then inspect how those permutations treat the group’s identity element. Figure 5.32 illustrates these two steps. It shows a multiplication table comprised of the permutations from Figure 5.31, and each cell of the table highlights the result of applying the permutation to the identity element 1. The correspondence between Figures 5.31 and 5.32 is clear: If I remove all but the highlighted elements from Figure 5.32, all that remains is the multiplication table from Figure 5.31.

This proof is more casual but I want to understand this before Fraleigh. The aim is to prove a multiplication table made out of the permutations of any group behaves the same as the mutliplication table of any group. viz. $p_i \cdot p_j = p_k \iff i \cdot j = k.$ For some reason, I understand figures 5.31 and 5.32 but I'm still unconvinced.

(1.) I think I understand the first three paragraphs. I'm confounded by the last two. Why does the proof only "consider how the permutations treat the identity element from the original group"? What about the other elements mapped by the permutations?

(2.) The proof says applying to $p_k$ to $1$ means multiplying $1$ by $k$. Is this because the permutation for column $k$ maps $1$ to $k$? I can see this is true for $V_4$ in Figure 5.32. $V_4$ was defined to have this property. However, how's it true in general? We don't know what the permutation $p_k$ is?

(3.) Same question as (2.) for $p_i \cdot p_j$.

(4.) I don't fully know why I'm unsettled hence what other things am I missing?

I think the main issue is your point (2). Applying $p_k$ to $1$ does give the same result as multiplying $1$ by $k$ in the original group (note 'multiplying' here refers to the group operation). But this isn't an incidental fact about the group you happen to use, this is necessarily true from the way the permutation $p_k$ is constructed from the group's multiplication table. You form $p_k$ by reading down column $k$ of the table, so by definition it sends 1 to whatever number is in row 1 of column $k$. But this is just another way of saying $1\cdot k$.

The proof then shows that applying $p_i\cdot p_j$ to 1 gives $(i\cdot j)$ by the same token -- $p_i$ by definition sends $1$ to $j$ and $p_j$ by definition sends $i$ to $(i\cdot j)$. So $p_i\cdot p_j$ sends $1$ to $i\cdot j$, but we already know $p_i\cdot p_j$ is equal to $p_k$ so they must both send $1$ to the same thing, ie., $i\cdot j$ must in fact be $k$, which is what was required. We look at the effects on $1$ rather than any other element just because it's easier.

This seems to me to be glossing over the question of whether the permutations can be put into a closed multiplication table at all, ie, why does multiplying $p_i$ by $p_j$ as permutations necessarily give a permutation corresponding to another column of the multiplication table at all, but there you go.

I wondered the exact same thing when I read through that part of Visual Group Theory as well. Here's what I came up with after reading aPaulT's answer.

First let's just look at the multiplication table from the book and extend it with the indexes from the proof. We don't really need e.g. that $2\ast3=4$, we only need the column and row that is multiplied with the identity element, so the following argument works for any multiplication table.

$\begin{array}{c|cccccccccccc} \ast & 1 & 2 & 3 & 4 & \dots & j & \dots & k & \dots & i & \dots & n\\ \hline 1 & 1 & 2 & 3 & 4 & & j & & k & & i & & n\\ 2 & 2 & 1 & 4 & 3\\ 3 & 3 & 4 & 1 & 2\\ 4 & 4 & 3 & 2 & 1\\ \vdots & & & & & \ddots\\ j & j & & & & & 1\\ \vdots & & & & & & & \ddots\\ k & k & & & & & & & 1\\ \vdots & & & & & & & & & \ddots\\ i & i & & & & & i\ast j & & & & 1\\ \vdots & & & & & & & & & & & \ddots\\ n & n & & & & & & & & & & & 1 \end{array}$

If we create permutations $p_1,p_2,\dots,p_n$ for the above multiplication table, we can rewrite the table as:

$\begin{array}{c|cccccccccccc} & p_{1} & p_{2} & p_{3} & p_{4} & \dots & p_{j} & \dots & p_{k} & \dots & p_{i} & \dots & p_{n}\\ \\ \ast & 1 & 2 & 3 & 4 & \dots & j & \dots & k & \dots & i & \dots & n\\ \hline 1 & p_{1}(1) & p_{2}(1) & p_{3}(1) & p_{4}(1) & \dots & p_{j}(1) & & p_{k}(1) & & p_{i}(1) & & p_{n}(1)\\ 2 & p_{1}(2) & p_{2}(2) & p_{3}(2) & p_{4}(2) & \dots & p_{j}(2) & & p_{k}(2) & & p_{i}(2) & & p_{n}(2)\\ 3 & p_{1}(3) & p_{2}(3) & p_{3}(3) & p_{4}(3) & \dots\\ 4 & p_{1}(4) & p_{2}(4) & p_{3}(4) & p_{4}(4) & \dots\\ \vdots & \vdots & \vdots & \vdots & \vdots & \ddots\\ j & p_{1}(j) & p_{2}(j) & & & & p_{j}(j)\\ \vdots & & & & & & & \ddots\\ k & p_{1}(k) & p_{2}(k) & & & & & & p_{k}(k)\\ \vdots & & & & & & & & & \ddots\\ i & p_{1}(i) & p_{2}(i) & & & & p_{j}(i) & & & & p_{i}(i)\\ \vdots & & & & & & & & & & & \ddots\\ n & p_{1}(n) & p_{2}(n) & & & & & & & & & & p_{n}(n) \end{array}$

Notice that $p_j(i)$ is in the same spot as $i\ast j$; $p_j(i)$ has to map to $i\ast j$ because we are making the permutations be this way. Notice also that $p_k(1)$ is in the same place as $k$, it is indeed we who are defining $p_k(1)$ to be equal to $k$.

Let's look at a table for the permutations, the operation is now composition:

$\begin{array}{c|cccccccccccc} & p_{1} & p_{2} & p_{3} & p_{4} & \dots & p_{j} & \dots & p_{k} & \dots & p_{i} & \dots & p_{n}\\ \hline p_{1} & p_{1} & p_{2} & p_{3} & p_{4} & \dots & p_{j} & & p_{k} & & p_{i} & & p_{n}\\ p_{2} & p_{2} & p_{1} & p_{2}p_{3} & p_{2}p_{4} & \dots & p_{2}p_{j} & & p_{2}p_{k} & & p_{2}p_{i} & & p_{2}p_{n}\\ p_{3} & p_{3} & p_{3}p_{2} & p_{1} & p_{3}p_{4} & \dots\\ p_{4} & p_{4} & p_{4}p_{2} & p_{4}p_{3} & p_{1} & \dots\\ \vdots & \vdots & \vdots & \vdots & \vdots & \ddots\\ p_{j} & p_{j} & p_{j}p_{2}\\ \vdots & & & & & & & \ddots\\ p_{k} & p_{k} & p_{k}p_{2}\\ \vdots & & & & & & & & & \ddots\\ p_{i} & p_{i} & p_{i}p_{2} & & & & p_{i}p_{j}\\ \vdots & & & & & & & & & & & \ddots\\ p_{n} & p_{n} & p_{n}p_{2} & & & & & & & & & & p_{1} \end{array}$

Now we just assume that $p_ip_j=p_k$. If it is true that $p_ip_j=p_k$, it must be so that $i\ast j=k$, because $p_ip_j(1)=p_k(1)\Longleftrightarrow i\ast j=k$.

Because we assumed that $p_ip_j=p_k$, this works for any element, i.e. $p_ip_j(m)=p_k(m)$. One element that $m$ can be is identity element 1, and then we have that $p_ip_j(1)=p_k(1)$, which gives us $i\ast j=k$

If $p_ip_j(1)=p_k(1)\Rightarrow i\ast j=k$, and then somehow at the same time for $r\neq 1$, $p_ip_j(r)=p_k(r)\Rightarrow i\ast j\neq k$, then what element lies in the box in the $i$th row and the $j$th column of the multiplication table?

• I can't understand why we only check how the permutations treat the identity elements ... Commented Aug 3, 2015 at 10:27