Editing Permutation matrix (section)

== The two permutation/matrix correspondences ==

There are two natural one-to-one correspondences between permutations and permutation matrices, one of which works along the rows of the matrix, the other along its columns.  Here is an example, starting with a permutation {{pi}} in two-line form at the upper left:
:<math>\begin{matrix} 
\pi\colon\begin{pmatrix}1&2&3&4\\3&2&4&1\end{pmatrix}
& \longleftrightarrow &
R_\pi\colon\begin{pmatrix}
0&0&1&0\\
0&1&0&0\\
0&0&0&1\\
1&0&0&0\end{pmatrix}\\[5pt]
\Big\updownarrow && \Big\updownarrow\\[5pt]
C_\pi\colon\begin{pmatrix}
0&0&0&1\\
0&1&0&0\\
1&0&0&0\\
0&0&1&0\end{pmatrix}
& \longleftrightarrow &
\pi^{-1}\colon\begin{pmatrix}1&2&3&4\\4&2&1&3\end{pmatrix}\end{matrix}</math>
The row-based correspondence takes the permutation {{pi}} to the matrix <math>R_\pi</math> at the upper right.  The first row of <math>R_\pi</math> has its 1 in the third column because <math>\pi(1)=3</math>.  More generally, we have <math>R_\pi=(r_{ij})</math> where <math>r_{ij}=1</math> when <math>j=\pi(i)</math> and <math>r_{ij}=0</math> otherwise.

The column-based correspondence takes {{pi}} to the matrix <math>C_\pi</math> at the lower left.  The first column of <math>C_\pi</math> has its 1 in the third row because <math>\pi(1)=3</math>.  More generally, we have <math>C_\pi=(c_{ij})</math> where <math>c_{ij}</math> is 1 when <math>i=\pi(j)</math> and 0 otherwise.  Since the two recipes differ only by swapping ''i'' with ''j'', the matrix <math>C_\pi</math> is the transpose of <math>R_\pi</math>; and, since <math>R_\pi</math> is a permutation matrix, we have <math>C_\pi=R_\pi^\mathsf{T}=R_\pi^{-1}</math>.  Tracing the other two sides of the big square, we have <math>R_{\pi^{-1}}=C_\pi=R_\pi^{-1}</math> and <math>C_{\pi^{-1}}=R_\pi</math>.<ref>This terminology is not standard. Most authors use just one of the two correspondences, choosing which to be consistent with their other conventions.  For example, Artin uses the column-based correspondence.  We have here invented two names in order to discuss both options.</ref>