Walsh permutation; inversions

From Wikiversity
Jump to navigation Jump to search
Walsh permutation Rdrup.svg
Inversion (discrete mathematics) Rdrup.svg
Abbreviations
CV Compression vector
CM Compression matrix
Σ Number of ones in the compression matrix
IS Inversion set
# Index number of the finite permutation
IN Inversion number


Stripes[edit | edit source]

Among the n-bit Walsh permutations are 2n with striped inversion sets.
As seen below they correspond to Walsh functions, i.e. the rows of the Walsh matrix of order 2n.
These permutations under composition form the group Z2n, just like the row numbers under bitwise XOR.

3-bit[edit | edit source]

An extract of the table of 3-bit Walsh permutations:

CV   CM   D Σ # Permutation
F
IN IS PM FPC Cy
0 1 2 4

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

+ 3 0 0 1 2 3   4 5 6 7
0 0 0 0   0 0 0 0
 0

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

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

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

Walsh permutation 124 Fano.svg &1   0
1 3 5 1

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

+ 5 17576 0 7 1 6   2 5 3 4
0 0 1 1   2 2 3 3
12

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

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

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

&3   8   (4+2)>
2 3 6 2

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

5 16854 0 1 7 6   2 3 5 4
0 0 0 1   2 2 2 3
10

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

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

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

&4   9   (3+3)>
3 1 7 3

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

6 22622 0 7 6 1   2 5 4 3
0 0 1 2   2 2 3 4
14

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

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

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

&4   9   (3+3)>
4 5 6 4

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

+ 5 16680 0 1 2 3   7 6 5 4
0 0 0 0   0 1 2 3
 6

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

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

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

&2   3   (2+2)>
5 7 1 5

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

6 22736 0 7 1 6   5 2 4 3
0 0 1 1   2 3 3 4
14

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

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

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

&6  14b   (7)>
6 7 2 6

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

+ 6 23454 0 1 7 6   5 4 2 3
0 0 0 1   2 3 4 4
14

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

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

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

Walsh permutation 165 Fano red.svg &3   8   (4+2)>
7 5 3 7

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

+ 7 17702 0 7 6 1   5 2 3 4
0 0 1 2   2 3 3 3
14

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

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

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

Walsh permutation 357 Fano red.svg &5  14a   (7)>
Sorting by # gives the permutation (0,4,2,1,7,3,5,6) in the left column, which is reflection right shiftwp(6,5,7) (with the compression matrix

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

).

Sorting by Permutation gives the (0,4,2,6, 1,5,3,7) in the left column, which is the bit-reversal permutation wp(4,2,1).

4-bit[edit | edit source]

Binary Walsh matrix of order 16
# IS CV CM Σ Permutation
F
IN
0 0 16 choose 2 array.svg ( 1, 2, 4, 8)

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

4 ( 0, 1, 2, 3,  4, 5, 6, 7,  8, 9,10,11, 12,13,14,15)
( 0, 0, 0, 0,  0, 0, 0, 0,  0, 0, 0, 0,  0, 0, 0, 0)
0
1 9804424107176 Inversion set 16; wp( 3, 5, 9, 1).svg ( 3, 5, 9, 1)

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

7 ( 0,15, 1,14,  2,13, 3,12,  4,11, 5,10,  6, 9, 7, 8)
( 0, 0, 1, 1,  2, 2, 3, 3,  4, 4, 5, 5,  6, 6, 7, 7)
56
2 9717242186454 Inversion set 16; wp( 3, 6,10, 2).svg ( 3, 6,10, 2)

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

7 ( 0, 1,15,14,  2, 3,13,12,  4, 5,11,10,  6, 7, 9, 8)
( 0, 0, 0, 1,  2, 2, 2, 3,  4, 4, 4, 5,  6, 6, 6, 7)
52
3 11112138397022 Inversion set 16; wp( 1, 7,11, 3).svg ( 1, 7,11, 3)

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

9 ( 0,15,14, 1,  2,13,12, 3,  4,11,10, 5,  6, 9, 8, 7)
( 0, 0, 1, 2,  2, 2, 3, 4,  4, 4, 5, 6,  6, 6, 7, 8)
60
4 9710017245480 Inversion set 16; wp( 5, 6,12, 4).svg ( 5, 6,12, 4)

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

7 ( 0, 1, 2, 3, 15,14,13,12,  4, 5, 6, 7, 11,10, 9, 8)
( 0, 0, 0, 0,  0, 1, 2, 3,  4, 4, 4, 4,  4, 5, 6, 7)
44
5 11118325501136 Inversion set 16; wp( 7, 1,13, 5).svg ( 7, 1,13, 5)

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

9 ( 0,15, 1,14, 13, 2,12, 3,  4,11, 5,10,  9, 6, 8, 7)
( 0, 0, 1, 1,  2, 3, 3, 4,  4, 4, 5, 5,  6, 7, 7, 8)
60
6 11205500164254 Inversion set 16; wp( 7, 2,14, 6).svg ( 7, 2,14, 6)

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

9 ( 0, 1,15,14, 13,12, 2, 3,  4, 5,11,10,  9, 8, 6, 7)
( 0, 0, 0, 1,  2, 3, 4, 4,  4, 4, 4, 5,  6, 7, 8, 8)
60
7 9810691044902 Inversion set 16; wp( 5, 3,15, 7).svg ( 5, 3,15, 7)

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

11 ( 0,15,14, 1, 13, 2, 3,12,  4,11,10, 5,  9, 6, 7, 8)
( 0, 0, 1, 2,  2, 3, 3, 3,  4, 4, 5, 6,  6, 7, 7, 7)
60
8 9709968804480 Inversion set 16; wp( 9,10,12, 8).svg ( 9,10,12, 8)

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

7 ( 0, 1, 2, 3,  4, 5, 6, 7, 15,14,13,12, 11,10, 9, 8)
( 0, 0, 0, 0,  0, 0, 0, 0,  0, 1, 2, 3,  4, 5, 6, 7)
28
9 11118365775656 Inversion set 16; wp(11,13, 1, 9).svg (11,13, 1, 9)

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

9 ( 0,15, 1,14,  2,13, 3,12, 11, 4,10, 5,  9, 6, 8, 7)
( 0, 0, 1, 1,  2, 2, 3, 3,  4, 5, 5, 6,  6, 7, 7, 8)
60
10 11205547694934 Inversion set 16; wp(11,14, 2,10).svg (11,14, 2,10)

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

9 ( 0, 1,15,14,  2, 3,13,12, 11,10, 4, 5,  9, 8, 6, 7)
( 0, 0, 0, 1,  2, 2, 2, 3,  4, 5, 6, 6,  6, 7, 8, 8)
60
11 9810651495902 Inversion set 16; wp( 9,15, 3,11).svg ( 9,15, 3,11)

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

11 ( 0,15,14, 1,  2,13,12, 3, 11, 4, 5,10,  9, 6, 7, 8)
( 0, 0, 1, 2,  2, 2, 3, 4,  4, 5, 5, 5,  6, 7, 7, 7)
60
12 11212772635560 Inversion set 16; wp(13,14, 4,12).svg (13,14, 4,12)

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

9 ( 0, 1, 2, 3, 15,14,13,12, 11,10, 9, 8,  4, 5, 6, 7)
( 0, 0, 0, 0,  0, 1, 2, 3,  4, 5, 6, 7,  8, 8, 8, 8)
60
13 9804464392016 Inversion set 16; wp(15, 9, 5,13).svg (15, 9, 5,13)

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

11 ( 0,15, 1,14, 13, 2,12, 3, 11, 4,10, 5,  6, 9, 7, 8)
( 0, 0, 1, 1,  2, 3, 3, 4,  4, 5, 5, 6,  6, 6, 7, 7)
60
14 9717289730334 Inversion set 16; wp(15,10, 6,14).svg (15,10, 6,14)

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

11 ( 0, 1,15,14, 13,12, 2, 3, 11,10, 4, 5,  6, 7, 9, 8)
( 0, 0, 0, 1,  2, 3, 4, 4,  4, 5, 6, 6,  6, 6, 6, 7)
60
15 11112098838182 Inversion set 16; wp(13,11, 7,15).svg (13,11, 7,15)

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

13 ( 0,15,14, 1, 13, 2, 3,12, 11, 4, 5,10,  6, 9, 8, 7)
( 0, 0, 1, 2,  2, 3, 3, 3,  4, 5, 5, 5,  6, 6, 7, 8)
60
Sorting by # gives the (0, 8,4,2,14, 1,13,11,7, 15,3,5,9, 6,10,12) in the left column, which is reflection right shiftwp(12,10, 9, 7) (with the compression matrix

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

).

Sorting by Permutation gives the (0,8,4,12, 2,10,6,14, 1,9,5,13, 3,11,7,15) in the left column, which is the bit-reversal permutation wp( 8, 4, 2, 1).

Compression matrices[edit | edit source]

Compression matrices of Walsh permutations with striped inversion sets.svg


The CM of the n-th permutation is a matrix B with horizontal stripes for the binary digits of n (gray lines in the image), XORed with a modified unity matrix U (black dots in the image).
U is modified by including an empty row where n has its lowest binary digit (Sloane'sA001511). It pushes the other rows of the unity matrix down, and the last row "out of the matrix".


Bended stripes[edit | edit source]

Among the n-bit Walsh permutations are 2n-1 whose inversion sets show bended stripes.
They correspond to Walsh functions, i.e. the rows of the Walsh matrix of order 2n-1.
These permutations under composition form the group Z2n-1, just like the row numbers under bitwise XOR.

3-bit[edit | edit source]

CV   CM   D # Permutation
F
IN IS PM FPC Cy
0 1 2 4

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

+ 0 0 1 2 3   4 5 6 7
0 0 0 0   0 0 0 0
 0

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

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

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

Walsh permutation 124 Fano.svg &1   0
1 4 7 1

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

3776 0 6 2 4   3 5 1 7
0 0 1 1   2 1 5 0
10

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

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

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

&2   3   (2+2)>
2 7 4 2

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

414 0 1 5 4   3 2 6 7
0 0 0 1   2 3 0 0
 6

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

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

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

&2   3   (2+2)>
3 2 1 7

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

4142 0 6 5 3   4 2 1 7
0 0 1 2   2 4 5 0
14

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

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

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

&2   3   (2+2)>

Sorting by # or Permutation gives (0,2,1,3) in the left column, which is the bit-reversal permutation wp(2,1).
Sorting by CV gives (0,3,1,2) in the left column, which is wp(3,1).


4-bit[edit | edit source]

# IS CV CM Permutation
F
IN
0 0 16 choose 2 array.svg ( 1, 2, 4, 8)

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

( 0, 1, 2, 3,  4, 5, 6, 7,  8, 9,10,11, 12,13,14,15)
( 0, 0, 0, 0,  0, 0, 0, 0,  0, 0, 0, 0,  0, 0, 0, 0)
0
1 1144441325096 Inversion set 16; wp( 8,11,13, 1).svg ( 8,11,13, 1)

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

( 0,14, 2,12,  4,10, 6, 8,  7, 9, 5,11,  3,13, 1,15)
( 0, 0, 1, 1,  2, 2, 3, 3,  4, 3, 7, 2, 10, 1,13, 0)
52
2 73376328534 Inversion set 16; wp(11, 8,14, 2).svg (11, 8,14, 2)

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

( 0, 1,13,12,  4, 5, 9, 8,  7, 6,10,11,  3, 2,14,15)
( 0, 0, 0, 1,  2, 2, 2, 3,  4, 5, 2, 2, 10,11, 0, 0)
44
3 1209107634782 Inversion set 16; wp( 2, 1, 7,11).svg ( 2, 1, 7,11)

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

( 0,14,13, 3,  4,10, 9, 7,  8, 6, 5,11, 12, 2, 1,15)
( 0, 0, 1, 2,  2, 2, 3, 4,  4, 6, 7, 2,  2,12,13, 0)
60
4 303182760 Inversion set 16; wp(13,14, 8, 4).svg (13,14, 8, 4)

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

( 0, 1, 2, 3, 11,10, 9, 8,  7, 6, 5, 4, 12,13,14,15)
( 0, 0, 0, 0,  0, 1, 2, 3,  4, 5, 6, 7,  0, 0, 0, 0)
28
5 1144707321296 Inversion set 16; wp( 4, 7, 1,13).svg ( 4, 7, 1,13)

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

( 0,14, 2,12, 11, 5, 9, 7,  8, 6,10, 4,  3,13, 1,15)
( 0, 0, 1, 1,  2, 3, 3, 4,  4, 6, 3, 9, 10, 1,13, 0)
60
6 73677162654 Inversion set 16; wp( 7, 4, 2,14).svg ( 7, 4, 2,14)

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

( 0, 1,13,12, 11,10, 6, 7,  8, 9, 5, 4,  3, 2,14,15)
( 0, 0, 0, 1,  2, 3, 4, 4,  4, 4, 8, 9, 10,11, 0, 0)
60
7 1209371443622 Inversion set 16; wp(14,13,11, 7).svg (14,13,11, 7)

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

( 0,14,13, 3, 11, 5, 6, 8,  7, 9,10, 4, 12, 2, 1,15)
( 0, 0, 1, 2,  2, 3, 3, 3,  4, 3, 3, 9,  2,12,13, 0)
60

Sorting by # or Permutation gives (0,4,2,6, 1,5,3,7) in the left column, which is the bit-reversal permutation wp(4,2,1).
Sorting by CV gives (0,3,5,6, 1,2,4,7) in the left column, which is wp(7,1,2).

Compression matrices[edit | edit source]

Compression matrices of Walsh permutations with bendedly striped inversion sets.svg
The CM are matrices with an even number of horizontal stripes (gray lines in the image) XORed with the unity matrix (black dots in the image).
The order by the evil numbers (Sloane'sA001969) of the matrices, used in the image, corresponds to the lexicographical order of the compression vectors.

Bit permutations[edit | edit source]

Walsh permutation; bit permutation Rdrup.svg
Inversion set of wp( 4, 1, 8, 2)
All columns are symmetrical.
Inversion set of wp(14,13,11, 7)
Here the symmetry is easily seen.
Cycle graph of the bit permutations
Permutations of 4 elements
Rdr.svg Symmetric group S4

The inversion sets in the table below have a common property that is not easily seen with this layout of the triangles:
They are symmetric to the diagonal that starts in the top right corner. (So all columns are symmetrical.)
This is also the case for all complemented bit permutations (with compression vectors that are permutations of (14,13,11, 7)).

# IS CV
0 0 16 choose 2 array.svg ( 1, 2, 4, 8)
1 87181920722 Inversion set 16; wp( 2, 1, 4, 8).svg ( 2, 1, 4, 8)
2 13412045088 Inversion set 16; wp( 1, 4, 2, 8).svg ( 1, 4, 2, 8)
3 101069338632 Inversion set 16; wp( 4, 1, 2, 8).svg ( 4, 1, 2, 8)
4 262496507810 Inversion set 16; wp( 2, 4, 1, 8).svg ( 2, 4, 1, 8)
5 269202530354 Inversion set 16; wp( 4, 2, 1, 8).svg ( 4, 2, 1, 8)
6 175795200 Inversion set 16; wp( 1, 2, 8, 4).svg ( 1, 2, 8, 4)
7 87357715922 Inversion set 16; wp( 2, 1, 8, 4).svg ( 2, 1, 8, 4)
8 13588646400 Inversion set 16; wp( 1, 8, 2, 4).svg ( 1, 8, 2, 4)
9 101249608320 Inversion set 16; wp( 8, 1, 2, 4).svg ( 8, 1, 2, 4)
10 262679639762 Inversion set 16; wp( 2, 8, 1, 4).svg ( 2, 8, 1, 4)
11 269386065362 Inversion set 16; wp( 8, 2, 1, 4).svg ( 8, 2, 1, 4)
12 40237747488 Inversion set 16; wp( 1, 4, 8, 2).svg ( 1, 4, 8, 2)
13 127895041032 Inversion set 16; wp( 4, 1, 8, 2).svg ( 4, 1, 8, 2)
14 40325645088 Inversion set 16; wp( 1, 8, 4, 2).svg ( 1, 8, 4, 2)
15 127986607008 Inversion set 16; wp( 8, 1, 4, 2).svg ( 8, 1, 4, 2)
16 303216964872 Inversion set 16; wp( 4, 8, 1, 2).svg ( 4, 8, 1, 2)
17 303260913672 Inversion set 16; wp( 8, 4, 1, 2).svg ( 8, 4, 1, 2)
18 613140355490 Inversion set 16; wp( 2, 4, 8, 1).svg ( 2, 4, 8, 1)
19 619846378034 Inversion set 16; wp( 4, 2, 8, 1).svg ( 4, 2, 8, 1)
20 613228253090 Inversion set 16; wp( 2, 8, 4, 1).svg ( 2, 8, 4, 1)
21 619934678690 Inversion set 16; wp( 8, 2, 4, 1).svg ( 8, 2, 4, 1)
22 633259229234 Inversion set 16; wp( 4, 8, 2, 1).svg ( 4, 8, 2, 1)
23 633303178034 Inversion set 16; wp( 8, 4, 2, 1).svg ( 8, 4, 2, 1)

Nimber multiplication[edit | edit source]

Walsh permutation; nimber multiplication Rdrup.svg


Inversion sets of the 15 permutations in the 16x16 nimber multiplication table


# CV Permutation F IN
0 ( 1, 2, 4, 8) (0, 1, 2, 3,   4, 5, 6, 7,   8, 9,10,11,  12,13,14,15) (0, 0, 0, 0,   0, 0, 0, 0,   0, 0, 0, 0,   0, 0, 0, 0) 0
13827898032492 ( 2, 3, 8,12) (0, 2, 3, 1,   8,10,11, 9,  12,14,15,13,   4, 6, 7, 5) (0, 0, 0, 2,   0, 0, 0, 2,   0, 0, 0, 2,   8, 8, 8,10) 40
7001306732168 ( 3, 1,12, 4) (0, 3, 1, 2,  12,15,13,14,   4, 7, 5, 6,   8,11, 9,10) (0, 0, 1, 1,   0, 0, 1, 1,   4, 4, 5, 5,   4, 4, 5, 5) 40
19217812814448 ( 8,12, 5,10) (0, 4, 8,12,   6, 2,14,10,  11,15, 3, 7,  13, 9, 5, 1) (0, 0, 0, 0,   2, 4, 0, 2,   2, 0, 8, 6,   2, 6,10,14) 56
1630614229512 ( 9,14, 1, 2) (0, 5,10,15,   2, 7, 8,13,   3, 6, 9,12,   1, 4,11,14) (0, 0, 0, 0,   3, 2, 2, 1,   6, 5, 3, 2,  11, 9, 3, 1) 48
15433122573720 (10,15,13, 6) (0, 6,11,13,  14, 8, 5, 3,   7, 1,12,10,   9,15, 2, 4) (0, 0, 0, 0,   0, 3, 5, 6,   4, 8, 2, 4,   5, 0,12,11) 60
5564988000144 (11,13, 9,14) (0, 7, 9,14,  10,13, 3, 4,  15, 8, 6, 1,   5, 2,12,11) (0, 0, 0, 0,   1, 1, 5, 5,   0, 5, 7,10,   8,11, 3, 4) 60
17445432818676 (12, 4,10,15) (0, 8,12, 4,  11, 3, 7,15,  13, 5, 1, 9,   6,14,10, 2) (0, 0, 0, 2,   1, 4, 3, 0,   1, 6, 9, 4,   7, 1, 5,13) 56
3551688986892 (13, 6,14, 7) (0, 9,14, 7,  15, 6, 1, 8,   5,12,11, 2,  10, 3, 4,13) (0, 0, 0, 2,   0, 4, 5, 3,   6, 2, 3, 9,   4,10,10, 2) 60
10678227659604 (14, 7, 2, 3) (0,10,15, 5,   3, 9,12, 6,   1,11,14, 4,   2, 8,13, 7) (0, 0, 0, 2,   3, 2, 1, 4,   7, 2, 1, 8,  10, 6, 2, 8) 56
10169232103620 (15, 5, 6,11) (0,11,13, 6,   7,12,10, 1,   9, 2, 4,15,  14, 5, 3, 8) (0, 0, 0, 2,   2, 1, 3, 6,   4, 7, 7, 0,   1, 9,11, 7) 60
15737148505928 ( 4, 8,15, 5) (0,12, 4, 8,  13, 1, 9, 5,   6,10, 2,14,  11, 7,15, 3) (0, 0, 1, 1,   0, 4, 2, 4,   4, 2, 8, 0,   3, 7, 0,12) 48
5084423155256 ( 5,10,11,13) (0,13, 6,11,   9, 4,15, 2,  14, 3, 8, 5,   7,10, 1,12) (0, 0, 1, 1,   2, 4, 0, 6,   1, 7, 5, 7,   6, 4,13, 3) 60
12454407149960 ( 6,11, 7, 9) (0,14, 7, 9,   5,11, 2,12,  10, 4,13, 3,  15, 1, 8, 6) (0, 0, 1, 1,   3, 1, 5, 1,   3, 7, 1, 9,   0,12, 7, 9) 60
8566683323240 ( 7, 9, 3, 1) (0,15, 5,10,   1,14, 4,11,   2,13, 7, 8,   3,12, 6, 9) (0, 0, 1, 1,   3, 1, 4, 2,   6, 2, 5, 5,   9, 3, 8, 6) 56