24. Symmetric Array

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

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 99 ⊢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 3    ⍝ perm from §19 above
0 1 2
0 2 1
1 0 2
1 2 0
2 0 1
2 1 0

   (perm ≢⍴A) (⊢≡⍉)⍤1 99 ⊢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 99 ⊢A , then

   A ≡ p0⍉p2⍉p1⍉A 
   A ≡ p0⍉p4⍉p2⍉p0⍉p7⍉p2⍉A 

for all sequences from the set of permutations P .

   P            (⊢≡⍉)⍤1 99 ⊢A
   (subgroup P) (⊢≡⍉)⍤1 99 ⊢A

where subgroup P is the subgroup generated by P .

   stdarg   ← {(⊂⍳⊃⌽⍴⍵),(↓⍵)}
   pvp      ← ∪ ∘ , ∘ (∘.{⍵[⍺]}⍨)
   subgroup ← ↑ ∘ (pvp⍣≡) ∘ stdarg

   ⊢ P←↑3 3?¨3
2 0 1
0 2 1
      
   subgroup P
0 1 2
2 0 1
0 2 1
1 2 0
1 0 2
2 1 0

   P (⊢≡⍉)⍤1 99 ⊢A
1 1
   (subgroup P) (⊢≡⍉)⍤1 99 ⊢A
1 1 1 1 1 1

subgroup generates the subgroup for one permutation (a vector) or for a matrix of permutations. First, stdarg makes a list of permutations and prefaces it with the identity permutation. pvp permutes a set of permutations against itself and selects the unique cells; application pvp to the limit 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 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 0 2 3 4 1
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 p←1⌽⍳r (rotating by 1) and q←(⌽⍳2⌊r),2↓⍳r (transposing the first two items) generate the entire group. See [81] or [49a]. Therefore, two permutations are sufficient for testing for symmetry.

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

   r←5
   ⊢ p←1⌽⍳r
1 2 3 4 0
   ⊢ q←(⌽⍳2⌊r),2↓⍳r
1 0 2 3 4
   ⍴ subgroup ↑ p q
120 5

   r←6
   ⊢ p←1⌽⍳r
1 2 3 4 5 0
   ⊢ q←(⌽⍳2⌊r),2↓⍳r
1 0 2 3 4 5
   ⍴ subgroup ↑ p q
720 6

Conclusion

Since p←1⌽⍳r and q←(⌽⍳2⌊r),2↓⍳r generate the entire permutation group,

   A ≡ p⍉A
   A ≡ q⍉A

if and only if A is symmetric.

Postscript

The presentation can be improved if ⍤1 99 can be written as ⍤1 ∞ and if there is a single glyph for the function coded variously as {⍵[⍺]} or ⌷⍤0 ∞ or (⊂⍺)⌷⍵ or ⍵⌷⍨⊂⍺ .

Appeared in J in [82, 83].