Problem involving permutation matrices from Michael Artin's book.

Question

Let $p$ be the permutation $(3 4 2 1)$ of the four indices. The permutation matrix associated with it is $$ P = \begin{bmatrix} 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 \end{bmatrix} $$ This is the matrix that permutes the components of a column vector.

The problems asks you to decompose $p$ into transpositions and show that the associated matrix product equals the above matrix. However, I'm not getting that it does and I've run through it several times. Here are my calculations:

$p = (12)(14)(13)$

$$ P_{(12)} = \begin{bmatrix} 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}, P_{(14)} =\begin{bmatrix} 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 \end{bmatrix}, P_{(13)}=\begin{bmatrix} 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix} $$

However, $$P_{(12)} (P_{(14)} P_{(13)}) = \begin{bmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \end{bmatrix} \neq P$$

I don't see where I've made a mistake.

Answer 1

I think I found the issue. I was using the definition $PX = \begin{bmatrix} X_{p(1)}\\ X_{p(2)} \\ \vdots \\ X_{p(n)} \end{bmatrix} $ i.e. $P$ operates on $X$ by permuting the indices by $p$. However, the book defines $PX$ as $X_i$ gets sent to the position $p(i)$ in column vector $X$. These definitions are inverses of each other so that's somehow why my matrix multiplication was corrected by rearranging the matrices. Again, the proper definition of $P$ is $\sum_{i=1}^n e_{p(i), i}$ where $e_{i,j}$ is the matrix unit with $1$ at position $i,j$ and zero elsewhere.

Referring back to my first post, $P$ was defined using the incorrect definition, simply transposing $P$ will give us the proper $\sum_{i=1}^n e_{p(i), i}$ definition. Now the multiplication works out as it should.

Answer 2

The permutation is indeed $(1342)$, but this decomposes as $(13)(14)(12)$, so you should compute $$ P_{(13)} P_{(14)} P_{(12)} = \begin{bmatrix} 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix} \cdot \begin{bmatrix} 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 \end{bmatrix} \cdot \begin{bmatrix} 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix} = P. $$

You should compose both permutations and matrices consistently left-to-right.

Answer 3

The problem is that you are multiplying cycles from left to right, but matrices multiply from right to left.

Let's take this out of cycle notation for a second. $$(3421)=\left(\begin{array}{cccc}1&2&3&4\\3&1&4&2\end{array}\right)$$ You want to say that $$(3421)=(12)(14)(13).$$ If you are multiplying right to left, it works out like this. $$\begin{eqnarray*}(13)&=&\left(\begin{array}{cccc}1&2&3&4\\ \color{red}{3}&2&\color{red}{1}&4\end{array}\right)\\ (14)(13)&=&\left(\begin{array}{cccc}1&2&3&4\\\color{red}{4}&2&1&\color{red}{3}\end{array}\right)\\ (12)(14)(13)&=&\left(\begin{array}{cccc}1&2&3&4\\ \color{red}{2}&\color{red}{4}&1&3\end{array}\right)\end{eqnarray*}$$ That didn't work. Now let's try multiplying left to right. $$\begin{eqnarray*}(12)&=&\left(\begin{array}{cccc}1&2&3&4\\ \color{red}{2}&\color{red}{1}&3&4\end{array}\right)\\ (12)(14)&=&\left(\begin{array}{cccc}1&2&3&4\\ \color{red}{4}&1&3&\color{red}{2}\end{array}\right)\\ (12)(14)(13)&=&\left(\begin{array}{cccc}1&2&3&4\\ \color{red}{3}&1&\color{red}{4}&2\end{array}\right)\end{eqnarray*}$$

Now, there are competing conventions in group theory about whether to multiply permutations left to right or right to left. You've likely been taught to multiply them left to right; if so, you found the proper decomposition. In general, however, matrices are always multiplied right to left. So when you convert your transpositions to matrices and multiply them, you have to reverse their order. In fact,

$$\left( \begin{array}{cccc} 0 & 0 & \color{red}{1} & 0 \\ 0 & 1 & 0 & 0 \\ \color{red}{1} & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \end{array} \right)\left( \begin{array}{cccc} 0 & 0 & 0 & \color{red}{1} \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ \color{red}{1} & 0 & 0 & 0 \end{array} \right)\left( \begin{array}{cccc} 0 & \color{red}{1} & 0 & 0 \\ \color{red}{1} & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{array} \right)=\left( \begin{array}{cccc} 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 \end{array} \right)$$ So, to sum it all up, if you have matrices $P_a P_b$ associated with cycles $a$ and $b$, if you use the left to right convention of multiplying cycles, you'll want $P_{ab}=P_bP_a$; if you use the right to left convention, use $P_{ab}=P_aP_b$.

Remark. I should mention that some group theorists actually get so frustrated with this that they write all function composition in the left to right convention. Some even go as far as to write functions as $(x)f$, rather than $f(x)$, so that when they write $(x)fg$, it's clear that $f$ acts first, then $g$, whereas usually when we write $fg(x)$, we have that $g$ acts first, then $f$ (like with matrix multiplication). To me this seems kind of silly, but I must admit this consistency does fix issues like the one you were having.