Editing Permutation matrix (section)

== Multiplying permutation matrices ==
Given two permutations of {{math|''n''}} elements {{sigma}} and {{tau}}, the product of the corresponding column-based permutation matrices {{math|''C''<sub>σ</sub>}} and {{math|''C''<sub>τ</sub>}} is given,<ref name="Artin Algebra" />{{rp|page=25}} as you might expect, by
<math display=block>C_{\sigma} C_{\tau} = C_{\sigma\,\circ\,\tau}, </math>
where the composed permutation <math>\sigma\circ\tau</math> applies first {{tau}} and then {{sigma}}, working from right to left:
<math display=block>(\sigma\circ\tau) (k) = \sigma \left(\tau (k) \right).</math>
This follows because pre-multiplying some matrix by {{math|''C''<sub>τ</sub>}} and then pre-multiplying the resulting product by {{math|''C''<sub>σ</sub>}} gives the same result as pre-multiplying just once by the combined <math>C_{\sigma\,\circ\,\tau}</math>.

For the row-based matrices, there is a twist:  The product of {{math|''R''<sub>σ</sub>}} and {{math|''R''<sub>τ</sub>}} is given by
:<math>R_{\sigma} R_{\tau} = R_{\tau\,\circ\,\sigma}, </math>
with {{sigma}} applied before {{tau}} in the composed permutation.  This happens because we must post-multiply to avoid inversions under the row-based option, so we would post-multiply first by {{math|''R''<sub>σ</sub>}} and then by {{math|''R''<sub>τ</sub>}}.

Some people, when applying a function to an argument, write the function after the argument ([[Reverse Polish notation|postfix notation]]), rather than before it.  When doing linear algebra, they work with linear spaces of row vectors, and they apply a linear map to an argument by using the map's matrix to post-multiply the argument's row vector.  They often use a left-to-right composition operator, which we here denote using a semicolon; so the composition <math> \sigma\,;\,\tau</math> is defined either by
:<math>(\sigma\,;\,\tau)(k) = \tau\left(\sigma(k)\right),</math>
or, more elegantly, by
:<math>(k)(\sigma\,;\,\tau) = \left((k)\sigma \right)\tau,</math>
with {{sigma}} applied first.  That notation gives us a simpler rule for multiplying row-based permutation matrices:
:<math>R_{\sigma} R_{\tau} = R_{\sigma\,;\,\tau}. </math>