Essays/Symmetries of the Square

From J Wiki
Jump to: navigation, search

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


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.