Walsh permutation; nimber multiplication; patterns

From Wikiversity
Jump to navigation Jump to search
Walsh permutation; nimber multiplication

In the multiplication table of 4-bit nimbers five Walsh permutations of the binary Walsh matrix of order 16 can be found.
One matrix is found, when the dark fields (with odd binary digit sum) in the multiplication table are seen as binary ones. The other four matrices are shown below the multiplication table.


The binary digit sum of dark gray fields in the multiplication table is odd, for light gray fields it's even.
The dual matrix below shows the single bits of the entries.
wp(15, 5,11,13)

1 fixed point and 1 15-cycle
Sequence:
(0,15,5,10,  11,4,14,1,  13,2,8,7,   6,9,3,12)
Inversion vector:
(0,0,1,1,  1,4,1,6,  2,7,5,6,  7,5,11,3)
Inversion number: 60
wp( 8,12,10,15)

4 fixed points and 4 3-cycles
Sequence:
(0,8,12,4,  10,2,6,14,  15,7,3,11,  5,13,9,1)
Inversion vector:
(0,0,0,2,  1,4,3,0,  0,5,8,3,  8,2,6,14)
Inversion number: 56
wp( 4, 8, 5,10)

1 fixed point and 5 3-cycles
Sequence:
(0,4,8,12,  5,1,13,9,  10,14,2,6,  15,11,7,3)
Inversion vector:
(0,0,0,0,  2,4,0,2,  2,0,8,6,  0,4,8,12)
Inversion number: 48
wp( 2, 3,12, 4)

1 fixed point and 5 3-cycles
Sequence:
(0,2,3,1,  12,14,15,13,  4,6,7,5,  8,10,11,9)
Inversion vector:
(0,0,0,2,  0,0,0,2,  4,4,4,6,  4,4,4,6)
Inversion number: 40
wp( 1, 2, 8,12)

4 fixed points and 4 3-cycles
Sequence:
(0,1,2,3,  8,9,10,11,  12,13,14,15,  4,5,6,7)
Inversion vector:
(0,0,0,0,  0,0,0,0,  0,0,0,0,  8,8,8,8)
Inversion number: 32



Natural and sequency ordered Walsh matrix
wp( 1,14, 4, 8) permutes the s.o.W.m. in the left small matrix.

It is remarkable that the left one of the small matrices under the multiplication table resembles the sequency ordered Walsh matrix while the right one resembles the natural ordered W.m.

The four permutations that permute the s.o.W.m. in the four small matrices may deserve a closer look:

wp( 1,14, 4, 8), wp( 3, 9,12, 4), wp( 9,13, 1, 2), wp( 7,11, 3, 1). The bitxor is wp(12, 1,10,15).


wp(129,2,6,10,30,34,102,170) permutes the s.o.W.m. of order 256 into element 7 of the respective dual matrix.
This permutation is also self-inverse, and has 32 fixed points. This is its compression matrix:

1  0  0  0  0  0  0  0
0  1  1  1  1  1  1  1
0  0  1  0  1  0  1  0
0  0  0  1  1  0  0  1
0  0  0  0  1  0  0  0
0  0  0  0  0  1  1  1
0  0  0  0  0  0  1  0
1  0  0  0  0  0  0  1