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
See also
- 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.