Editing Permutation (section)

===Matrix representation===
{{main|Permutation matrix}}

A ''permutation matrix'' is an [[Square matrix|''n'' × ''n'' matrix]] that has exactly one entry 1 in each column and in each row, and all other entries are 0. There are several ways to assign a permutation matrix to a permutation of {1, 2, ..., ''n''}. One natural approach is to define <math>L_{\sigma}</math> to be the [[Linear map|linear transformation]] of <math>\mathbb{R}^n</math> which permutes the [[standard basis]] <math>\{\mathbf{e}_1,\ldots,\mathbf{e}_n\}</math> by <math>L_\sigma(\mathbf{e}_j)=\mathbf{e}_{\sigma(j)}</math>, and define <math>M_{\sigma}</math> to be its matrix. That is, <math>M_{\sigma}</math> has its ''j''<sup>th</sup> column equal to the n × 1 column vector <math>\mathbf{e}_{\sigma(j)}</math>: its (''i'', ''j'') entry is to 1 if ''i'' = ''σ''(''j''), and 0 otherwise. Since composition of linear mappings is described by matrix multiplication, it follows that this construction is compatible with composition of permutations:<blockquote><math>M_\sigma M_\tau = M_{\sigma\tau}</math>.  </blockquote>For example, the one-line permutations <math>\sigma=213,\ \tau=231</math> have product <math>\sigma\tau = 132</math>, and the corresponding matrices are:<math display="block">
M_{\sigma} M_{\tau} 
= \begin{pmatrix} 0&1&0\\1&0&0\\0&0&1\end{pmatrix}
\begin{pmatrix} 0&0&1\\1&0&0\\0&1&0\end{pmatrix} 
= \begin{pmatrix} 1&0&0\\0&0&1\\0&1&0\end{pmatrix} 
= M_{\sigma\tau}.</math>

[[File:Symmetric group 3; Cayley table; matrices.svg|thumb|Composition of permutations corresponding to a multiplication of permutation matrices.]]
It is also common in the literature to find the inverse convention, where a permutation ''σ'' is associated to the matrix <math>P_{\sigma} = (M_{\sigma})^{-1} = (M_{\sigma})^{T}</math> whose (''i'', ''j'') entry is 1 if ''j'' = ''σ''(''i'') and is 0 otherwise.  In this convention, permutation matrices multiply in the opposite order from permutations, that is, <math>P_\sigma P_{\tau} = P_{\tau\sigma}</math>.  In this correspondence, permutation matrices act on the right side of the standard <math>1 \times n</math> row vectors <math>({\bf e}_i)^T</math>: <math>({\bf e}_i)^T P_{\sigma} = ({\bf e}_{\sigma(i)})^T</math>.

The [[Cayley table]] on the right shows these matrices for permutations of 3 elements.