Gray code permutation powers

From Wikiversity
Jump to: navigation, search
Created by mate2code.

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 ...    (OEIS A062383)

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

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 = OEIS A001317 = 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.


Contents

3 bit [edit]

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

Corresponding
Fano plane collineation		 Fanoperm124.svg Fanoperm364.svg Fanoperm524.svg Fanoperm764.svg
Compression vector
and
compression matrix		 124

[1,0,0;
0,1,0;
0,0,1]

 364

[1,0,0;
1,1,0;
0,1,1]

 524

[1,0,0;
0,1,0;
1,0,1]

 764

[1,0,0;
1,1,0;
1,1,1]
Permutation matrix

[1,0,0,0, 0,0,0,0;
0,1,0,0, 0,0,0,0;
0,0,1,0, 0,0,0,0;
0,0,0,1, 0,0,0,0;

0,0,0,0, 1,0,0,0;
0,0,0,0, 0,1,0,0;
0,0,0,0, 0,0,1,0;
0,0,0,0, 0,0,0,1]

[1,0,0,0, 0,0,0,0;
0,1,0,0, 0,0,0,0;
0,0,0,1, 0,0,0,0;
0,0,1,0, 0,0,0,0;

0,0,0,0, 0,0,1,0;
0,0,0,0, 0,0,0,1;
0,0,0,0, 0,1,0,0;
0,0,0,0, 1,0,0,0]

[1,0,0,0, 0,0,0,0;
0,1,0,0, 0,0,0,0;
0,0,1,0, 0,0,0,0;
0,0,0,1, 0,0,0,0;

0,0,0,0, 0,1,0,0;
0,0,0,0, 1,0,0,0;
0,0,0,0, 0,0,0,1;
0,0,0,0, 0,0,1,0]

[1,0,0,0, 0,0,0,0;
0,1,0,0, 0,0,0,0;
0,0,0,1, 0,0,0,0;
0,0,1,0, 0,0,0,0;

0,0,0,0, 0,0,0,1;
0,0,0,0, 0,0,1,0;
0,0,0,0, 1,0,0,0;
0,0,0,0, 0,1,0,0]

Compare: 3-bit Walsh permutation

4 bit [edit]

Cycle graph of the cyclic group Z4
    
The four permutations in a matrix (top left corner of OEIS A195467)

Below the dual matrix, showing the single Binary digits
The rightmost Binary matrix is the top left corner of OEIS A197819.
(see file description page)
The left columns of the compression matrices form the matrix

[1,1,1,1;
0,1,0,1;
0,0,1,1;
0,0,0,1]

 , which is the beginning of the Sierpinski triangle.
Cayley table of the cyclic group Z4

5 bit [edit]

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.
The PDF (fxtbook.pdf) is linked on the authors home page: http://www.jjj.de/fxt/#fxtbook


Infinite array [edit]

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

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

This table shows the first 216 = 65536 of these fractions: Table of fractions in OEIS A197819
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 = OEIS A001317.



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  )
Retrieved from "http://en.wikiversity.org/w/index.php?title=Gray_code_permutation_powers&oldid=927191"