# Walsh permutation; sequency ordered Walsh matrix

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:

For the matrices of order 2^{n} this permutation is *wp*( 2^{n-1} , 3 * ( 2^{n-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 2^{n}-1 ( A000225) and (4^{n}-1)/3 ( A002450).

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:

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 A239303:

1 3 1 6 1 5 6 9 1 10 12 18 1 17 10

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 A239304.

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