Walsh permutation; bit permutation; calc

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

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

p₁ * p₈Edit

$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

p₁ * p₃ * p₈Edit

$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

p₈ * p₃ * p₁Edit

$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

Walsh permutation; bit permutation; calc

p1 * p8Edit

p1 * p3 * p8Edit

p8 * p3 * p1Edit

p₁ * p₈Edit

p₁ * p₃ * p₈Edit

p₈ * p₃ * p₁Edit