Fifty Shades of J/Chapter 26
Table of Contents ... Glossary ... Previous Chapter ... Next Chapter
Principal Topics
- " (rank conjunction) |. (shift), /: (grade up) \: (grade down) |: (transpose) ` (gerund) ~ (reflex) subgroups, identity, inverse, cyclic groups, anti-cyclic groups, dihedral group.
Groups in mathematics are a reflection of patterns observed in what seem to be totally disparate contexts. Given that some of J’s founding concepts are based in mathematical ideas, it is not too surprising that the primitive verbs exhibit their own form of group behaviour. To start with, here is some simple geometry -
Plane transformations
Suppose the character ‘J’ is fitted into a 4-by-4 character frame thus
]J=.4 4 $' * ** * **' * * * * **
To turn it about its horizontal middle line do
(X=.|.)J ** * * * *
To turn J about a north-west/south-east axis :
(Q=.|:)J * * * ***
The effects of X then Q, and of Q then X are :
┌────┬────┐ │ * │*** │ │* │ *│ │* │ *│ │ ***│ * │ └────┴────┘
Use a gerund to generate two more verbs P and Y :
* * * * ** *** * * *
Two things are needed to complete the repertoire needed to form a group. First a half turn, for which either R or S could be applied twice (e.g. H=.R^:2), or X and Q can be continued with as atomic items :
(H=.X&.Q&X)J ** * * * *
... and secondly a ‘do nothing’ operation I=.[ or equivalently I=.] .
There are many alternative ways of defining these eight verbs. For example, using the rank conjunction, reverse ‘at rank 1’ means ‘at list level’ so that each member of the stack of four lists is separately reversed instead of the stack as a whole, which results in a Y reflection. The full set of eight transformations are given in the table below with some of the many possible variants which are increased on account of the equivalence of & and @ in this context .
alternative meaning algebra I=. [ ] identity H=. X&.Q&X X"1@X half-turn H=YX=XY X=. |. refln in Ox X=QS=YH Y=. X&.Q X"1 refln in Oy Y=QR=XH S=. Q&X X"1@Q rotn π/2 clockwise S=QX=YQ R=. X&Q Q@X"1 rotn π/2 a-clockwise R=XQ=QY P=. Q&.X X&R rotn in x=y P=XS=YR Q=. |: rotn in x=-y Q=YS=XR
The column headed ‘algebra’ contains some equivalences in which the conjunction & has been elided. A full composition table for the conjunction & applied to the eight verbs is
| I | R | H | S | X | P | Y | Q | |
|---|---|---|---|---|---|---|---|---|
| I | I | R | H | S | X | P | Y | Q |
| R | R | H | S | I | P | Y | Q | X |
| H | H | S | I | R | Y | Q | X | P |
| S | S | I | R | H | Q | X | P | Y |
| X | X | Q | Y | P | I | S | H | R |
| P | P | X | Q | Y | R | I | S | H |
| Y | Y | P | X | Q | H | R | I | S |
| Q | Q | Y | P | X | S | H | R | I |
This is an example of a mathematical group, or more fully a group of order eight since the body of the table contains nothing other than the basic eight distinct elements (this property is called closure).
Properties of groups
Let G be a set of elements {a, b, c,…} together with a pairwise operation between the elements, typically called the (group) product, or (group) operation and written thus: ab or (ab).
G is said to form a group under the given group product if it possesses the following four properties (see: http://mathworld.wolfram.com/Group.html):
- Closure: G is closed under the group product, i.e. if a and b are any two elements of G then so is (ab)
- Association: G is associative i.e. for all a∈G, b∈G, c∈G: (ab)c = a(bc)
- Identity: G has a unique element I called the identity such that for all a∈G: aI = Ia = a
- Inverse: every element a∈G has a unique inverse, i.e. there exists a unique element a⁻¹∈G such that aa⁻¹ = a⁻¹a = I
Furthermore if all the elements of G commute, i.e. for all a∈G and b∈G: ab = ba, then G is said to be Abelian. Conversely if there is at least one instance where ab ≠ ba then G is said to be non-Abelian.
In the present case,
- our group G is the set of all distinct transformations on the 4-by-4 character matrix J, called the "symmetries" of J,
- our group product is the operation of applying to J a given transformation (a) followed by a second given transformation (b) to yield the combined transformation (ab).
The body of the operation table shown above contains no elements outside the group, i.e. the group is closed under the given operation. Specifically the eight transformations of the plane which transform a square into its own outline are closed under the operation ‘perform in sequence’, which in J is rendered by the conjunction: Atop (@). Also because there are precisely eight distinct elements the group is said to be of order 8. Furthermore as we see from the table, RX=P but XR=Q, i.e. R and X do not commute. Therefore G is non-Abelian.
Groups and subgroups
Now look for structures in the ways in which group operations combine. To start with, the first four rows and columns in the above table themselves form a group of order four, which is structurally identical (isomorphic) to the table for addition in arithmetic modulo 4 (i.e. clock arithmetic applied to a clock with just four numbers). This table is
cyc=.| +/~@i. NB. cyclic group of order y. cyc 4 0 1 2 3 1 2 3 0 2 3 0 1 3 0 1 2
which can be transcribed into subsets of the 8-by-8 table by
(cyc 4)&{ each 'IRHS';'XPYQ'
┌────┬────┐
│IRHS│XPYQ│
│RHSI│PYQX│
│HSIR│YQXP│
│SIRH│QXPY│
└────┴────┘
The first of these is a subgroup of the full table but the second is not a subgroup because it has no identity element (that is an element with the property that Ia = aI=a for all elements of the subgroup). The two bottom quadrants have row shifts which go in the opposite direction to cyc 4 . A general algorithm for this uses the minus table for i.n in modulo n arithmetic together with two hooks
ac=.|(+-/~@i.) NB. anti-cyclic table of order y ac 4 0 3 2 1 1 0 3 2 2 1 0 3 3 2 1 0
(ac 4){'XPYQ' and (ac 4){'IRHS' give the bottom left-hand and right-hand quadrants respectively of the full table. These two expressions can be merged as (4+ac 4){'IRHSXPYQ', and the indices in the string 'IRHSXPYQ' of the cells in the four quadrants are, in clockwise order, given by (cyc 4), (4+cyc 4), (ac 4) and (4+cyc 4).
These define a non-Abelian group known as the dihedral group of order 4 (D4). An adverb based on a hook which adds the tally of a matrix to itself (recall that tally for a matrix is simply the number of rows) leads to the following general definition of dihedral groups :
a2n=.(+#)@ NB. adverb : adding 2 to the power n di=.(cyc,.cyc a2n),((ac a2n),.ac) NB. Dihedral group order n di 4 0 1 2 3 4 5 6 7 1 2 3 0 5 6 7 4 2 3 0 1 6 7 4 5 3 0 1 2 7 4 5 6 4 7 6 5 0 3 2 1 5 4 7 6 1 0 3 2 6 5 4 7 2 1 0 3 7 6 5 4 3 2 1 0
and
(di 4){'IRHSXPYQ'
generates the 8 by 8 composition table given above.
The table of I, H, X and Y rotations only is simply the dihedral group of order 2 (D2).
(di 2);(di 2){'IHXY'
┌───────┬────┐
│0 1 2 3│IHXY│
│1 0 3 2│HIYX│
│2 3 0 1│XYIH│
│3 2 1 0│YXHI│
└───────┴────┘
and the set of all possible subgroups is exhibited in the following lattice diagram in which a connecting line indicates that the lower node is a subgroup of the higher one.
{I,R,H,S,X,P,Y,Q}
|
──────────────────────────────
{I,H,X,Y} {I,R,H,S} {I,H,P,Q}
| | |
───────── | ─────────
{I,Y} {I,X} {I,H} {I,P} {I,Q}
| | | | |
────────────────────────────────────
|
{I}
On a two-dimensional plane there are eight shape-preserving transformations of the square, namely four rotations about the centre through 0,1, 2 and 3 right angles, together with four reflections, two in the axes joining midpoints of opposite sides, and two in the diagonals. These geometrical transformations can be demonstrated by performing J transformations on the matrix i.4 4, for example reflections about the x axis and about the diagonal x=-y are described by
(|.m);|:m=.i.4 4 ┌───────────┬─────────┐ │12 13 14 15│0 4 8 12│ │ 8 9 10 11│1 5 9 13│ │ 4 5 6 7│2 6 10 14│ │ 0 1 2 3│3 7 11 15│ └───────────┴─────────┘
The full set of eight transformations are given in the table below, in which the final column gives an algebraic shorthand in which, for example, R=QX means the rotation R is equivalent to a reflection X followed by a reflection Q.
alternative meaning algebra I identity H=. |.@|"1 |."1@|. half-turn H=YX=XY X=. |. refl in Ox X=QR=YH Y=. |."1 refl in Oy Y=QS=XH R=. |:@|. |."1@|: rotn pi%2 clockwise R=QX=YQ S=. |.@|: |:@|."1 rotn pi%2 a-clockwise S=XQ=QY P=. |.@R |:"1@S rotn in x=y P=XR=YS Q=. |: rotn in x=-y Q=YR=XS
In general the symmetries of an n-sided regular polygon (including the operation of flipping the polygon over) form the dihedral group (Gk: two-sided) of order n (Dn). For example
di 3 0 1 2 3 4 5 1 2 0 5 3 4 2 0 1 4 5 3 3 4 5 0 1 2 4 5 3 2 0 1 5 3 4 1 2 0
gives the non-Abelian group of symmetries of the equilateral triangle:
- 0, 1, 2 correspond to rotations by 0, π/3, 2π/3,
- 3, 4, 5 correspond to reflections in the three perpendicular bisectors of the sides.
Groups and grade
Group relationships exists between the grade operations, /: and \: , applied to permutation vectors and the symmetries of the square. To demonstrate here are two verbs with obvious similarities, which convert permutation vectors to matrices and vice versa :
pm=.=/~ i.@# NB. transforms perm vector to matrix pm 1 3 2 0 0 0 0 1 1 0 0 0 0 0 1 0 0 1 0 0 pv=.+/ .*~i.@# NB. transforms perm matrix to vector pv pm 1 3 2 0 1 3 2 0
The compositions of grade verbs which match the analogous transformations of the permutation matrix can be added to the previous table in the following way:
grade verb
compositionalternative I H=. |.@|"1 \:@\: |.@X X=. |. /:@\: |.@H Y=. |."1 \:@/: |. R=. |:@|. \:@\:@\: /:@|. S=. |.@|: \: |.@Q P=. |.@R /:@\:@\: \:@|. Q=. |: /: |.@S
The binary operation ‘perform in sequence’ is again modelled by the conjunction atop . Since the grade operations are dyadic, @ may not be elided, that is if u and v are any of the eight permutation operations, u@v (= u v y) is not in general equivalent to the hook u v which equals y u v y .
Code Summary
cyc=.| +/~@i. NB. cyclic group of order y ac=.|(+-/~@i.) NB. anti-cyclic table of order y a2n=.(+#)@ NB. adverb : add 2 to the power n di=.(cyc,.cyc a2n),((ac a2n),.ac) NB. Dihedral grp order n pm=.=/~ i.@# NB. Transforms permn vector to matrix pv=.+/ .*~i.@# NB. Transforms perm matrix to vector