3-bit Walsh permutation

Walsh permutation

There are Template:Oeis(3) = 4 * 6 * 7 = 168 Template:W binary 3×3 matrices.

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

It is isomorphic to the Template:W Template:W, the symmetry group of the Template:W.

Each of these maps corresponds to a permutation of seven elements, which can be seen as a Template:W of the Template:W.

Representations

Template:Collapsible START These images show the connection between the 3×3 matrices and the permutations:
Each row of the 3×3 matrix can be interpreted as a number in $\{1..7\}$. The corresponding Template:W (row of a Walsh matrix) is shown to its right.
The columns of the resulting 3×8 matrix can be interpreted as a permutation of $(0..7)$.
(The small gray cube shows the result of applying the permutation. Reading it as a sequence corresponds to reading the permutation matrix by rows.)

Template:WalshPermCatLink

Template:WalshPermCatLink

Template:WalshPermCatLink

Template:WalshPermCatLink

Template:WalshPermCatLink

Template:Collapsible START These images show why the author chose the term Walsh permutation.
A permutation is Walsh iff applying it to the columns of a Template:W creates a matrix that can also be described as a Walsh matrix with permuted rows.

Error creating thumbnail:

Template:Collapsible START Here the binary 3×3 matrices are used as transformation matrices. A list of these files can be found here.

File:Walsh permutation 124 JF.png

Error creating thumbnail:

File:Walsh permutation 316 JF.png

File:Walsh permutation 341 JF.png

Template:Collapsible START These are transforms with inverses of binary matrices, which contain some negative 1s. A list of these files can be found here.

Error creating thumbnail:

File:Walsh permutation 471 JF as inverse.png

File:Walsh permutation 316 JF as inverse.png

Template:Collapsible START These images show the connection between transforms and permutations:
The vertices of the periodic gray cubes have values from 0 to 7, and the transformation moves each vertex of the colored cube to some vertex in some gray cube.
This file shows essentially the same as this one (shown below), but the colored small vertices make it clearer how it corresponds to this.
(This is the result of applying the permutation. It corresponds to the gray cube in the overview files above.)

File:Walsh permutation 124 RGB.png

Error creating thumbnail:

File:Walsh permutation 316 RGB.png

File:Walsh permutation 124 RGB as inverse.png

File:Walsh permutation 316 RGB as inverse.png

Template:Collapsible START The colors are in the same vertices of the gray cube as in the transform images above.
This is the result of applying the permutation. The number values of the colors are like those in the gray cubes in the overview files (in the first box above).
Complementary vertices are connected by brown edges. The patterns are numbered 1..7.

File:Walsh permutation 124 balls.png 7

2

7

File:Walsh permutation 316 balls.png 4

6

Conjugacy classes

The group has Template:Oeis(3) = 6 Template:W. They almost correspond to the Template:W,
but there are two different conjugacy classes with 7-cycles. (For the distinction between them, see here.)

The permutations in 2+2 are self-inverse, and their fixed points correspond to Walsh functions. They can be found here.

The 3×3 matrices in the same conjugacy class are Template:W.

Cycle shapes Template:Anchor

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.

Template:Collapsible START Template:FanoPatternArrowsTriangleBerlin Template:Collapsible END Template:Collapsible START Template:FanoPatternArrowsHexagonShanghai Template:Collapsible END Template:Collapsible START Inverse 3×3 matrices differ in their determinant. Those in the inner triangle have 1, and those in the outer have −1. Template:FanoPatternArrowsDoubleTriangleSantiago Template:Collapsible END Template:Collapsible START Inverse 3×3 matrices differ in their number of ones. Those in the inner hexagon have 5, and those in the outer have 6. Template:FanoPatternArrowsDoubleHexagonBuenosAires Template:Collapsible END

$A$ and $B$ have the same cycle shape, if there is a $P$ from the symmetric subgroup, so that $B=P^{-1}AP$. (The 3×3 matrix of $P$ is a permutation matrix.)

This is a refinement of Template:W, where $P$ is allowed to be any element of the group. (Cycle shapes are a refinement of Template:Wes.)

Powers and cycle graph

The Template:W 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 Template:W 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

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

Template:FanoColl	Template:FanoColl
Delhi 5	Delhi 6

Squares

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

Template:FanoColl	Template:FanoColl	Template:FanoColl
Toronto	Rome	Toronto

Template:FanoColl	Template:FanoColl	Template:FanoColl
Montreal	Florence	Montreal

Template:FanoColl	Template:FanoColl	Template:FanoColl
New York	Berlin	New York

Template:FanoColl	Template:FanoColl	Template:FanoColl
San Francisco	Hamburg	San Francisco

Template:FanoColl	Template:FanoColl	Template:FanoColl
Buenos Aires 5	Paris	Buenos Aires 6

Template:FanoColl	Template:FanoColl	Template:FanoColl
Santiago +	London	Santiago −

Heptagons

Template:FanoColl	Template:FanoColl	Template:FanoColl	Template:FanoColl	Template:FanoColl	Template:FanoColl
Cape Town a	Cape Town a	Cape Town b	Cape Town a	Cape Town b	Cape Town b

Template:FanoColl	Template:FanoColl	Template:FanoColl	Template:FanoColl	Template:FanoColl	Template:FanoColl
Cairo b	Alexandria b	Tripoli a	Tripoli b	Alexandria a	Cairo a

Template:FanoColl	Template:FanoColl	Template:FanoColl	Template:FanoColl	Template:FanoColl	Template:FanoColl
Alexandria a	Tripoli a	Cairo b	Cairo a	Tripoli b	Alexandria b

Template:FanoColl	Template:FanoColl	Template:FanoColl	Template:FanoColl	Template:FanoColl	Template:FanoColl
Tripoli b	Cairo b	Alexandria a	Alexandria b	Cairo a	Tripoli a