Essays/Cayley's Theorem

Let G be a group table of a finite group of order n . relabel G relabels the group elements according to their index in the first row of the table, and the columns of the result are distinct permutations of i.n .

relabel=: ({. i. ]) @ (<"_2)

   ] G=: 7| */~ 1+i.6
1 2 3 4 5 6
2 4 6 1 3 5
3 6 2 5 1 4
4 1 5 2 6 3
5 3 1 6 4 2
6 5 4 3 2 1
   relabel G
0 1 2 3 4 5
1 3 5 0 2 4
2 5 1 4 0 3
3 0 4 1 5 2
4 2 0 5 3 1
5 4 3 2 1 0
   relabel {"1/~ |: relabel G
0 1 2 3 4 5
1 3 5 0 2 4
2 5 1 4 0 3
3 0 4 1 5 2
4 2 0 5 3 1
5 4 3 2 1 0

  (relabel G) -: relabel {"1/~ |: relabel G
1

The last equivalence is true in general, and says that every finite group of G of order n is isomorphic to a subgroup of the permutation group of degree n . This is Cayley's Theorem, named in honor of the English mathematician who first proved it in 1878.

Another illustration, on the group of non-singular 2 2 boolean matrices under boolean matrix multiplication.

   ] M=: (0 ~: -/ .*"2 M) # M=: 2 2 $"1 #: i.16
0 1
1 0

0 1
1 1

1 0
0 1

1 0
1 1

1 1
0 1

1 1
1 0
   G=: ~:/ .*."2/~ M
   $G
6 6 2 2
   relabel G
0 1 2 3 4 5
5 3 4 1 2 0
2 4 0 5 1 3
4 2 5 0 3 1
3 5 1 4 0 2
1 0 3 2 5 4
   relabel {"1/~ |: relabel G
0 1 2 3 4 5
5 3 4 1 2 0
2 4 0 5 1 3
4 2 5 0 3 1
3 5 1 4 0 2
1 0 3 2 5 4

  (relabel G) -: relabel {"1/~ |: relabel G
1

---

See also

• MathWorld

• Permutations
• Inverse Permutation
• Permutation Index
• Self-Upgrading Permutations
• Self-Downgrading Permutations
• Symmetric Array
• Symmetries of the Square
• Cayley's Theorem
• N Queens Problem

---

Contributed by Roger Hui.