Editing Permutation matrix (section)

== Permutation matrices permute rows or columns ==
Multiplying a matrix ''M'' by either <math>R_\pi</math> or <math>C_\pi</math> on either the left or the right will permute either the rows or columns of ''M'' by either {{pi}} or {{pi}}<sup>−1</sup>.  The details are a bit tricky.

To begin with, when we permute the entries of a vector <math>(v_1,\ldots,v_n)</math> by some permutation {{pi}}, we move the <math>i^\text{th}</math> entry <math>v_i</math> of the input vector into the <math>\pi(i)^\text{th}</math> slot of the output vector.  Which entry then ends up in, say, the first slot of the output?  Answer: The entry <math>v_j</math> for which <math>\pi(j)=1</math>, and hence <math>j=\pi^{-1}(1)</math>.  Arguing similarly about each of the slots, we find that the output vector is
:<math> \big(v_{\pi^{-1}(1)},v_{\pi^{-1}(2)},\ldots,v_{\pi^{-1}(n)}\big),</math>
even though we are permuting by <math>\pi</math>, not by <math>\pi^{-1}</math>. Thus, in order to permute the entries by <math>\pi</math>, we must permute the indices by <math>\pi^{-1}</math>.<ref name="Artin Algebra" />{{rp|page=25}}  (Permuting the entries by <math>\pi</math> is sometimes called taking the ''alibi viewpoint'', while permuting the indices by <math>\pi</math> would take the ''alias viewpoint''.<ref>{{cite book |author1-link=John H. Conway |last1=Conway |first1=John H. |last2=Burgiel |first2=Heidi |author3-link=Chaim Goodman-Strauss |last3=Goodman-Strauss |first3=Chaim |date=2008 |title=The Symmetries of Things |publisher=A K Peters/CRC Press |doi=10.1201/b21368 |isbn=978-0-429-06306-0 |oclc=946786108 |page=179 |quote=A permutation—say, of the names of a number of people—can be thought of as moving either the names or the people.  The alias viewpoint regards the permutation as assigning a new name or ''alias'' to each person (from the Latin ''alias'' = otherwise).  Alternatively, from the alibi viewoint we move the people to the places corresponding to their new names (from the Latin ''alibi'' = in another place.) }}</ref>)

Now, suppose that we pre-multiply some ''n''-row matrix <math>M=(m_{i,j})</math> by the permutation matrix <math>C_\pi</math>.  By the rule for [[matrix multiplication]], the <math>(i,j)^\text{th}</math> entry in the product <math>C_\pi M</math> is
:<math display=block>\sum_{k=1}^n c_{i,k}m_{k,j},</math>
where <math>c_{i,k}</math> is 0 except when <math>i=\pi(k)</math>, when it is 1.  Thus, the only term in the sum that survives is the term in which <math>k=\pi^{-1}(i)</math>, and the sum reduces to <math>m_{\pi^{-1}(i),j}</math>.  Since we have permuted the row index by <math>\pi^{-1}</math>, we have permuted the rows of ''M'' themselves by {{pi}}.<ref name="Artin Algebra" />{{rp|page=25}}  A similar argument shows that post-multiplying an ''n''-column matrix ''M'' by <math>R_\pi</math> permutes its columns by {{pi}}.

The other two options are pre-multiplying by <math>R_\pi</math> or post-multiplying by <math>C_\pi</math>, and they permute the rows or columns respectively by {{pi}}<sup>−1</sup>, instead of by {{pi}}.