Essays/Cayley's Theorem
< Essays
Jump to navigation
Jump to search
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
- 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.