Essays/Symmetries of the Square
The following are tables of the group of transpositions (reflections and rotations) of the square, using two sets of labels:
] |.@|: |."1@|. |."1@|: |. |: |."1 |.@|:@|. |.@|: |."1@|. |."1@|: ] |.@|:@|. |. |: |."1 |."1@|. |."1@|: ] |.@|: |."1 |.@|:@|. |. |: |."1@|: ] |.@|: |."1@|. |: |."1 |.@|:@|. |. |. |: |."1 |.@|:@|. ] |.@|: |."1@|. |."1@|: |: |."1 |.@|:@|. |. |."1@|: ] |.@|: |."1@|. |."1 |.@|:@|. |. |: |."1@|. |."1@|: ] |.@|: |.@|:@|. |. |: |."1 |.@|: |."1@|. |."1@|: ]
] \: \:@\: /:@|. |. /: /:@\: \:@|. \: \:@\: /:@|. ] \:@|. |. /: /:@\: \:@\: /:@|. ] \: /:@\: \:@|. |. /: /:@|. ] \: \:@\: /: /:@\: \:@|. |. |. /: /:@\: \:@|. ] \: \:@\: /:@|. /: /:@\: \:@|. |. /:@|. ] \: \:@\: /:@\: \:@|. |. /: \:@\: /:@|. ] \: \:@|. |. /: /:@\: \: \:@\: /:@|. ]
] ] identity |.@|: \: rotate counterclockwise 90° |."1@|. \:@\: rotate counterclockwise 180° |."1@|: /:@|. rotate counterclockwise 270° |. |. reflect along x-axis |: /: reflect along main diagonal |."1 /:@\: reflect along y-axis |.@|:@|. \:@|. reflect along back diagonal
The second set of labels are due to considerations discovered independently by Thomson [1979], Hui [1981], and Benkard and Seebe [1983]:
{= and i."1&1 are an inverse pair, mapping integer permutation vectors to boolean permutation matrices and vice versa. Let F be a composition of ] \: /: |. , a function on permutations, and T be a composition of ] |: |. |."1 , a transposition of the square. Identify F and T , if
(F -: T&.({=) ) p (T -: F&.(i."1&1)) m
In other words, the group may be viewed as a group of transpositions of the square, or isomorphically as a group of functions on permutations.
For example:
NB. reflect along y-axis F=: /:@\: T=: |."1 ] p=: ?.~ 5 1 4 0 3 2 ({=) p 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 T ({=) p 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 i."1&1 T ({=) p 3 0 4 1 2 F p 3 0 4 1 2 (F -: T&.({=)) p 1 ] m=: ({=) p 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 i."1&1 m 1 4 0 3 2 F i."1&1 m 3 0 4 1 2 ({=) F i."1&1 m 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 T m 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 (T -: F&.(i."1&1)) m 1
The tables are a compact presentation of numerous identities involving functions ] |: |. |."1 on square matrices, or ] \: /: |. on permutations: The entry (<i,j){G is equivalent to the result of composing (<i,0){G and (<0,j){G . For example:
i,j row column composition simplification 1 6 \: /:@\: \:@/:@\: /: |.@|: |."1 |.@|:@:(|."1) |: 5 5 /: /: /:@/: ] |: |: |:@|: ] 2 1 \:@\: \: \:@\:@\: /:@|. |."1@|. |.@|: |."1@|.@|.@|: |."1@|: 2 2 \:@\: \:@\: \:@\:@\:@\: ] |."1@|. |."1@|. |."1@|.@:(|."1)@|. ]
References
- Iverson, Kenneth E., Formalism in Programming Languages, Communications of the ACM, Volume 7, Number 2, 1964-02, Table 9.
- Thomson, Norman D., The Geometric Primitives of APL, APL79 Conference Proceedings, 1978-05-30.
- Hui, Roger, The N Queens Problem, APL Quote Quad, Volume 11, Number 3, 1981-03.
- Benkard, J. Philip, and John N. Seebe, Reflections on Grades, APL83 Conference Proceedings, 1983-04-10.
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. Portions of the text previously appeared as part of Some Uses of { and } by Roger Hui, APL87 Conference Proceedings, May 10-14, 1987.