Walsh permutation

The term Walsh permutation was chosen by the author for permutations that permute Walsh functions into other Walsh functions.
A Walsh permutation of degree n has length 2ⁿ, and corresponds to an n×n matrix in the general linear group of degree n over the finite field.
This matrix will sometimes be called compression matrix, and its expression as a vector of n integers $\in \{1,...,2^{n}-1\}$ will be called compression vector.

There are A002884(n) Walsh permutations of degree n.

Product of two Walsh permutations: wp( 8,12, 2, 3) * wp( 6, 9, 1, 2) = wp(14,11, 8,12)
(the product of two Walsh permutations related to bent functions)

Product of the compression matrices

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.

Notation warning

This article and its subpages currently use two different ways to name and display Walsh permutations. In older files the direction of the compression vector is horizontal, and the permutation is vertical. In new files both compression vector and permutation are horizontal. The old files are gradually replaced. 3-bit Walsh permutation already uses new files.

wp(1, 3, 5) new = wp(7, 2, 4) old

Ambiguity of wp(1, 3, 5) new: horizontal (0, 1, 3, 2, 5, 4, 6, 7) old: vertical (0, 7, 2, 5, 4, 3, 6, 1)

wp(1, 14, 4, 8) old = wp(1, 2, 6, 10) new

Sequences

There are mainly two ways to express the number of Walsh permutations as a product:

• number of bases of an n-dimensional vector space over GF(2)   ·   n!
• product of the first n powers of two {1, 2, 4, 8, ...}   ·   product of the first n Mersenne numbers {1, 3, 7, 15, ...}

n	A002884(n)	A023758	A053601(n) · A000142(n)		A006125(n) · A005329(n)		A002884(n−1) * A006516(n)
0	1		1 · 1	20 · 1 / 1 · 20 · 1	20 · 20 · 1	20 · 1
1	1	1	1 · 1	20 · 1 / 1 · 20 · 1	20 · 20 · 1	20 · 1	1 · 20 · 1	1 · 1
2	6	2 · 3	3 · 2	20 · 3 / 1 · 21 · 1	20 · 21 · 3	21 · 3	1 · 21 · 3	1 · 6
3	168	4 · 6 · 7	28 · 6	22 · 21 / 3 · 21 · 3	22 · 21 · 21	23 · 21	6 · 22 · 7	6 · 28
4	20160	8 · 12 · 14 · 15	840 · 24	23 · 315 / 3 · 23 · 3	23 · 23 · 315	26 · 315	168 · 23 · 15	168 · 120
5	9999360	16 · 24 · 28 · 30 · 31	83328 · 120	27 · 9765 / 15 · 23 · 15	27 · 23 · 9765	210 · 9765	20160 · 24 · 31	20160 · 496
6	20158709760	32 · 48 · 56 · 60 · 62 · 63	27998208 · 720	211 · 615195 / 45 · 24 · 45	211 · 24 · 615195	215 · 615195	9999360 · 25 · 63	9999360 · 2016

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

See also Algebraic normal form.

Sequency ordered Walsh matrix

The permutation that changes the natural ordered into the sequency ordered Walsh matrix is the product of the Gray code permutation and the bit-reversal permutation.

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(13,11, 7,15)

wp(14,13,11, 7)

wp( 4, 8, 1, 2)

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

wp(3, 1)

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

3-bit

wp(5,3,7) as a permutation of the Fano plane

wp(5,3,7) has permutation pattern 73, matrix pattern 74.b, and its inversion set is striped.

The A002884(3) = 168 3-bit Walsh permutations correspond to the collineations of the Fano plane.

Compression vectors, Permutations

4-bit

There are A002884(4) = 20160 4-bit Walsh permutations.

Compression vectors

Relationship to seals

The fixed points of an n-bit Walsh permutation are seals of arity n.

The splice of a Walsh permutation is the XOR of its values and indices. It is a set partition.
The set of its values also describes a seal.

wp(5,6,4)

seal 1001 1001 (compare matrix 12 in this list)