Walsh permutations of 2n elements can be represented by an n-element compression vector
of integers 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 F2 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).
There are A002884(n) n-bit Walsh permutations.
Not all vectors with different elements correspond to Walsh permutations, as the following example shows:
|No Walsh permutation wp(1,2,3,4)|
Notation warning[edit | edit source]
In this article and the related material it was chosen to base the compression vector on the columns of the compression matrix. But it would probably have been better to base it on the rows. Then the bit permutations and the small permutations corresponding to their compression vectors would be homomorphic. With the current convention they form an antihomomorphism. This might be corrected in the future.
With the row based convention the result of the example multiplication above would be wp(2, 3, 9, 15) instead of wp(14, 11, 8, 12).
When a simple permutation of n elements is applied on the binary digits of numbers from 0 to 2n-1 the result is a permutation of the numbers from 0 to 2n-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.
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).
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.
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.
Some inversion sets of Walsh permutations are very regular.
E.g. there are 2n-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[edit | edit source]
3-bit[edit | edit source]
4-bit[edit | edit source]
There are A002884(4) = 20160 4-bit Walsh permutations.
Fixed points[edit | edit source]
The fixed points of an n-bit Walsh permutation correspond to a subgroup of Z2n. (Compare Subgroups of nimber addition)