﻿ A History of APL in 50 Functions

<<   >>

 12. Cayley’s Theorem r←,⍳⊢ ⋄ (r G) ≡ r ∘.{⍺[⍵]}⍨ ↓r G The finite case of Cayley’s theorem [49a]: every group G is isomorphic to a subgroup of the group of permutations. For example: ``` ⎕←T←2 2∘⍴¨(4⍴2)∘⊤¨9 6 7 11 13 14 ┌───┬───┬───┬───┬───┬───┐ │1 0│0 1│0 1│1 0│1 1│1 1│ │0 1│1 0│1 1│1 1│0 1│1 0│ └───┴───┴───┴───┴───┴───┘ ⎕←G←∘.(≠.∧)⍨T ┌───┬───┬───┬───┬───┬───┐ │1 0│0 1│0 1│1 0│1 1│1 1│ │0 1│1 0│1 1│1 1│0 1│1 0│ ├───┼───┼───┼───┼───┼───┤ │0 1│1 0│1 1│1 1│0 1│1 0│ │1 0│0 1│0 1│1 0│1 1│1 1│ ├───┼───┼───┼───┼───┼───┤ │0 1│1 0│1 1│1 1│0 1│1 0│ │1 1│1 1│1 0│0 1│1 0│0 1│ ├───┼───┼───┼───┼───┼───┤ │1 0│0 1│0 1│1 0│1 1│1 1│ │1 1│1 1│1 0│0 1│1 0│0 1│ ├───┼───┼───┼───┼───┼───┤ │1 1│1 1│1 0│0 1│1 0│0 1│ │0 1│1 0│1 1│1 1│0 1│1 0│ ├───┼───┼───┼───┼───┼───┤ │1 1│1 1│1 0│0 1│1 0│0 1│ │1 0│0 1│0 1│1 0│1 1│1 1│ └───┴───┴───┴───┴───┴───┘ ``` T are the non-singular 2-by-2 boolean matrices, and G is its group table under boolean matrix multiplication. The function r←,⍳⊢ relabels a group table according to its index in its ravel (cf. x⍳x); such relabelling, like displaying in a different font, does not affect group-theoretic properties. ``` r ← , ⍳ ⊢ r G 0 1 2 3 4 5 1 0 4 5 2 3 2 3 5 4 1 0 3 2 1 0 5 4 4 5 3 2 0 1 5 4 0 1 3 2 ``` The rows of r G are permutations, and the relabeled version of its group table as permutations is the same as the relabelling of the original group: ``` (r G) ≡ r ∘.{⍺[⍵]}⍨ ↓r G 1 ```