# Essays/Symmetric Array

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
```