# Gray code permutation powers

n-bit Gray code permutations are permutations of 2n elements.
They have m different powers for the following n:

 n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 ... m 1 2 4 4 8 8 8 8 16 16 16 16 16 16 16 16 32 ... ( (n-1) )

With permutation composition they form cyclic groups Zm.
The consecutive powers applied on the non-negative integers give the infinite matrix .

Powers of gray code permutations are Walsh permutations
with lower unitriangular Toeplitz compression matrices related to the Sierpinski triangle.
The first element of the compression vector of Gn is always S(n),
whith S = = 1, 3, 5, 15... (Sierpinski triangle rows read like Binary numbers)
The other elements of the compression vector follow from the first one
because all diagonals of the compression matrix have the same value.

## 3 bit

The four different powers of the 3-bit Gray code permutation:

 Corresponding Compression vector Permutation matrix Fano plane collineation and compression matrix 124 364 524 764

Compare: 3-bit Walsh permutation

## 4 bit

 Cycle graph of the cyclic group Z4 The four permutations in a matrix (top left corner of ) Below the dual matrix, showing the single Binary digits The rightmost Binary matrix is the top left corner of . (see file description page)
 The left columns of the compression matrices form the matrix , which is the beginning of the Sierpinski triangle.
Cayley table of the cyclic group Z4

## 5 bit

The following calculation, multiplying the compression matrices using F2 operations,
shows that the 8 different powers of the 5-bit Gray code permutation form the cyclic group Z8:

The compression matrices are also shown in
Arndt, Jörg (2010). Matters Computational, Springer, p. 48.

## Infinite array

The infinite array of Gray code permutations can be generated by the binary array = W(S),
where W(0,1,2...) are the rows of the infinite binary Walsh matrix and S = = 1, 3, 5, 15...

The even columns of (counted from 0) show Binary expansions of fractions.
(The odd columns also do, but they just show the complements, so they shall be ignored.)

Among the first 2n numerators of the reduced fractions appear the numbers from 0 to 2n−1.
Among the first 2n denominators appear the first n+1 elements of S = .

The first 2,4,8,16,32... elements of this sequence sum up to fractions that are slightly smaller than powers of two:

 ``` 1 14 28 1016 2032 4064 8128 4194176 8388352 16776704 33553408 67106816 134213632 268427264 536854528 70368744144896 ``` ```/ / / / / / / / / / / / / / / / ``` ``` 3 15 15 255 255 255 255 65535 65535 65535 65535 65535 65535 65535 65535 4294967295 ``` ```= = = = = = = = = = = = = = = = ``` ```0000000000000000000000000000000000000000000001 0000000000000000000000000000000000000000001110 0000000000000000000000000000000000000000011100 0000000000000000000000000000000000001111111000 0000000000000000000000000000000000011111110000 0000000000000000000000000000000000111111100000 0000000000000000000000000000000001111111000000 0000000000000000000000001111111111111110000000 0000000000000000000000011111111111111100000000 0000000000000000000000111111111111111000000000 0000000000000000000001111111111111110000000000 0000000000000000000011111111111111100000000000 0000000000000000000111111111111111000000000000 0000000000000000001111111111111110000000000000 0000000000000000011111111111111100000000000000 1111111111111111111111111111111000000000000000 ``` ```/ / / / / / / / / / / / / / / / ``` ```00000000000000000000000000000011 00000000000000000000000000001111 00000000000000000000000000001111 00000000000000000000000011111111 00000000000000000000000011111111 00000000000000000000000011111111 00000000000000000000000011111111 00000000000000001111111111111111 00000000000000001111111111111111 00000000000000001111111111111111 00000000000000001111111111111111 00000000000000001111111111111111 00000000000000001111111111111111 00000000000000001111111111111111 00000000000000001111111111111111 11111111111111111111111111111111 ``` ``` = = = = = = = = = = = = = = = ``` ``` 2^0 − ( 2^0 / 2^4−1 ) 2^1 − ( 2^1 / 2^4−1 ) 2^2 − ( 2^2 / 2^8−1 ) 2^3 − ( 2^3 / 2^8−1 ) 2^4 − ( 2^4 / 2^8−1 ) 2^5 − ( 2^5 / 2^8−1 ) 2^6 − ( 2^6 / 2^16−1 ) 2^7 − ( 2^7 / 2^16−1 ) 2^8 − ( 2^8 / 2^16−1 ) 2^9 − ( 2^9 / 2^16−1 ) 2^10 − ( 2^10 / 2^16−1 ) 2^11 − ( 2^11 / 2^16−1 ) 2^12 − ( 2^12 / 2^16−1 ) 2^13 − ( 2^13 / 2^16−1 ) 2^14 − ( 2^14 / 2^32−1 ) ```