Walsh permutation; inversions
Walsh permutation |
Inversion (discrete mathematics) |
|
Stripes edit
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
An extract of the table of 3-bit Walsh permutations:
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 edit
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).
Matrices |
---|
Compression vectors: 1 2 4 8 3 5 9 1 3 6 10 2 1 7 11 3 5 6 12 4 7 1 13 5 7 2 14 6 5 3 15 7 9 10 12 8 11 13 1 9 11 14 2 10 9 15 3 11 13 14 4 12 15 9 5 13 15 10 6 14 13 11 7 15 Permutations: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 15 1 14 2 13 3 12 4 11 5 10 6 9 7 8 0 1 15 14 2 3 13 12 4 5 11 10 6 7 9 8 0 15 14 1 2 13 12 3 4 11 10 5 6 9 8 7 0 1 2 3 15 14 13 12 4 5 6 7 11 10 9 8 0 15 1 14 13 2 12 3 4 11 5 10 9 6 8 7 0 1 15 14 13 12 2 3 4 5 11 10 9 8 6 7 0 15 14 1 13 2 3 12 4 11 10 5 9 6 7 8 0 1 2 3 4 5 6 7 15 14 13 12 11 10 9 8 0 15 1 14 2 13 3 12 11 4 10 5 9 6 8 7 0 1 15 14 2 3 13 12 11 10 4 5 9 8 6 7 0 15 14 1 2 13 12 3 11 4 5 10 9 6 7 8 0 1 2 3 15 14 13 12 11 10 9 8 4 5 6 7 0 15 1 14 13 2 12 3 11 4 10 5 6 9 7 8 0 1 15 14 13 12 2 3 11 10 4 5 6 7 9 8 0 15 14 1 13 2 3 12 11 4 5 10 6 9 8 7 Little-endian factorial numbers: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 0 0 0 1 2 2 2 3 4 4 4 5 6 6 6 7 0 0 1 2 2 2 3 4 4 4 5 6 6 6 7 8 0 0 0 0 0 1 2 3 4 4 4 4 4 5 6 7 0 0 1 1 2 3 3 4 4 4 5 5 6 7 7 8 0 0 0 1 2 3 4 4 4 4 4 5 6 7 8 8 0 0 1 2 2 3 3 3 4 4 5 6 6 7 7 7 0 0 0 0 0 0 0 0 0 1 2 3 4 5 6 7 0 0 1 1 2 2 3 3 4 5 5 6 6 7 7 8 0 0 0 1 2 2 2 3 4 5 6 6 6 7 8 8 0 0 1 2 2 2 3 4 4 5 5 5 6 7 7 7 0 0 0 0 0 1 2 3 4 5 6 7 8 8 8 8 0 0 1 1 2 3 3 4 4 5 5 6 6 6 7 7 0 0 0 1 2 3 4 4 4 5 6 6 6 6 6 7 0 0 1 2 2 3 3 3 4 5 5 5 6 6 7 8 |
Compression matrices edit
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 ( A001511). It pushes the other rows of the unity matrix down, and the last row "out of the matrix".
Bended stripes edit
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
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
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
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 ( A001969) of the matrices, used in the image, corresponds to the lexicographical order of the compression vectors.
Bit permutations edit
| |||
|
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)).
F |
---|
Little-endian factorial numbers: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 2 2 0 0 0 0 0 0 2 2 0 0 0 0 0 0 3 2 1 0 0 0 0 0 3 2 1 0 0 0 1 0 2 0 3 0 0 0 1 0 2 0 3 0 0 0 1 0 3 1 3 0 0 0 1 0 3 1 3 0 0 0 0 0 0 0 0 0 4 4 4 4 0 0 0 0 0 0 1 0 0 0 1 0 4 4 5 4 0 0 1 0 0 0 0 0 0 0 0 0 6 6 4 4 2 2 0 0 0 0 0 0 0 0 0 0 7 6 5 4 3 2 1 0 0 0 1 0 0 0 1 0 6 4 7 4 2 0 3 0 0 0 1 0 0 0 1 0 7 5 7 4 3 1 3 0 0 0 0 0 2 2 0 0 4 4 0 0 6 6 0 0 0 0 0 0 3 2 1 0 4 4 0 0 7 6 1 0 0 0 0 0 2 2 0 0 6 6 2 2 6 6 0 0 0 0 0 0 2 2 0 0 7 6 3 2 7 6 1 0 0 0 0 0 3 2 1 0 6 4 2 0 9 6 3 0 0 0 0 0 3 2 1 0 7 5 3 1 9 6 3 0 0 0 1 0 2 0 3 0 4 0 5 0 6 0 7 0 0 0 1 0 3 1 3 0 4 0 5 0 7 1 7 0 0 0 1 0 2 0 3 0 6 2 7 2 6 0 7 0 0 0 1 0 2 0 3 0 7 3 7 2 7 1 7 0 0 0 1 0 3 1 3 0 6 2 5 0 9 3 7 0 0 0 1 0 3 1 3 0 7 3 6 1 9 3 7 0 Inversion numbers: 0 4 8 12 12 16 16 20 24 28 28 32 24 28 32 36 36 40 28 32 36 40 40 44 |
Nimber multiplication edit
Walsh permutation; nimber multiplication |
# | 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 |