3-bit Walsh permutation

From Wikiversity
Jump to navigation Jump to search
Walsh permutation Rdrup.svg

There are Sloane'sA002884(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 Sloane'sA198380)
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 Sloane'sA194602 (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,