Gray code permutation powers

Walsh permutation

The n-bit Gray code G_n is a permutation of the integers from 0 to 2ⁿ − 1, whose only fixed points are 0 and 1.

The powers of G_n form the the cyclic group Z_n, if n is a power of 2.
In general they form the the cyclic group Z_m, with $m=2^{\lfloor {\log }_{2}n\rfloor }$ (which is Template:Oeislink(n−1)).

n	1	2	3..4	5..8	9..16	17..32
m	1	2	4	8	16	32

Gray matrix

The following sections show the powers for n = 2 .. 5.   (A more readable version for n = 6 can be found here.)
Each row has the exponent k on the left, then the vector abbreviating the Walsh permutation, and on the right the permutation itself.
It can be seen, that each m×2ⁿ matrix is the top left corner of the next one.
This leads to the infinite matrix G = Template:Oeis whose rows are G^k.

2-bit

0         1   2         0   1   2   3
1         1   3         0   1   3   2

3-bit

0         1   2   4         0   1   2   3   4   5   6   7
1         1   3   6         0   1   3   2   6   7   5   4
2         1   2   5         0   1   2   3   5   4   7   6
3         1   3   7         0   1   3   2   7   6   4   5

4-bit

0         1   2   4   8         0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
1         1   3   6  12         0   1   3   2   6   7   5   4  12  13  15  14  10  11   9   8
2         1   2   5  10         0   1   2   3   5   4   7   6  10  11   8   9  15  14  13  12
3         1   3   7  15         0   1   3   2   7   6   4   5  15  14  12  13   8   9  11  10

5-bit

0         1   2   4   8  16         0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31
1         1   3   6  12  24         0   1   3   2   6   7   5   4  12  13  15  14  10  11   9   8  24  25  27  26  30  31  29  28  20  21  23  22  18  19  17  16
2         1   2   5  10  20         0   1   2   3   5   4   7   6  10  11   8   9  15  14  13  12  20  21  22  23  17  16  19  18  30  31  28  29  27  26  25  24
3         1   3   7  15  30         0   1   3   2   7   6   4   5  15  14  12  13   8   9  11  10  30  31  29  28  25  24  26  27  17  16  18  19  22  23  21  20
4         1   2   4   8  17         0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  17  16  19  18  21  20  23  22  25  24  27  26  29  28  31  30
5         1   3   6  12  25         0   1   3   2   6   7   5   4  12  13  15  14  10  11   9   8  25  24  26  27  31  30  28  29  21  20  22  23  19  18  16  17
6         1   2   5  10  21         0   1   2   3   5   4   7   6  10  11   8   9  15  14  13  12  21  20  23  22  16  17  18  19  31  30  29  28  26  27  24  25
7         1   3   7  15  31         0   1   3   2   7   6   4   5  15  14  12  13   8   9  11  10  31  30  28  29  24  25  27  26  16  17  19  18  23  22  20  21

The 5×5 matrices can be found on page 48 of Matters Computational by Jörg Arndt (2010), which can be found here: jjj.de/fxt

Zhegalkin matrix

W: 256×256 binary Walsh matrix
Ж: 8×256 Zhegalkin matrix
S: 1, 3, 5, 15, 17, 51, 85, 255   (sequence corresponding to an 8×8 Sierpiński triangle)

The image on the right shows the four powers of G₄.
The dual matrix below shows the separated binary digits of the integer entries.
It's columns correspond to the entries of Zhegalkin permutation Ж₂ (row 2 of Template:Oeis),
which is the Walsh permutation corresponding to the 4×4 lower triangular Template:W.

The whole integer matrix can be derived from this binary matrix:
Each of the other elements of the dual matrix is a stretch of its neighbor with the smaller place value,
i.e. the left half is doubled, and the right half vanishes.

The infinite Zhegalkin matrix Ж is the infinite Gray matrix G mod 2.

Let stretchsum be a function that receives a binary matrix whose left column has only zeros,
and returns the integer matrix created by adding up its stretches multiplied with binary place values.
Then G = stretchsum(Ж).

Let W be the infinite binary Walsh matrix (whose 16×16 top left corner is shown on the right), and W_i the binary Walsh function in row i,
and let S = Template:Oeis = 1, 3, 5, 15... be the integer sequence corresponding to the Sierpiński triangle,
then Ж = W_S, i.e. the rows of W whose indices are in S.

That means that the Gray code power G^k = stretchsum(W_S(k)).