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

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

	CV	D	Σ	#	Permutation Inversion Vector	IN	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-bitEdit

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 S₄ with permutations P_n

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