# Walsh permutation; bit permutation; calc

Finite permutations p and corresponding bit permutations P are composed in opposite directions:

${\displaystyle p_{a}*p_{b}*...=p_{x}~~~~\Leftrightarrow ~~~~...*P_{b}*P_{a}=P_{x}}$

## p1 * p8

${\displaystyle p_{1}*p_{8}=p_{9}~~~~\Leftrightarrow ~~~~P_{8}*P_{1}=P_{9}}$

```p1 = [0 1 0 0;
1 0 0 0;
0 0 1 0;
0 0 0 1];
p1 * [1:4]'
ans =
2
1
3
4

p8 = [1 0 0 0;
0 0 0 1;
0 1 0 0;
0 0 1 0];
p8 * [1:4]'
ans =
1
4
2
3

p1 * p8 * [1:4]'
ans =
4
1
2
3
%      The result is p9.
%      p1 after p8 = p9

P1 = [1 0 0 0  0 0 0 0  0 0 0 0  0 0 0 0;
0 0 1 0  0 0 0 0  0 0 0 0  0 0 0 0;
0 1 0 0  0 0 0 0  0 0 0 0  0 0 0 0;
0 0 0 1  0 0 0 0  0 0 0 0  0 0 0 0;
0 0 0 0  1 0 0 0  0 0 0 0  0 0 0 0;
0 0 0 0  0 0 1 0  0 0 0 0  0 0 0 0;
0 0 0 0  0 1 0 0  0 0 0 0  0 0 0 0;
0 0 0 0  0 0 0 1  0 0 0 0  0 0 0 0;
0 0 0 0  0 0 0 0  1 0 0 0  0 0 0 0;
0 0 0 0  0 0 0 0  0 0 1 0  0 0 0 0;
0 0 0 0  0 0 0 0  0 1 0 0  0 0 0 0;
0 0 0 0  0 0 0 0  0 0 0 1  0 0 0 0;
0 0 0 0  0 0 0 0  0 0 0 0  1 0 0 0;
0 0 0 0  0 0 0 0  0 0 0 0  0 0 1 0;
0 0 0 0  0 0 0 0  0 0 0 0  0 1 0 0;
0 0 0 0  0 0 0 0  0 0 0 0  0 0 0 1];
P1 * [0:15]'
ans =
0
2
1
3
4
6
5
7
8
10
9
11
12
14
13
15

P8 = [1 0 0 0  0 0 0 0  0 0 0 0  0 0 0 0;
0 1 0 0  0 0 0 0  0 0 0 0  0 0 0 0;
0 0 0 0  1 0 0 0  0 0 0 0  0 0 0 0;
0 0 0 0  0 1 0 0  0 0 0 0  0 0 0 0;
0 0 0 0  0 0 0 0  1 0 0 0  0 0 0 0;
0 0 0 0  0 0 0 0  0 1 0 0  0 0 0 0;
0 0 0 0  0 0 0 0  0 0 0 0  1 0 0 0;
0 0 0 0  0 0 0 0  0 0 0 0  0 1 0 0;
0 0 1 0  0 0 0 0  0 0 0 0  0 0 0 0;
0 0 0 1  0 0 0 0  0 0 0 0  0 0 0 0;
0 0 0 0  0 0 1 0  0 0 0 0  0 0 0 0;
0 0 0 0  0 0 0 1  0 0 0 0  0 0 0 0;
0 0 0 0  0 0 0 0  0 0 1 0  0 0 0 0;
0 0 0 0  0 0 0 0  0 0 0 1  0 0 0 0;
0 0 0 0  0 0 0 0  0 0 0 0  0 0 1 0;
0 0 0 0  0 0 0 0  0 0 0 0  0 0 0 1];
P8 * [0:15]'
ans =
0
1
4
5
8
9
12
13
2
3
6
7
10
11
14
15

P1 * P8 * [0:15]'
ans =
0
4
1
5
8
12
9
13
2
6
3
7
10
14
11
15
%      The result is not P9 but P10, the inverse permutation of P9.
%      The row permutation matrices of the big permutations have to be multiplied like column permutation matrices from right to left
%      to get the result corresponding to the small permutations:
P8 * P1 * [0:15]'
ans =
0
2
4
6
8
10
12
14
1
3
5
7
9
11
13
15
%      The result is P9.
%      P1 before P8 = P9
```

## p1 * p3 * p8

${\displaystyle p_{1}*p_{3}*p_{8}=p_{6}~~~~\Leftrightarrow ~~~~P_{8}*P_{3}*P_{1}=P_{6}}$

```p1 = [0 1 0 0;
1 0 0 0;
0 0 1 0;
0 0 0 1];

p3 = [0 0 1 0;
1 0 0 0;
0 1 0 0;
0 0 0 1];

p8 = [1 0 0 0;
0 0 0 1;
0 1 0 0;
0 0 1 0];

P1 = [1 0 0 0  0 0 0 0  0 0 0 0  0 0 0 0;
0 0 1 0  0 0 0 0  0 0 0 0  0 0 0 0;
0 1 0 0  0 0 0 0  0 0 0 0  0 0 0 0;
0 0 0 1  0 0 0 0  0 0 0 0  0 0 0 0;
0 0 0 0  1 0 0 0  0 0 0 0  0 0 0 0;
0 0 0 0  0 0 1 0  0 0 0 0  0 0 0 0;
0 0 0 0  0 1 0 0  0 0 0 0  0 0 0 0;
0 0 0 0  0 0 0 1  0 0 0 0  0 0 0 0;
0 0 0 0  0 0 0 0  1 0 0 0  0 0 0 0;
0 0 0 0  0 0 0 0  0 0 1 0  0 0 0 0;
0 0 0 0  0 0 0 0  0 1 0 0  0 0 0 0;
0 0 0 0  0 0 0 0  0 0 0 1  0 0 0 0;
0 0 0 0  0 0 0 0  0 0 0 0  1 0 0 0;
0 0 0 0  0 0 0 0  0 0 0 0  0 0 1 0;
0 0 0 0  0 0 0 0  0 0 0 0  0 1 0 0;
0 0 0 0  0 0 0 0  0 0 0 0  0 0 0 1];

P3 = [1 0 0 0  0 0 0 0  0 0 0 0  0 0 0 0;
0 0 1 0  0 0 0 0  0 0 0 0  0 0 0 0;
0 0 0 0  1 0 0 0  0 0 0 0  0 0 0 0;
0 0 0 0  0 0 1 0  0 0 0 0  0 0 0 0;
0 1 0 0  0 0 0 0  0 0 0 0  0 0 0 0;
0 0 0 1  0 0 0 0  0 0 0 0  0 0 0 0;
0 0 0 0  0 1 0 0  0 0 0 0  0 0 0 0;
0 0 0 0  0 0 0 1  0 0 0 0  0 0 0 0;
0 0 0 0  0 0 0 0  1 0 0 0  0 0 0 0;
0 0 0 0  0 0 0 0  0 0 1 0  0 0 0 0;
0 0 0 0  0 0 0 0  0 0 0 0  1 0 0 0;
0 0 0 0  0 0 0 0  0 0 0 0  0 0 1 0;
0 0 0 0  0 0 0 0  0 1 0 0  0 0 0 0;
0 0 0 0  0 0 0 0  0 0 0 1  0 0 0 0;
0 0 0 0  0 0 0 0  0 0 0 0  0 1 0 0;
0 0 0 0  0 0 0 0  0 0 0 0  0 0 0 1];

P8 = [1 0 0 0  0 0 0 0  0 0 0 0  0 0 0 0;
0 1 0 0  0 0 0 0  0 0 0 0  0 0 0 0;
0 0 0 0  1 0 0 0  0 0 0 0  0 0 0 0;
0 0 0 0  0 1 0 0  0 0 0 0  0 0 0 0;
0 0 0 0  0 0 0 0  1 0 0 0  0 0 0 0;
0 0 0 0  0 0 0 0  0 1 0 0  0 0 0 0;
0 0 0 0  0 0 0 0  0 0 0 0  1 0 0 0;
0 0 0 0  0 0 0 0  0 0 0 0  0 1 0 0;
0 0 1 0  0 0 0 0  0 0 0 0  0 0 0 0;
0 0 0 1  0 0 0 0  0 0 0 0  0 0 0 0;
0 0 0 0  0 0 1 0  0 0 0 0  0 0 0 0;
0 0 0 0  0 0 0 1  0 0 0 0  0 0 0 0;
0 0 0 0  0 0 0 0  0 0 1 0  0 0 0 0;
0 0 0 0  0 0 0 0  0 0 0 1  0 0 0 0;
0 0 0 0  0 0 0 0  0 0 0 0  0 0 1 0;
0 0 0 0  0 0 0 0  0 0 0 0  0 0 0 1];

p1 * p3 * p8 * [1:4]'
ans =
1
2
4
3
%      The result is p6.
%      p1 after p3 after p8 = p6

P8 * P3 * P1 * [0:15]'
ans =
0
1
2
3
8
9
10
11
4
5
6
7
12
13
14
15
%      The result is P6.
%      P1 before P3 before P8 = P6
```

## p8 * p3 * p1

${\displaystyle p_{8}*p_{3}*p_{1}=p_{22}~~~~\Leftrightarrow ~~~~P_{1}*P_{3}*P_{8}=P_{22}}$

```p8 * p3 * p1 * [1:4]'
ans =
3
4
2
1
%      The result is p22.
%      p8 after p3 after p1 = p22

P1 * P3 * P8 * [0:15]'
ans =
0
8
4
12
1
9
5
13
2
10
6
14
3
11
7
15
%      The result is P22.
%      P8 before P3 before P1 = P22
```