Walsh permutation; sequency ordered Walsh matrix

From Wikiversity
Jump to navigation Jump to search
Walsh permutation

A Walsh matrix is usually shown in natural order, like the left one in the following file.
It can also be shown in sequency order, like the right one, so that each row number is the number of sign changes in that row.

The permutation that changes the former into the latter is the product of the Gray code permutation and the bit-reversal permutation:

Product of the compression matrices

For the matrices of order 2n this permutation is wp( 2n-1 , 3 * ( 2n-2, ... , 4, 2, 1 ) ). E.g. for n=5 it is wp(16,24,12,6,3).

It seems that the cycle lengths of these permutations are all of the forms 2n-1 (Sloane'sA000225) and (4n-1)/3 (Sloane'sA002450).

   1      1                      1      1
  11      3                    101      5
 111      7                  10101     21
1111     15                1010101     85

That means that the length of all cycles is odd, which means that all these permutations have a unique square root.

Square roots[edit | edit source]

Like the natural ordered Walsh matrix () the sequency ordered can also be represented as a matrix product:

wp(6,1,5)
wp(6,9,1,10)

The two factors (which are transposed to each other) correspond to a Walsh permutation. Many Walsh permutations would be possible.
For the 8x8 matrix all whose compression vectors are permutations of (1,5,6).
For the 16x16 matrix all whose compression vectors are permutations of (1,6,9,10) or (2,5,13,14).
wp(6,1,5) and wp(6,9,1,10) are displayed, because they are the only ones with symmetric compression matrices.
They are the square roots of the permutations wp(4,6,3) and wp(8,12,6,3), that change natural into sequency order.

These square roots are unique and form the triangle Sloane'sA239303:

              1
           3     1
        6     1     5
     6     9     1    10
 12    18     1    17    10
Compression matrices
Graphs

These matrices correspond to graphs. They are chains where one end is connected to itself, so they can be interpreted as permutations, which are shown in the triangle Sloane'sA239304.

The compression matrix of size 16:

. . . . . . . 1 1 . . . . . . .
. . . . . . 1 . . 1 . . . . . .
. . . . . 1 . . . . 1 . . . . .
. . . . 1 . . . . . . 1 . . . .
. . . 1 . . . . . . . . 1 . . .
. . 1 . . . . . . . . . . 1 . .
. 1 . . . . . . . . . . . . 1 .
1 . . . . . . . . . . . . . . 1
1 . . . . . . . . . . . . . . .
. 1 . . . . . . . . . . . . . 1
. . 1 . . . . . . . . . . . 1 .
. . . 1 . . . . . . . . . 1 . .
. . . . 1 . . . . . . . 1 . . .
. . . . . 1 . . . . . 1 . . . .
. . . . . . 1 . . . 1 . . . . .
. . . . . . . 1 . 1 . . . . . .