Walsh permutation

The term n-bit Walsh permutation was chosen by the author for permutations of 2ⁿ elements, that permute Walsh functions into other Walsh functions.

When the rows of a Walsh matrix are permuted, the columns of the resulting matrix are usually no Walsh functions anymore.
When the permutation is a Walsh permutation, they are.

Walsh permutations of 2ⁿ elements can be represented by an n-element compression vector
of integers $\in \{ 1, ... , 2^n-1\}$ referring to the numbering of Walsh functions (displayed in orange in the images).
It corresponds to the n×n compression matrix. It's columns show the elements of the compression vector in binary representation.
The multiplication of the compression matrices (with F₂ operations) corresponds to the composition of the permutations.
As the compression matrices are the elements of the general linear group GL(n,2) the Walsh permutations form a group isomorphic to GL(n,2).

Product of two Walsh permutations: wp( 8,12, 2, 3) * wp( 6, 9, 1, 2) = wp(14,11, 8,12)      (compare section Bent functions)

Product of the compression matrices

Another example:   Gray * bitrev
Product of the 4-bit Gray code permutation and the 4-bit bit-reversal permutation $wp(3,6,12,8) * wp(8,4,2,1) = wp(8,12,6,3)$ Product of the compression matrices This product permutes the natural ordered Hadamard matrix (Walsh matrix) in the sequency ordered Hadamard matrix: In the latter one the number of sign changes per row is consecutive.

Not all vectors $(v_1,...,v_n)$ with different elements $\in \{ 1, ... , 2^n-1\}$ correspond to Walsh permutations, as the following example shows:

No Walsh permutation wp(1,2,3,4)
This is not a permutation of 16 elements, so there is no Walsh permutation $wp(1,2,3,4)$. The corresponding compression matrix would be which has determinant 0.

Bit permutation

When a simple permutation of n elements is applied on the binary digits of numbers from 0 to 2ⁿ-1 the result is a permutation of the numbers from 0 to 2ⁿ-1.
The example on the right corresponds to the simple permutation that swaps the first two and the last two digits of the 4-bit binary numbers.
Probably the most important bit permutation is the bit-reversal permutation.

Nimber multiplication

The rows of each nimber multiplication table are Walsh permutations (except row 0).
They are not only closed under multiplication (function composition), but even under addition (bitwise XOR).

Gray code permutation powers

Cayley table with compression matrices

Powers of the Gray code permutation have very simple compression matrices and vectors.
In each vector all entries follow from the first one, and the first entries follow from the rows of the Sierpinski triangle.

Bent functions

From 0111 1000 1000 1000 to wp(2,1,8,4)

Each bent function corresponds to a Walsh permutation.
This can be seen when all rows of its sec matrix are XORed with the function itself (second step in the example on the right).

Magic squares

Multigrade operator XOR These matrices are found in the dual matrices of the magic squares.

The Melencolia square, corresponding to wp(11, 7,14,13)

There are 24*9=216 Walsh permutations that correspond to magic squares of order 4.
One my say that only 6 of them are essentially different.

Inversions

wp( 3, 5, 9, 1)

wp( 4, 8, 1, 2)

wp(14,13,11, 7)

Some inversion sets of Walsh permutations are very regular.
E.g. there are 2ⁿ-1 n-bit Walsh permutations with horizontally striped inversion sets (like the left one of the examples). The pattern of the stripes is that of Walsh functions.

2-bit

The 2-bit Walsh permutations form the general linear group GL(2,2) which is also the symmetric group S₃.

Cayley table with permutations

Cayley table with compression matrices

3-bit

The 168 3-bit Walsh permutations correspond to the collineations of the Fano plane.

4-bit

Compression vectors