2
$\begingroup$

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?

$\endgroup$
2
  • 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$
    – Evgeny
    Sep 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$
    – xxxxxxxxx
    Sep 8, 2015 at 7:28

1 Answer 1

0
$\begingroup$

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.

$\endgroup$
1
  • $\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

You must log in to answer this question.