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

• 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. Portions of the text previously appeared as part of Some Uses of { and } by Roger Hui, APL87 Conference Proceedings, May 10-14, 1987.