Walsh permutation; bit permutation

Walsh permutation

The term bit permutation was chosen by the author for Walsh permutations whose compression matrices are permutation matrices.

Ordered in rows like the corresponding finite permutations ( A055089) they form the infinite array  A195665.

3-bit

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

	CV	CM	D	Σ	#	Permutation Inversion Vector	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	2 1 4		−	3	722	0 2 1 3   4 6 5 7 0 0 1 0   0 0 1 0	2				&2   3   (2+2)>
2	1 4 2		−	3	288	0 1 4 5   2 3 6 7 0 0 0 0   2 2 0 0	4				&2   3   (2+2)>
3	4 1 2		+	3	1032	0 2 4 6   1 3 5 7 0 0 0 0   3 2 1 0	6				&4   9   (3+3)>
4	2 4 1		+	3	2210	0 4 1 5   2 6 3 7 0 0 1 0   2 0 3 0	6				&4   9   (3+3)>
5	4 2 1		−	3	2354	0 4 2 6   1 5 3 7 0 0 1 0   3 1 3 0	8				&2   3   (2+2)>

4-bit

Applying a permutation p_n of 0,...,3 on the reverse binary digits of numbers 0,...,15 gives a permutation P_n of these 16 elements.

p₂₃ permutes (0,1,2,3) into (3,2,1,0). P₂₃ = wp(2³,2²,2¹,2⁰) = wp(8,4,2,1) is the 4-bit bit-reversal permutation.

Applying all permutations p₀,...,p₂₃ of 0,...,3 on the digits of 0,...,15 gives the bit permutations P₀,...,P₂₃, which also form the symmetric group S₄.
But the big permutations have to be composed in a different way, to get corresponding results:
$p_{a}*p_{b}*...=p_{x}~~~~\Leftrightarrow ~~~~...*P_{b}*P_{a}=P_{x}$

See example calculations.

    Cycle graphs of S₄
The 4×4 matrices of the permutations p_n are the transposed compression matrices
of the Walsh permutations P_n, here represented by their 16×16 matrices.

With compression vectors
Magnification of permutation 7     Cycle graph of S4 with permutations Pn

24×16 matrix

This is the top left 24x16 submatrix of  A195665. Below the dual matrix. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 2 1 3 4 6 5 7 8 10 9 11 12 14 13 15 0 1 4 5 2 3 6 7 8 9 12 13 10 11 14 15 0 2 4 6 1 3 5 7 8 10 12 14 9 11 13 15 0 4 1 5 2 6 3 7 8 12 9 13 10 14 11 15 0 4 2 6 1 5 3 7 8 12 10 14 9 13 11 15 0 1 2 3 8 9 10 11 4 5 6 7 12 13 14 15 0 2 1 3 8 10 9 11 4 6 5 7 12 14 13 15 0 1 4 5 8 9 12 13 2 3 6 7 10 11 14 15 0 2 4 6 8 10 12 14 1 3 5 7 9 11 13 15 0 4 1 5 8 12 9 13 2 6 3 7 10 14 11 15 0 4 2 6 8 12 10 14 1 5 3 7 9 13 11 15 0 1 8 9 2 3 10 11 4 5 12 13 6 7 14 15 0 2 8 10 1 3 9 11 4 6 12 14 5 7 13 15 0 1 8 9 4 5 12 13 2 3 10 11 6 7 14 15 0 2 8 10 4 6 12 14 1 3 9 11 5 7 13 15 0 4 8 12 1 5 9 13 2 6 10 14 3 7 11 15 0 4 8 12 2 6 10 14 1 5 9 13 3 7 11 15 0 8 1 9 2 10 3 11 4 12 5 13 6 14 7 15 0 8 2 10 1 9 3 11 4 12 6 14 5 13 7 15 0 8 1 9 4 12 5 13 2 10 3 11 6 14 7 15 0 8 2 10 4 12 6 14 1 9 3 11 5 13 7 15 0 8 4 12 1 9 5 13 2 10 6 14 3 11 7 15 0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15

Walsh permutation; inversions#Bit permutations