Walsh permutation; bit permutation

Walsh permutation Rdrup.svg

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 (Sloane'sA055089) they form the infinite array Sloane'sA195665.

3-bitEdit

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-bitEdit

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

p23 permutes (0,1,2,3) into (3,2,1,0). P23 = wp(23,22,21,20) = wp(8,4,2,1) is the 4-bit bit-reversal permutation.

Applying all permutations p0,...,p23 of 0,...,3 on the digits of 0,...,15 gives the bit permutations P0,...,P23, which also form the symmetric group S4.
But the big permutations have to be composed in a different way, to get corresponding results:
 

  See example calculations.

 
      Cycle graphs of S4
The 4×4 matrices of the permutations pn are the transposed compression matrices
of the Walsh permutations Pn, here represented by their 16×16 matrices.


  Walsh permutation; inversions#Bit permutations