View source for 3-bit Walsh permutation

<templatestyles src="3-bit Walsh permutation/style.css" />
__NOTOC__
{| align=right style="text-align=right; border:1px solid lightgray" cellspacing="10"
|-
|[[Walsh permutation]] [[File:Rdrup.svg|link=]]
|}

There are {{oeis|A002884}}(3) = <abbr title="(8-4) * (8-2) * (8-1)">4 * 6 * 7</abbr> = 168 {{w|invertible matrix|invertible}} binary 3×3 matrices.

They form the [[w:General linear group|general linear group]] GL(3,2).
<small>(As all non-zero determinants are 1 in the {{w|GF(2)|binary field}}, it is also the {{w|special linear group}}.)</small>

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

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

{{3-bit Walsh permutation/inverse nitpick}}

==Representations==

{{Collapsible START|overview|open followed wide}}
These images show the connection between the 3×3 matrices and the permutations:<br>
Each row of the 3×3 matrix can be interpreted as a number in <math>\{1..7\}</math>. The corresponding {{w|Walsh function}} (row of a Walsh matrix) is shown to its right.<br>
The columns of the resulting 3×8 matrix can be interpreted as a permutation of <math>(0..7)</math>.<br>
<small>(The small gray cube shows the result of applying the permutation. Reading it as a sequence corresponds to reading the permutation matrix by rows.)</small>
{|
| [[File:Walsh permutation 124.svg|thumb|200px|{{WalshPermCatLink|124}}]]
| [[File:Walsh permutation 471.svg|thumb|200px|{{WalshPermCatLink|471}}]]
| [[File:Walsh permutation 456.svg|thumb|200px|{{WalshPermCatLink|456}}]]
| [[File:Walsh permutation 316.svg|thumb|200px|{{WalshPermCatLink|316}}]]
| [[File:Walsh permutation 341.svg|thumb|200px|{{WalshPermCatLink|341}}]]
|}
{{Collapsible END}}

{{Collapsible START|permuted Walsh matrices |collapsed followed wide}}
These images show why the author chose the term ''Walsh permutation''.<br>
A permutation is ''Walsh'' iff applying it to the columns of a {{w|Walsh matrix}} creates a matrix that can also be described as a Walsh matrix with permuted rows.
{|
| [[File:Walsh permutation 124 Walsh.svg|thumb|200px]]
| [[File:Walsh permutation 471 Walsh.svg|thumb|200px]]
| [[File:Walsh permutation 456 Walsh.svg|thumb|200px]]
| [[File:Walsh permutation 316 Walsh.svg|thumb|200px]]
| [[File:Walsh permutation 341 Walsh.svg|thumb|200px]]
|}
{{Collapsible END}}

{{Collapsible START|transformations (letter compound)|collapsed followed wide}}
Here the binary 3×3 matrices are used as transformation matrices.
A list of these files can be found [[3-bit Walsh permutation/matrix columns|'''here''']].
{|
| [[File:Walsh permutation 124 JF.png|thumb|200px]]
| [[File:Walsh permutation 471 JF.png|thumb|200px]]
| [[File:Walsh permutation 456 JF.png|thumb|200px]]
| [[File:Walsh permutation 316 JF.png|thumb|200px]]
| [[File:Walsh permutation 341 JF.png|thumb|200px]]
|}
{{Collapsible START|as inverses|collapsed light wide}}
These are transforms with inverses of binary matrices, which contain some negative 1s.
A list of these files can be found [[3-bit Walsh permutation/matrix columns/inverses|'''here''']].
{|
| [[File:Walsh permutation 124 JF as inverse.png|thumb|200px]]
| [[File:Walsh permutation 471 JF as inverse.png|thumb|200px]]
| [[File:Walsh permutation 456 JF as inverse.png|thumb|200px]]
| [[File:Walsh permutation 316 JF as inverse.png|thumb|200px]]
| [[File:Walsh permutation 341 JF as inverse.png|thumb|200px]]
|}
{{Collapsible END}}
{{Collapsible END}}

{{Collapsible START|transformations (colored cube)|collapsed followed wide}}
These images show the connection between transforms and permutations:<br>
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.<br>
<small>
[[:File:Walsh 316 transform 110 101 001.png|'''This''']] file shows essentially the same as [[:File:Walsh permutation 316 RGB.png|'''this''']] one (shown below), but the colored small vertices make it clearer how it corresponds to [[:File:Walsh permutation 316 balls.png|'''this''']].<br>
(This is the result of applying the permutation. It corresponds to the gray cube in the overview files above.)
</small>

{|
| [[File:Walsh permutation 124 RGB.png|thumb|200px]]
| [[File:Walsh permutation 471 RGB.png|thumb|200px]]
| [[File:Walsh permutation 456 RGB.png|thumb|200px]]
| [[File:Walsh permutation 316 RGB.png|thumb|200px]]
| [[File:Walsh permutation 341 RGB.png|thumb|200px]]
|}
{{Collapsible START|as inverses|collapsed light wide}}
{|
| [[File:Walsh permutation 124 RGB as inverse.png|thumb|200px]]
| [[File:Walsh permutation 471 RGB as inverse.png|thumb|200px]]
| [[File:Walsh permutation 456 RGB as inverse.png|thumb|200px]]
| [[File:Walsh permutation 316 RGB as inverse.png|thumb|200px]]
| [[File:Walsh permutation 341 RGB as inverse.png|thumb|200px]]
|}
{{Collapsible END}}
{{Collapsible END}}

{{Collapsible START|cube with RGB vertices and complement patterns|collapsed wide}}
The colors are in the same vertices of the gray cube as in the transform images above.<br>
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 <small>(in the first box above)</small>.<br>
Complementary vertices are connected by brown edges. The patterns are numbered 1..7.
{|
| [[File:Walsh permutation 124 balls.png|thumb|200px|[[c:Category:Single 3-bit Walsh permutations; RGB balls; complement pattern 7|7]]]]
| [[File:Walsh permutation 471 balls.png|thumb|200px|[[c:Category:Single 3-bit Walsh permutations; RGB balls; complement pattern 2|2]]]]
| [[File:Walsh permutation 456 balls.png|thumb|200px|[[c:Category:Single 3-bit Walsh permutations; RGB balls; complement pattern 7|7]]]]
| [[File:Walsh permutation 316 balls.png|thumb|200px|[[c:Category:Single 3-bit Walsh permutations; RGB balls; complement pattern 4|4]]]]
| [[File:Walsh permutation 341 balls.png|thumb|200px|[[c:Category:Single 3-bit Walsh permutations; RGB balls; complement pattern 6|6]]]]
|}
{{Collapsible END}}

==Conjugacy classes==

The group has {{oeis|A006951}}(3) = 6 {{w|conjugacy classes}}. They almost correspond to the {{w|Cycles and fixed points|cycle type}},<br>
but there are two different conjugacy classes with 7-cycles.
(For the distinction between them, see [[commons:Category:Related sets of 3-bit Walsh permutations; heptagon|'''here''']].)

The permutations in 2+2 are self-inverse, and their fixed points correspond to Walsh functions. They can be found [[3-bit Walsh permutation; conjugacy class 2+2|'''here''']]. 

{{3-bit Walsh permutation/examples}}

The 3×3 matrices in the same conjugacy class are {{w|Matrix similarity|similar}}.

{{3-bit Walsh permutation/matrix similarity}}

==Cycle shapes {{anchor|Fano plane collineations}}==

In a symmetric representation like the Fano plane, there are 33 different cycle shapes (or 24 if the direction is ignored).<br>
A complete list can be found [[3-bit Walsh permutation/cycle shapes|'''here''']].
<small>They are denoted by city names, followed by a qualifier of the direction, where needed.</small>

{{Collapsible START|triangle {{FanoCycleShapeLink|Berlin}}|collapsed followed wide}}
{{FanoPatternArrowsTriangleBerlin}}
{{Collapsible END}}
{{Collapsible START|hexagon {{FanoCycleShapeLink|Shanghai}}|open followed wide}}
{{FanoPatternArrowsHexagonShanghai}}
{{Collapsible END}}
{{Collapsible START|triangles {{FanoCycleShapeLink|Santiago}} + and −|collapsed followed wide}}
Inverse 3×3 matrices differ in their determinant. Those in the inner triangle have 1, and those in the outer have −1.
{{FanoPatternArrowsDoubleTriangleSantiago}}
{{Collapsible END}}
{{Collapsible START|hexagons {{FanoCycleShapeLink|Buenos Aires}} 5 and 6|collapsed wide}}
Inverse 3×3 matrices differ in their number of ones. Those in the inner hexagon have 5, and those in the outer have 6.
{{FanoPatternArrowsDoubleHexagonBuenosAires}}
{{Collapsible END}}

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

This is a refinement of {{w|matrix similarity}}, where <math>P</math> is allowed to be any element of the group.
<small>(Cycle shapes are a refinement of {{w|conjugacy class}}es.)</small>

==Powers and cycle graph==

The {{w|Cycle graph (algebra)|cycle graph}} of this group has 28 triangles, 21 squares and 8 heptagons.

Each of the following rows is an example of a cycle.
<small>(Each one is closed by the [[commons:Category:Related images of Walsh permutation 124|neutral element]], which is not shown.)</small><br>
It shows consecutive {{w|Exponentiation|powers}} of the first element from left to right.
<small>(Also of the last element from right to left.)</small><br>
Elements in symmetric positions are inverse to each other.

===Triangles===

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

{{Collapsible START|{{FanoCycleShapeLink|Delhi}}|collapsed wide}}
{| class="collineations border"
|- 
| {{FanoColl|4|3|5}}
| {{FanoColl|5|7|1}}
|-
| ''Delhi'' 5
| ''Delhi'' 6
|}
{{Collapsible END}}

===Squares===

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

{{Collapsible START|{{FanoCycleShapeLink|Toronto}}, {{FanoCycleShapeLink|Rome}}|open followed wide}}
{| class="collineations border"
|- 
| {{FanoColl|4|3|1}}
| {{FanoColl|1|7|4}}
| {{FanoColl|4|6|1}}
|-
| ''Toronto''
| ''Rome''
| ''Toronto''
|}
{{Collapsible END}}
{{Collapsible START|{{FanoCycleShapeLink|Montreal}}, {{FanoCycleShapeLink|Florence}}|collapsed followed wide}}
{| class="collineations border"
|- 
| {{FanoColl|6|2|1}}
| {{FanoColl|3|2|6}}
| {{FanoColl|4|2|3}}
|-
| ''Montreal''
| ''Florence''
| ''Montreal''
|}
{{Collapsible END}}
{{Collapsible START|{{FanoCycleShapeLink|New York}}, {{FanoCycleShapeLink|Berlin}}|collapsed followed wide}}
{| class="collineations border"
|- 
| {{FanoColl|2|4|7}}
| {{FanoColl|4|7|1}}
| {{FanoColl|7|1|2}}
|-
| ''New York''
| ''Berlin''
| ''New York''
|}
{{Collapsible END}}
{{Collapsible START|{{FanoCycleShapeLink|San Francisco}}, {{FanoCycleShapeLink|Hamburg}}|collapsed followed wide}}
{| class="collineations border"
|- 
| {{FanoColl|4|5|6}}
| {{FanoColl|6|2|3}}
| {{FanoColl|3|5|1}}
|-
| ''San Francisco''
| ''Hamburg''
| ''San Francisco''
|}
{{Collapsible END}}
{{Collapsible START|{{FanoCycleShapeLink|Buenos Aires}}, {{FanoCycleShapeLink|Paris}}|collapsed followed wide}}
{| class="collineations border"
|- 
| {{FanoColl|1|3|6}}
| {{FanoColl|1|2|5}}
| {{FanoColl|1|3|7}}
|-
| ''Buenos Aires'' 5
| ''Paris''
| ''Buenos Aires'' 6
|}
{{Collapsible END}}
{{Collapsible START|{{FanoCycleShapeLink|Santiago}}, {{FanoCycleShapeLink|London}}|collapsed wide}}
{| class="collineations border"
|- 
| {{FanoColl|6|7|3}}
| {{FanoColl|4|2|1}}
| {{FanoColl|3|7|6}}
|-
| ''Santiago'' +
| ''London''
| ''Santiago'' −
|}
{{Collapsible END}}

===Heptagons===

{{Collapsible START|{{FanoCycleShapeLink|Cape Town}}|collapsed followed wide}}
{| class="collineations border"
|- 
| {{FanoColl|4|6|3}}
| {{FanoColl|3|5|2}}
| {{FanoColl|2|7|6}}
| {{FanoColl|6|1|5}}
| {{FanoColl|5|4|7}}
| {{FanoColl|7|3|1}}
|-
| ''Cape Town'' a
| ''Cape Town'' a
| ''Cape Town'' b
| ''Cape Town'' a
| ''Cape Town'' b
| ''Cape Town'' b
|}
{{Collapsible END}}
{{Collapsible START|{{FanoCycleShapeLink|Cairo}}, {{FanoCycleShapeLink|Alexandria}}, {{FanoCycleShapeLink|Tripoli}}|open followed wide}}
{| class="collineations border"
|- 
| {{FanoColl|4|1|3}}
| {{FanoColl|3|4|5}}
| {{FanoColl|5|3|7}}
| {{FanoColl|7|5|6}}
| {{FanoColl|6|7|2}}
| {{FanoColl|2|6|1}}
|-
| ''Cairo'' b
| ''Alexandria'' b
| ''Tripoli'' a
| ''Tripoli'' b
| ''Alexandria'' a
| ''Cairo'' a
|}
{{Collapsible END}}
{{Collapsible START|''Alexandria'', ''Tripoli'', ''Cairo''|collapsed followed wide}}
{| class="collineations border"
|- 
| {{FanoColl|7|1|3}}
| {{FanoColl|5|7|6}}
| {{FanoColl|4|5|2}}
| {{FanoColl|3|4|1}}
| {{FanoColl|6|3|7}}
| {{FanoColl|2|6|5}}
|-
| ''Alexandria'' a
| ''Tripoli'' a
| ''Cairo'' b
| ''Cairo'' a
| ''Tripoli'' b
| ''Alexandria'' b
|}
{{Collapsible END}}
{{Collapsible START|''Tripoli'', ''Cairo'', ''Alexandria''|collapsed wide}}
{| class="collineations border"
|- 
| {{FanoColl|7|6|3}}
| {{FanoColl|2|5|1}}
| {{FanoColl|6|4|7}}
| {{FanoColl|5|3|2}}
| {{FanoColl|4|1|6}}
| {{FanoColl|3|7|5}}
|-
| ''Tripoli'' b
| ''Cairo'' b
| ''Alexandria'' a
| ''Alexandria'' b
| ''Cairo'' a
| ''Tripoli'' a
|}
{{Collapsible END}}


[[Category:Walsh permutation]]