Essays/Symmetric Array

From J Wiki
Jump to: navigation, search

This note developed as a result of a question that Kip Murray posed to the J Forum on 2003-08-03, entitled "Testing Whether an Array is Symmetric".


Introduction

Definition: An array A with rank r>1 is symmetric if A -: p|:A for any permutation p of order r .

   ] A=: +// 3 $ ,: 2 3 7 11
 6  7 11 15
 7  8 12 16
11 12 16 20
15 16 20 24

 7  8 12 16
 8  9 13 17
12 13 17 21
16 17 21 25

11 12 16 20
12 13 17 21
16 17 21 25
20 21 25 29

15 16 20 24
16 17 21 25
20 21 25 29
24 25 29 33

   A -: 0 1 2|:A
1
   A -: 0 2 1|:A
1
   A -: 1 0 2|:A
1
   A -: 1 2 0|:A
1
   A -: 2 0 1|:A
1
   A -: 2 1 0|:A
1

All Transpositions

If P is a set of permutations, then P (] -: |:)"1 _ A matches A against each of its transpositions by P .  To test whether an array A is symmetric, we can simply match it against each one of its !#$A transposes.

   perm=: i.@! A. i.   NB. all permutations of order y
   perm 3
0 1 2
0 2 1
1 0 2
1 2 0
2 0 1
2 1 0

   (perm #$A) (] -: |:)"1 _ A
1 1 1 1 1 1

It is possible to test A for symmetry by matching against just 2 transposes.

Permutation Groups

If p and q are permutations of order #$A , then (p|:q|:A) -: (p{q)|:A .

   p=: ?~ #$A
   q=: ?~ #$A
   (p|:q|:A) -: (p{q)|:A
1

If A -: p|:A , then (by repeatedly substituting for A on the right hand side):
   A -: p|:p|:A
   A -: p|:p|:p|:A
   A -: p|:p|:p|:p|:A
and so on; similarly, if  P (] -: |:)"1 _ A , then
   A -: p0|:p2|:p1|:A
   A -: p0|:p4|:p2|:p0|:p7|:p2|:A
for all sequences from the set of permutations P .

Since (p|:q|:A) -: (p{q)|:A , the following are equivalent:
   P (] -: |:)"1 _ A
   (subgroup P) (] -: |:)"1 _ A
where subgroup P is the subgroup generated by P .

   stdarg  =: i.@{:@$ , ,:^:(1: -: #@$)
   pvp     =: ~. @ (,/) @ ({"1/~)
   subgroup=: pvp^:_ @ stdarg

   ] P=: 3 3 ? 3
1 0 2
1 0 2
   subgroup P
0 1 2
1 0 2
   P (] -: |:)"1 _ A
1 1
   (subgroup P) (] -: |:)"1 _ A
1 1

subgroup generates the subgroup for one permutation (a vector) or for a matrix of permutations. First, stdarg makes a matrix of permutations (if necessary), and prefaces it with the identity permutation. pvp permutes a set of permutations against itself, forms a matrix from the (3-dimensional) result, and selects the unique items from the matrix. Repeated application pvp therefore computes the subgroup.

   ] P=: stdarg 0 2 3 4 1
0 1 2 3 4
0 2 3 4 1
   pvp P
0 1 2 3 4
0 2 3 4 1
0 3 4 1 2
   pvp pvp P
0 1 2 3 4
0 2 3 4 1
0 3 4 1 2
0 4 1 2 3
   pvp pvp pvp P
0 1 2 3 4
0 2 3 4 1
0 3 4 1 2
0 4 1 2 3
   pvp^:_ P
0 1 2 3 4
0 2 3 4 1
0 3 4 1 2
0 4 1 2 3
   subgroup P
0 1 2 3 4
0 2 3 4 1
0 3 4 1 2
0 4 1 2 3

Two Permutations

The two permutations 0&C. (rotating by 1) and _2&C. (transposing the last two items) generate the entire group. See I.N. Herstein, Topics in Algebra, Second Edition, Xerox College Publishing, 1975, exercise 2.10.11; and R.K.W. Hui, Some Uses of { and }, APL87 Conference Proceedings, section 4.4. Therefore, two permutations are sufficient for testing for symmetry.

Are two permutations required? For n>2, no single permutation can generate the entire group, because a single-generator group is commutative, but the permutation group is not commutative.

   (,.0 _2) C. i.5
1 2 3 4 0
0 1 2 4 3
   $ subgroup (,.0 _2) C. i.5
120 5

   (,.0 _2) C. i.6
1 2 3 4 5 0
0 1 2 3 5 4
   $ subgroup (,.0 _2) C. i.6
720 6

The verb gen below generates any permutation of order > 1 as a sequence of the two permutations 0&C. and _2&C. .  It is based on the idea that
   p=: 0 C. i.n
   q=: _2 C. i.n
can generate
   p0=: {/ (n=>:i.2+n) { p,:q
   q0=: q
which are similar to p and q except that the leading item is invariant under permutation by p0 and q0 .  e.g. for n=: 7

   p: 1 2 3 4 5 6 0
   q: 0 1 2 3 4 6 5

   p0: 0 2 3 4 5 6 1
   q0: 0 1 2 3 4 6 5

gen=: gn { (,.0 _2)"_ C. i.@#

gn=: 3 : 0
 0 ,~ (0 C. i.#y) gn y
:
 if. 2=n=. #y do.
  (x-:y)}.1
 else.
  m=. x i. {.y
  (m#0) ,~ ; ((m|.x) gn&}. y) { (n=>:i.2+n) ; 1
 end.
)
   7 {. gen 3 1 4 2 0
0 1 2 4 3
1 2 3 4 0
1 2 3 4 0
1 2 3 4 0
1 2 3 4 0
0 1 2 4 3
1 2 3 4 0
   $ gen 3 1 4 2 0
54 5
   ~. gen 3 1 4 2 0
0 1 2 4 3
1 2 3 4 0
   {/ gen 3 1 4 2 0
3 1 4 2 0

   (-: {/@gen) ?~5
1
   (-: {/@gen) ?~7
1

Conclusion

Since 0&C. and _2&C. generate the entire group,
   A -: 0|:A
   A -: _2|:A
if and only if A is symmetric.

<!> Note: the dyad |: accepts non-standard specifications for its permutation left argument; for numeric x the phrase x|:y is equivalent to (x C. i.#$y)|:y .

   sym=: (-: 0&|:) *. (-: _2&|:)
   sym A
1



See also


Contributed by Roger Hui.