# Walsh permutation; inversions

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

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

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

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

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

0
1 3 5 1

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

8   (4+2)>
2 3 6 2

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

9   (3+3)>
3 1 7 3

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

9   (3+3)>
4 5 6 4

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

3   (2+2)>
5 7 1 5

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

14b   (7)>
6 7 2 6

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

8   (4+2)>
7 5 3 7

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

14a   (7)>
 Sorting by # gives the permutation (0,4,2,1,7,3,5,6) in the left column, which is reflection ∘ right shift ∘ wp(6,5,7) (with the compression matrix ).

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

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

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 ( 3, 5, 9, 1)

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 ( 3, 6,10, 2)

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 ( 1, 7,11, 3)

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 ( 5, 6,12, 4)

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 ( 7, 1,13, 5)

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 ( 7, 2,14, 6)

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 ( 5, 3,15, 7)

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 ( 9,10,12, 8)

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 (11,13, 1, 9)

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 (11,14, 2,10)

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 ( 9,15, 3,11)

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 (13,14, 4,12)

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 (15, 9, 5,13)

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 (15,10, 6,14)

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 (13,11, 7,15)

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 shift ∘ wp(12,10, 9, 7) (with the compression matrix ).

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

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 (). It pushes the other rows of the unity matrix down, and the last row "out of the matrix".

## Bended stripes

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

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

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

0
1 4 7 1

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

3   (2+2)>
2 7 4 2

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

3   (2+2)>
3 2 1 7

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

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

# IS CV CM Permutation
F
IN
0 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
1 1144441325096 ( 8,11,13, 1)

( 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 (11, 8,14, 2)

( 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 ( 2, 1, 7,11)

( 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 (13,14, 8, 4)

( 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 ( 4, 7, 1,13)

( 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 ( 7, 4, 2,14)

( 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 (14,13,11, 7)

( 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

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 () of the matrices, used in the image, corresponds to the lexicographical order of the compression vectors.

## Bit permutations

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 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 ( 1, 2, 4, 8)
1 87181920722 ( 2, 1, 4, 8)
2 13412045088 ( 1, 4, 2, 8)
3 101069338632 ( 4, 1, 2, 8)
4 262496507810 ( 2, 4, 1, 8)
5 269202530354 ( 4, 2, 1, 8)
6 175795200 ( 1, 2, 8, 4)
7 87357715922 ( 2, 1, 8, 4)
8 13588646400 ( 1, 8, 2, 4)
9 101249608320 ( 8, 1, 2, 4)
10 262679639762 ( 2, 8, 1, 4)
11 269386065362 ( 8, 2, 1, 4)
12 40237747488 ( 1, 4, 8, 2)
13 127895041032 ( 4, 1, 8, 2)
14 40325645088 ( 1, 8, 4, 2)
15 127986607008 ( 8, 1, 4, 2)
16 303216964872 ( 4, 8, 1, 2)
17 303260913672 ( 8, 4, 1, 2)
18 613140355490 ( 2, 4, 8, 1)
19 619846378034 ( 4, 2, 8, 1)
20 613228253090 ( 2, 8, 4, 1)
21 619934678690 ( 8, 2, 4, 1)
22 633259229234 ( 4, 8, 2, 1)
23 633303178034 ( 8, 4, 2, 1)

## Nimber multiplication

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