Walsh permutation; inversions

Walsh permutation

Inversion (discrete mathematics)

The vectors need to be corrected. See Walsh permutation#Notation warning. Done only for section Nimber multiplication.

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 2ⁿ with striped inversion sets.
As seen below they correspond to Walsh functions, i.e. the rows of the Walsh matrix of order 2ⁿ.
These permutations under composition form the group Z₂ⁿ, 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				&1   0
1	3 5 1		+	5	17576	0 7 1 6   2 5 3 4 0 0 1 1   2 2 3 3	12				&3   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				&4   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				&4   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				&2   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				&6  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				&3   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				&5  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).

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

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

Among the n-bit Walsh permutations are 2^n-1 whose inversion sets show bended stripes.
They correspond to Walsh functions, i.e. the rows of the Walsh matrix of order 2^n-1.
These permutations under composition form the group Z₂^n-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				&1   0
1	4 7 1		−	3776	0 6 2 4   3 5 1 7 0 0 1 1   2 1 5 0	10				&2   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				&2   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				&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

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

Bit permutations

Walsh permutation; bit permutation
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)

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

Walsh permutation; nimber multiplication

Images: Inversion set of a 4-bit 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	( 4, 8, 6,11)	(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	( 5,10, 2, 3)	(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	( 6,11,14, 7)	(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	( 7, 9,10,15)	(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	( 8,12,11,13)	(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	( 9,14,15, 5)	(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	(10,15, 3, 1)	(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	(11,13, 7, 9)	(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	(12, 4,13, 6)	(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	(13, 6, 9,14)	(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	(14, 7, 5,10)	(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	(15, 5, 1, 2)	(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