# 3-bit Walsh permutation; conjugacy class 2+2

The elements in this conjugacy class are self-inverse and leave half of the elements fixed (i.e. there are two fixed points for one transposition).
The cardinality of this conjugacy class is determined by  A134057(n) = ${\binom {2^{n}-1}{2}}$. For n = 3 that is ${\binom {7}{2}}$ = 21, the number of 2-subsets of a 7-set.
The equations $a\oplus b~=~c$ show a bijection between the permutations and the 2-subsets of $\{1..7\}$.  ($\oplus$ is the bitwise XOR.) $\{a,b,c\}$ are the positive fixed points. $c$ is the XOR of the elements in any of the two cycles. The other two fixed points $\{a,b\}$ are one of the 21 subsets. E.g. 134 has the cycles (2, 3) and (6, 7). 2⊕3 = 6⊕7 = 1, which is one of the fixed points. The other two are {4, 5}, so this is the subset.
The pattern of fixed and moved points corresponds to the rows 1..7 of a Walsh matrix. Permutations with the same fixed points are in the same column.
Walsh matrix :
| 1 | 2 | 4 | 3 | 5 | 6 | 7 | 7 | 7 |
| $4\oplus 6~=~2$ | $1\oplus 5~=~4$ | $2\oplus 3~=~1$ | $4\oplus 7~=~3$ | $2\oplus 7~=~5$ | $1\oplus 7~=~6$ | Walsh matrix 0 1 2 3 4 5 6 7 0 1 134 125 135 2 324 126 326 3 214 127 217 4 524 164 564 5 174 421 471 6 724 142 742 7 654 623 153   $a\oplus b~=~c$   $\{0,a,b,c\}$ | Walsh matrix 0 1 2 3 4 5 6 7 0 1 134 125 135 2 324 126 326 3 214 127 217 4 524 164 564 5 174 421 471 6 724 142 742 7 654 623 153   $a\oplus b~=~c$   $\{0,a,b,c\}$ | Walsh matrix 0 1 2 3 4 5 6 7 0 1 134 125 135 2 324 126 326 3 214 127 217 4 524 164 564 5 174 421 471 6 724 142 742 7 654 623 153   $a\oplus b~=~c$   $\{0,a,b,c\}$ |
| Paris | Paris | Paris | London | London | London | | | Walsh matrix 0 1 2 3 4 5 6 7 0 1 134 125 135 2 324 126 326 3 214 127 217 4 524 164 564 5 174 421 471 6 724 142 742 7 654 623 153   $a\oplus b~=~c$   $\{0,a,b,c\}$ | Walsh matrix 0 1 2 3 4 5 6 7 0 1 134 125 135 2 324 126 326 3 214 127 217 4 524 164 564 5 174 421 471 6 724 142 742 7 654 623 153   $a\oplus b~=~c$   $\{0,a,b,c\}$ | Walsh matrix 0 1 2 3 4 5 6 7 0 1 134 125 135 2 324 126 326 3 214 127 217 4 524 164 564 5 174 421 471 6 724 142 742 7 654 623 153   $a\oplus b~=~c$   $\{0,a,b,c\}$ |
| $2\oplus 6~=~4$ | $4\oplus 5~=~1$ | $1\oplus 3~=~2$ | $3\oplus 7~=~4$ | $5\oplus 7~=~2$ | $6\oplus 7~=~1$ | Walsh matrix 0 1 2 3 4 5 6 7 0 1 134 125 135 2 324 126 326 3 214 127 217 4 524 164 564 5 174 421 471 6 724 142 742 7 654 623 153   $a\oplus b~=~c$   $\{0,a,b,c\}$ | Walsh matrix 0 1 2 3 4 5 6 7 0 1 134 125 135 2 324 126 326 3 214 127 217 4 524 164 564 5 174 421 471 6 724 142 742 7 654 623 153   $a\oplus b~=~c$   $\{0,a,b,c\}$ | Walsh matrix 0 1 2 3 4 5 6 7 0 1 134 125 135 2 324 126 326 3 214 127 217 4 524 164 564 5 174 421 471 6 724 142 742 7 654 623 153   $a\oplus b~=~c$   $\{0,a,b,c\}$ |
| Paris | Paris | Paris | Florence | Florence | Florence | | | Walsh matrix 0 1 2 3 4 5 6 7 0 1 134 125 135 2 324 126 326 3 214 127 217 4 524 164 564 5 174 421 471 6 724 142 742 7 654 623 153   $a\oplus b~=~c$   $\{0,a,b,c\}$ | Walsh matrix 0 1 2 3 4 5 6 7 0 1 134 125 135 2 324 126 326 3 214 127 217 4 524 164 564 5 174 421 471 6 724 142 742 7 654 623 153   $a\oplus b~=~c$   $\{0,a,b,c\}$ | Walsh matrix 0 1 2 3 4 5 6 7 0 1 134 125 135 2 324 126 326 3 214 127 217 4 524 164 564 5 174 421 471 6 724 142 742 7 654 623 153   $a\oplus b~=~c$   $\{0,a,b,c\}$ |
| $2\oplus 4~=~6$ | $1\oplus 4~=~5$ | $1\oplus 2~=~3$ | $3\oplus 4~=~7$ | $2\oplus 5~=~7$ | $1\oplus 6~=~7$ | $3\oplus 5~=~6$ | $3\oplus 6~=~5$ | $5\oplus 6~=~3$ |
| Rome | Rome | Rome | Hamburg | Hamburg | Hamburg | Berlin | Berlin | Berlin |
Above  A134057(n) has been expressed as a binomial, but it can also be expressed as a product $(2^{n-1}-1)\cdot (2^{n}-1)$.  (3 · 7 for n = 3) That is the number of 0s in positive rows and columns of a binary Walsh matrix. In the Walsh matrix shown above the positive rows correspond to $a\oplus b$, and the positive columns to the patterns of fixed points.
* conversion of the formula
* ${\binom {2^{n}-1}{2}}~=~{\frac {(2^{n}-1)!}{2\cdot (2^{n}-3)!}}~=~{\frac {(2^{n}-2)\cdot (2^{n}-1)}{2}}~=~{\frac {2^{2n}-2^{n}-2^{n+1}+2}{2}}~=~2^{2n-1}-2^{n-1}-2^{n}+1~=~(2^{n-1}-1)\cdot (2^{n}-1)$