# Problem involving permutation matrices from Michael Artin's book.

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.

-

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.

-
I don't understand completely. –  Enjoys Math Mar 2 '13 at 23:43
I chose the convention that (12) is a function and so (12)(14) is evaluated right to left. –  Enjoys Math Mar 2 '13 at 23:49
This doesn't make sense to me because if $P X$ is the permuted column vector then $P_{(12)}$ was the first perm applied but in the expression $(13)(14)(12)$, $(13)$ is applied first. It doesn't make sense. –  Enjoys Math Mar 3 '13 at 0:01
@EnjoysMath, sorry for not having reacted earlier, a matter of time zones. If you evaluate right-to-left then $p = (12)(14)(13) : 1 \mapsto 3 \mapsto 4 \mapsto 2 \mapsto 1$. But for matrices evaluating right-to-left means looking at the action on column vectors, and then $P : 1 \mapsto 2 \mapsto 4 \mapsto 3 \mapsto 1$. I believe it is a matter of doing everything consistently, either left-to-right or right-to-left. –  Andreas Caranti Mar 3 '13 at 9:45
@EnjoysMath, thanks a bunch! –  Andreas Caranti Mar 7 '13 at 12:03

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.

-
As a group theorist at heart, I feel compelled to respond. It is only natural to feel that the habits of others are silly (how funny are the languages other people speak). I encountered the problem that originated this post long ago, and I solved it (you guess) going the group-theoretic way: I compose permutations left-to-right (which fits with the way I read in my language), my vectors are row vectors, so matrices operate on the right, my conjugacy is $x \mapsto g^{-1} x g$, etc. But this is only my own private way of doing things, where consistency rules. [follows in next comment] –  Andreas Caranti Mar 6 '13 at 6:54
[follows from next comment] When I teach second-year Maths majors, though, I do everything consistently right-to-left. I need to watch myself at every step, lest my reflexes take me the wrong way, but otherwise the burden would be on them. I mention the problem, though. Later they can choose which kind of approach they prefer. One last thing. When I multiply a row vector $v$ by a matrix $A$, the matrix is on the right, of course, so we write $v A$. So it is only natural (at least to my group-theoretic mind) to write functions on the right, when one composes left-to-right. –  Andreas Caranti Mar 6 '13 at 7:03
@AndreasCaranti I didn't mean any offense by saying it seems silly to me - as you said, the habits of others sometimes seem funny. I know why you do it. (My conjugacy is the same way by the way.) –  Alexander Gruber Mar 6 '13 at 18:20

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.

-