3-bit Walsh permutation

From Wikiversity
Jump to navigation Jump to search
Walsh permutation Rdrup.svg
Fano plane with nimber labels

There are Sloane'sA002884(3) = 4 * 6 * 7 = 168 invertible binary 3×3 matrices.

They form the general linear group GL(3,2). (As all non-zero determinants are 1 in the binary field, it is also the special linear group.)

It is isomorphic to the projective special linear group PSL(2,7), the symmetry group of the Fano plane.

Each of these maps corresponds to a permutation of seven elements, which can be seen as a collineation of the Fano plane.


Conjugacy classes[edit | edit source]

The group has six conjugacy classes. They almost correspond to the cycle type,
but there are two different conjugacy classes with 7-cycles. (For the distinction between them, see here.)

description neutral 2+2 2+4 3+3 7a 7b
size 1 21 42 56 24 24
examples

Walsh permutation 124 Fano.svg

Walsh permutation 421 Fano.svg


bit-reversal

Walsh permutation 136 Fano.svg


Gray code

Walsh permutation 241 Fano.svg

Walsh permutation 765 Fano.svg

Walsh permutation 357 Fano.svg

Walsh permutation 623 Fano.svg

Walsh permutation 247 Fano.svg

Walsh permutation 517 Fano.svg

Walsh permutation 512 Fano.svg

Walsh permutation 243 Fano.svg

The 3×3 matrices in the same conjugacy class are similar.


Cycle shapes[edit | edit source]

In a symmetric representation like the Fano plane, there are 33 different cycle shapes (or 24 if the direction is ignored).
A complete list can be found here. They are denoted by city names, followed by a qualifier of the direction, where needed.

hexagon Shanghai

Walsh permutation 236 Fano.svg

Walsh permutation 362 Fano.svg

Walsh permutation 315 Fano.svg

Walsh permutation 546 Fano.svg

Walsh permutation 531 Fano.svg

Walsh permutation 465 Fano.svg



and have the same cycle shape, if there is a from the symmetric subgroup, so that . (The 3×3 matrix of is a permutation matrix.)

This is a refinement of matrix similarity, where is allowed to be any element of the group. (Cycle shapes are a refinement of conjugacy classes.)

Powers and cycle graph[edit | edit source]

The cycle graph of this group has 28 triangles, 21 squares and 8 heptagons.

Each of the following rows is an example of a cycle. (Each one is closed by the neutral element, which is not shown.)
It shows consecutive powers of the first element from left to right. (Also of the last element from right to left.)
Elements in symmetric positions are inverse to each other.

Triangles[edit | edit source]

Each of the 28 triangles contains two inverse permutations of cycle type 3+3.


Squares[edit | edit source]

This shows why there are two permutations of cycle type 2+4 for each one with 2+2.

Toronto, Rome

Walsh permutation 461 Fano.svg

Walsh permutation 174 Fano.svg

Walsh permutation 431 Fano.svg

Toronto Rome Toronto


Heptagons[edit | edit source]

Cairo, Alexandria, Kinshasa

Walsh permutation 413 Fano.svg

Walsh permutation 345 Fano.svg

Walsh permutation 537 Fano.svg

Walsh permutation 756 Fano.svg

Walsh permutation 672 Fano.svg

Walsh permutation 261 Fano.svg

Cairo b Alexandria b Kinshasa a Kinshasa b Alexandria a Cairo a