One can associate an $n \times n$ matrix $M_\sigma$ with a permutation $\sigma \in S_n$ by letting the entry at $(i, \sigma(i))$ be $1$ and letting all other entries be $0$. For example, the matrix corresponding to the permutation$$\sigma = \begin{pmatrix} 1&2&3\\3&1&2\end{pmatrix} \in S_3$$would be$$M_\sigma = \begin{pmatrix}0 & 0 & 1\\0 & 1 & 0\\1 & 0 & 0\end{pmatrix}.$$Does it follow that $$M_{\sigma \tau} = M_\sigma M_\tau$$for all $\sigma, \tau \in S_n$, where the product on the right is the ordinary product of matrices?
-
1$\begingroup$ Are you sure that this is the right permutation matrix? Shouldn't it be $M_\sigma = \begin{pmatrix}0 & 0 & 1\\1 & 0 & 0\\0 & 1 & 0\end{pmatrix}$ ? $\endgroup$– EvgenySep 8, 2015 at 5:49
-
$\begingroup$ It depends on whether you are using left or right multiplication. If the matrix is acting on row vectors by right multiplication then it should be $M_{\sigma} = \begin{pmatrix} 0&1&0\\0&0&1\\1&0&0 \end{pmatrix}$. This goes with the standard group action notation for permutation multiplication, where $x^{\sigma \tau}=(x^{\sigma})^{\tau}$. But I guess the OP does mention that he wants $1$ at $(i, \sigma(i))$, which is your matrix. $\endgroup$– xxxxxxxxxSep 8, 2015 at 7:28
1 Answer
Yes, for $\sigma\in S_n$, $M_\sigma$ is called a permutation matrix. Essentially it permutes the standard basis (that is, the columns of the identity matrix). So the actions of $M_{\sigma\tau}$ and $M_\sigma M_\tau$ on the standard basis coincide. In view of linear algebra, they define the same linear transformation.
-
$\begingroup$ @MorganRodgers That wouldn't work still (note that it is symmetric). That matrix is of order $2$ (only permutes rows 1 and 3) while the permutation is of order $3$. $\endgroup$ Sep 8, 2015 at 7:25