3-bit Walsh permutation

From Wikiversity
Jump to: navigation, search
Created by mate2code.
Walsh permutation Rdrup.svg

There are OEISA002884(3) = (8-1)*(8-2)*(8-4) = 168 Walsh permutations of 8 elements.
The compression matrices are the elements of the general linear group GL(3,2)
and the permutations correspond to the elements of PSL(2,7), the symmetry group of the Fano plane.

A table of all 168 can be found here.


Fano plane collineations[edit]

Fano plane with nimber labels

The Walsh permutations leave the 0 unchanged,
so they can be interpreted as permutations of the seven points of the Fano plane
and it happens that these are the Fano plane's collineations.

E.g. these

Fanoperm124.svg
124

[1,0,0;
0,1,0;
0,0,1]

Fanoperm364.svg
364

[1,0,0;
1,1,0;
0,1,1]

Fanoperm524.svg
524

[1,0,0;
0,1,0;
1,0,1]

Fanoperm764.svg
764

[1,0,0;
1,1,0;
1,1,1]

are the four different powers of the 3-bit Gray code permutation,
and this

Fanoperm421.svg
421

[0,0,1;
0,1,0;
1,0,0]

is the 3-bit bit-reversal permutation.


Permutation patterns[edit]

The blue table shows 24 equivalence classes
containing turned, reflected and complemented collineations.
These are it's columns:

D     Real determinant of the 3×3 compression matrices (+ stands for 1, − for −1)
In two rows ∓ is shown: Determinants in the inner circle are −, those in the outer circle are +
Σ Number of ones in the compression matrices (sorting Co Ro will sort also this column)
In six rows 5 and 6 are shown: Sums in the inner circle are 5, those in the outer circle are 6 (analogously for Co Ro)
Co Ro Partitions representing the number of ones in the columns and rows of the compression matrices
Cy Partition representing the cycle structure of the permutations (compare OEISA198380)
F Fixed points (images that are not rotationally symmetric are examples)
E Example permutation
mateq Matrix patterns that appear in the blue box (links go to the green table)
permeq Collineations ordered by permutation pattern
The shade of the blue corresponds to the number of collineations in the box (1,2,3,6,12).

The violet numbers represent partitions by index numbers of OEISA194602 (compare this table).
As these numbers are everything but intuitive, the actual partitions are always shown in parentheses.
The sums shown in Co Ro give the corresponding entry in column Σ. In Cy only the non-one addends are shown.

D  Σ  Co Ro Cy F E mateq permeq
&1 +   3      0 (1+1+1)  0 (1+1+1) &1      0   &8 7 fixed points   Fanoperm124.svg     32    
&1 + 3  0 (1+1+1)  0 (1+1+1) &1  9 (3+3) &4 1 fixed point; digit sum 3 Fanoperm241.svg 33
&3 3  0 (1+1+1)  0 (1+1+1) &1  3 (2+2) &6 3 fixed points; digit sums 1 3 2 Fanoperm421.svg 32 33
&1 + 4  1 (2+1+1)  1 (2+1+1) &2 14 (7) &1 no fixed points Fanoperm341.svg 41.ab 42.ab
&3 4  1 (2+1+1)  1 (2+1+1) &2  8 (4+2) &2 1 fixed point; digit sum 1 Fanoperm431.svg 41.ab 45
&3 4  1 (2+1+1)  1 (2+1+1) &2  8 (4+2) &3 1 fixed point; digit sum 2 Fanoperm621.svg 41.ab 45
&3 4  1 (2+1+1)  1 (2+1+1) &2  9 (3+3) &2 1 fixed point; digit sum 1 Fanoperm521.svg 42.ab 46
&1 + 4  1 (2+1+1)  1 (2+1+1) &2  3 (2+2) &5 3 fixed points; digit sums 1 2 1 Fanoperm324.svg 45 46
&3 5  2 (3+1+1)  3 (2+2+1) &3  3 (2+2) &6 3 fixed points; digit sums 1 3 2 Fanoperm471.svg 50 53
&3 5  3 (2+2+1)  2 (3+1+1) &4  3 (2+2) &7 3 fixed points; digit sums 2 2 2 Fanoperm623.svg 50 53
&1 + 5  2 (3+1+1)  3 (2+2+1) &3  3 (2+2) &6 3 fixed points; digit sums 1 3 2 Fanoperm174.svg 50 54
&1 + 5  3 (2+2+1)  2 (3+1+1) &4  3 (2+2) &5 3 fixed points; digit sums 1 2 1 Fanoperm326.svg 50 54
&1 + 5  2 (3+1+1)  3 (2+2+1) &3  8 (4+2) &4 1 fixed point; digit sum 3 Fanoperm247.svg  53 57.ms
&1 + 5  3 (2+2+1)  2 (3+1+1) &4  8 (4+2) &3 1 fixed point; digit sum 2 Fanoperm351.svg  53 57.ms
&3 5  2 (3+1+1)  3 (2+2+1) &3  9 (3+3) &4 1 fixed point; digit sum 3 Fanoperm721.svg  54 57.ms
&3 5  3 (2+2+1)  2 (3+1+1) &4  9 (3+3) &2 1 fixed point; digit sum 1 Fanoperm465.svg  54 57.ms
&2 7 11 (3+2+2) 11 (3+2+2) &6  8 (4+2) &3 1 fixed point; digit sum 2 Fanoperm673.svg 70 74.ab
&2 7 11 (3+2+2) 11 (3+2+2) &6 14 (7) &1 no fixed points Fanoperm537.svg 71 74.ab
&3 5
6
 3
 5
(2+2+1)
(3+2+1)
 3
 5
(2+2+1)
(3+2+1)
&5 14 (7) &1 no fixed points Fanoperm615.svg BL.56 BM.56 BR.56
&1 + 5
6
 3
 5
(2+2+1)
(3+2+1)
 3
 5
(2+2+1)
(3+2+1)
&5  9 (3+3) &3 1 fixed point; digit sum 2 Fanoperm651.svg BL.56 TL.56
&1 + 5
6
 3
 5
(2+2+1)
(3+2+1)
 3
 5
(2+2+1)
(3+2+1)
&5  8 (4+2) &2 1 fixed point; digit sum 1 Fanoperm175.svg BM.56 TM.56
&1 + 5
6
 3
 5
(2+2+1)
(3+2+1)
 3
 5
(2+2+1)
(3+2+1)
&5 14 (7) &1 no fixed points Fanoperm751.svg BR.56 TR.56
&3 5
6
 3
 5
(2+2+1)
(3+2+1)
 3
 5
(2+2+1)
(3+2+1)
&5  9 (3+3) &2 1 fixed point; digit sum 1 Fanoperm561.svg TL.56 TM.56 TR.56
&3 5
6
 3
 5
(2+2+1)
(3+2+1)
 3
 5
(2+2+1)
(3+2+1)
&5  9 (3+3) &3 1 fixed point; digit sum 2 Fanoperm354.svg TL.56 TM.56 TR.56


Matrix patterns[edit]

The green table shows 29 equivalence classes
containing collineations with turned and reflected compression matrices.
These are it's columns:

Σ Number of ones in the compression matrices
5₂₃ tells that the matrix has a row or column with only ones, compare CoRo in blue table
E Example matrix
permeq Permutation patterns that appear in the green box (links go to the blue table)
mateq Collineations ordered by matrix pattern
The shade of the green corresponds to the number of collineations in the box.
Σ   E   permeq mateq
&1 3

[1,0,0;
0,1,0;
0,0,1]

30 34
&1 3

[0,0,1;
1,0,0;
0,1,0]

31 34
&2 4

[1,0,1;
1,0,0;
0,1,0]

43.ab 40
&2 4

[0,0,1;
1,0,1;
0,1,0]

43.ab 40
&2 4

[0,0,1;
1,0,0;
1,1,0]

40 44
&2 4

[0,0,1;
1,1,0;
0,1,0]

40 44
&2 4

[1,0,0;
1,1,0;
0,0,1]

43.ab 47
&2 4

[1,0,0;
0,1,0;
1,0,1]

44 47
&3 5₂₃

[1,1,0;
0,1,0;
0,1,1]

51.ab 52.ab
&3 5₂₃

[1,1,0;
1,0,1;
1,0,0]

51.ab 55.ab
&3 5₂₃

[1,0,0;
1,1,0;
1,0,1]

52.ab 56.ab
&3 5₂₃

[0,1,0;
1,1,1;
1,0,0]

55.ab 56.ab
&3 5₂₃

[1,0,1;
1,0,0;
1,1,0]

55.ab 56.ab
&6 7

[0,1,1;
1,1,1;
1,1,0]

72
&6 7

[1,1,0;
1,1,1;
1,0,1]

73
&6 7

[1,1,1;
1,0,1;
1,1,0]

72 73
&6 7

[1,0,1;
1,1,0;
1,1,1]

72 73
&4 5₃₃

[0,1,0;
1,0,1;
1,1,0]

B CL
&5 6

[1,0,1;
1,0,0;
1,1,1]

B CL
&4 5₃₃

[1,0,0;
1,1,0;
0,1,1]

B CM
&5 6

[1,0,0;
1,1,0;
1,1,1]

B CM
&4 5₃₃

[1,0,1;
1,0,0;
0,1,1]

B CR
&5 6

[0,1,0;
1,1,1;
1,1,0]

B CR
&4 5₃₃

[0,1,1;
1,0,1;
1,0,0]

CL T.ab
&5 6

[1,1,0;
1,1,1;
1,0,0]

CL T.ab
&4 5₃₃

[1,0,1;
0,1,0;
0,1,1]

CM T.ab
&5 6

[1,0,0;
1,1,1;
1,0,1]

CM T.ab
&4 5₃₃

[1,1,0;
0,1,1;
1,0,0]

CR T.ab
&5 6

[1,1,1;
1,0,1;
1,0,0]

CR T.ab


Graphs[edit]

The connections between permutation patterns (blue) and matrix patterns (green) can be visualized in five graphs.
It can be seen that, apart from the graph on the right, all compression matrices in the same graph have the same number of ones,
used as the first digit of the node numbers.

The compression matices have 3 ones.
The compression matices have 7 ones.
The compression matices have 5 or 6 ones.

The nodes are named after their positions:
T, C, B stand for top, center, bottom,
L, M, R stand for left, middle, right.
The compression matices have 4 ones.
The compression matices have 5 ones.

Conjugacy classes[edit]

The cycle structures 0, 3, 8 and 9 uniquely define four conjugacy classes with 1, 21, 42 and 56 elements.
The 48 permutations with cycle structure 14 (the 7-cycle) form two distinct conjugacy classes with 24 elements,
here called 14a and 14b. The inverse of a permutation in one of these is in the other one,
so in the blue table above each of the four boxes in a row with a 14 contains six permutations from 14a and six from 14b.

When the elements x and y belong to the conjugacy class C their powers xn and yn belong to the conjugacy class Cn.
When the conjugacy class is defined by the cycle structure it's powers follow from the cycle structure.
The powers of 14a and 14b can be seen in the examples below:


Powers of a permutation with two 3-cycles:

wp(7,2,1)1 wp(7,2,1)2
Fanoperm721.svg
721

[1,0,1;
1,1,0;
1,0,0]

Fanoperm427.svg
427

[0,0,1;
0,1,1;
1,0,1]

9 9
56.a 56.a
54 54


Powers of a permutation with a 4-cycle and a 2-cycle:

wp(6,2,1)1 wp(6,2,1)2 wp(6,2,1)3
Fanoperm621.svg
621

[0,0,1;
1,1,0;
1,0,0]

Fanoperm326.svg
326

[1,0,0;
1,1,1;
0,0,1]

Fanoperm423.svg
423

[0,0,1;
0,1,1;
1,0,0]

8 3 8
43.b 52.b 43.b
45 50 45


Powers of 14a and 14b:

wp(7,6,5)1 wp(7,6,5)2 wp(7,6,5)3 wp(7,6,5)4 wp(7,6,5)5 wp(7,6,5)6
Fanoperm765.svg
765

[1,0,1;
1,1,0;
1,1,1]

Fanoperm432.svg
432

[0,1,0;
0,1,1;
1,0,0]

Fanoperm516.svg
516

[1,1,0;
0,0,1;
1,0,1]

Fanoperm273.svg
273

[0,1,1;
1,1,1;
0,1,0]

Fanoperm641.svg
641

[0,0,1;
1,0,0;
1,1,0]

Fanoperm357.svg
357

[1,1,1;
1,0,1;
0,1,1]

14a 14a 14b 14a 14b 14b
73 40 CR CR 40 73
74.b 42.b BR.5 BR.6 42.a 74.a
wp(7,3,1)1 wp(7,3,1)2 wp(7,3,1)3 wp(7,3,1)4 wp(7,3,1)5 wp(7,3,1)6
Fanoperm731.svg
731

[1,1,1;
1,1,0;
1,0,0]

Fanoperm547.svg
547

[1,0,1;
0,0,1;
1,1,1]

Fanoperm615.svg
615

[0,1,1;
1,0,0;
1,0,1]

Fanoperm276.svg
276

[0,1,0;
1,1,1;
0,1,1]

Fanoperm352.svg
352

[1,1,0;
1,0,1;
0,1,0]

Fanoperm463.svg
463

[0,0,1;
0,1,1;
1,1,0]

14b 14b 14a 14b 14a 14a
B B B B B B
BM.6 BL.6 BR.5 BR.6 BL.5 BM.5

Cayley table[edit]

In the following Cayley table the conjugacy classes of the permutations are shown by colors.

The Walsh functions 124  ,   421  ,   376  ,   241  ,   765  ,   357
belong to the conjugacy classes 0  ,   3 (2+2)  ,   8 (4+2)  ,   9 (3+3)  ,   14a (7)  ,   14b (7)
with 1  ,   21  ,   42  ,   56  ,   24  ,   24 elements.

The Cayley table can be found here.