Permutation Matrices

Suppose we have a matrix \(\,\boldsymbol{A}=[a_{ij}]_{m\times n}\in M_{m\times n}(K)\,\) given in the row form

\[\begin{split}\boldsymbol{A}\ \ =\ \ \left[\begin{array}{c} \boldsymbol{A}_1 \\ \boldsymbol{A}_2 \\ \ldots \\ \boldsymbol{A}_m\end{array}\right],\qquad \text{where}\quad\boldsymbol{A}_i\ =\ [\,a_{i1}\ \,a_{i2}\ \,\dots\ \,a_{in}\,]\,,\quad i=1,2,\dots,m\,,\end{split}\]

and a permutation \(\ \ \sigma\ =\ \left(\begin{array}{cccc} 1 & 2 & \ldots & m \\ \sigma(1) & \sigma(2) & \ldots & \sigma(m) \end{array}\right)\ \in\ S_m.\)

\(\;\)

The permutation \(\,\sigma\,\) determines an operation \(\,O_\sigma\,\) which rearranges rows of matrix \(\,\boldsymbol{A}\,:\)

(1)\[\begin{split}O_\sigma\,\boldsymbol{A}\ :\,=\ \left[\begin{array}{c} \boldsymbol{A}_{\,\sigma(1)} \\ \boldsymbol{A}_{\,\sigma(2)} \\ \ldots \\ \boldsymbol{A}_{\,\sigma(m)}\end{array}\right]\,.\end{split}\]

The operation \(\,O_\sigma\,\) being applied to the identity matrix

\[\begin{split}\boldsymbol{I}_m\ \ =\ \ \left[\begin{array}{c} \boldsymbol{e}_1 \\ \boldsymbol{e}_2 \\ \ldots \\ \boldsymbol{e}_m \end{array}\right]\,,\end{split}\]

(\(\,\boldsymbol{e}_i\,\) is a row of length \(\,m\,\) with unity in the \(\,i\)-th position, zeroes elsewhere), we obtain \(\\\) the matrix \(\,\boldsymbol{P}_\sigma\,\) referred to as the \(\,\) permutation matrix \(\,\) (matrix of the permutation \(\,\sigma\)):

\[\begin{split}\boldsymbol{P}_\sigma\ \ :\,=\ \ O_\sigma\,\boldsymbol{I}_m\ \ =\ \ \left[\begin{array}{c} \boldsymbol{e}_{\,\sigma(1)} \\ \boldsymbol{e}_{\,\sigma(2)} \\ \ldots \\ \boldsymbol{e}_{\,\sigma(m)} \end{array}\right]\,.\end{split}\]

Example. \(\,\) For \(\quad\sigma\ =\ \left(\begin{array}{ccccc} 1 & 2 & 3 & 4 & 5 \\ 4 & 3 & 5 & 1 & 2 \end{array}\right)\,\in S_5\quad\) the permutation matrix is

\[\begin{split}\boldsymbol{P}_\sigma\ =\ \left[\begin{array}{c} \boldsymbol{e}_{\,\sigma(1)} \\ \boldsymbol{e}_{\,\sigma(2)} \\ \boldsymbol{e}_{\,\sigma(3)} \\ \boldsymbol{e}_{\,\sigma(4)} \\ \boldsymbol{e}_{\,\sigma(5)} \end{array}\right]\ =\ \left[\begin{array}{c} \boldsymbol{e}_4 \\ \boldsymbol{e}_3 \\ \boldsymbol{e}_5 \\ \boldsymbol{e}_1 \\ \boldsymbol{e}_2 \end{array}\right]\ =\ \left[\begin{array}{ccccc} 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \end{array}\right]\,.\end{split}\]

\(\;\)

By analogy with elementary matrices, a permutation of rows of a product \(\,\boldsymbol{A}\boldsymbol{B}\,\) of two matrices is equivalent to the same permutation of rows of matrix \(\,\boldsymbol{A}\,\) only. This may be formulated as

Lemma.

If \(\,\boldsymbol{A}\in M_{m\times p}(K),\ \boldsymbol{B} \in M_{p\times n}(K),\ \ \sigma\in S_m,\ \ \) then \(\ \,O_\sigma\,(\boldsymbol{A}\boldsymbol{B})\ = \ (O_\sigma\boldsymbol{A})\,\boldsymbol{B}\,.\)

Proof. \(\,\) Using the Row Rule of Matrix Multiplication:

\[\begin{split}\boldsymbol{A}\boldsymbol{B}\ \equiv\ \left[\begin{array}{c} \boldsymbol{A}_1 \\ \boldsymbol{A}_2 \\ \dots \\ \boldsymbol{A}_m \\ \end{array} \right]\boldsymbol{B}\ \ =\ \ \left[\begin{array}{c} \boldsymbol{A}_1\,\boldsymbol{B} \\ \boldsymbol{A}_2\,\boldsymbol{B} \\ \dots \\ \boldsymbol{A}_m\,\boldsymbol{B} \\ \end{array} \right]\,.\end{split}\]

we get

\[\begin{split}O_\sigma\,(\boldsymbol{A}\boldsymbol{B})\ =\ O_\sigma \left[\begin{array}{c} \boldsymbol{A}_1\,\boldsymbol{B} \\ \boldsymbol{A}_2\,\boldsymbol{B} \\ \dots \\ \boldsymbol{A}_m\,\boldsymbol{B} \\ \end{array} \right]\ = \left[\begin{array}{c} \boldsymbol{A}_{\sigma(1)}\,\boldsymbol{B} \\ \boldsymbol{A}_{\sigma(2)}\,\boldsymbol{B} \\ \dots \\ \boldsymbol{A}_{\sigma(m)}\,\boldsymbol{B} \\ \end{array} \right]\ =\ \left[\begin{array}{c} \boldsymbol{A}_{\sigma(1)} \\ \boldsymbol{A}_{\sigma(2)} \\ \dots \\ \boldsymbol{A}_{\sigma(m)} \\ \end{array} \right]\boldsymbol{B}\ =\ (O_\sigma\boldsymbol{A})\,\boldsymbol{B}\,.\quad\bullet\end{split}\]

\(\;\)

Again by analogy with elementary matrices, pre-multiplying a given matrix by a permutation matrix simulates rearrangement of its rows according to that permutation. This is expressed as

Theorem 4.

If \(\,\boldsymbol{A}\in M_{m\times n}(K),\ \ \sigma\in S_m,\ \ \) then \(\ \,O_\sigma\,\boldsymbol{A}\ = \ \boldsymbol{P}_\sigma\,\boldsymbol{A}\,,\ \) \(\\\) where \(\ \ \boldsymbol{P}_\sigma\,= \,O_\sigma\,\boldsymbol{I}_m\in M_m(K)\,.\)

Proof. \(\,\) The thesis results immediately from the Lemma:

\[O_\sigma\,\boldsymbol{A}\ \ =\ \ O_\sigma\,(\boldsymbol{I}_m\,\boldsymbol{A})\ \ =\ \ (O_\sigma\,\boldsymbol{I}_m)\,\boldsymbol{A}\ \ =\ \ \boldsymbol{P}_\sigma\,\boldsymbol{A}\,, \qquad\sigma\in S_m\,.\quad\bullet\]

A product of two permutation matrices is also a permutation matrix, the multiplication rule being given by

Proposition 4. \(\,\)

If \(\quad P_\rho = O_\rho\,\boldsymbol{I}_m,\ \,P_\sigma = O_\sigma\,\boldsymbol{I}_m,\quad\) then \(\quad\boldsymbol{P}_\rho\,\boldsymbol{P}_\sigma\ = \ \boldsymbol{P}_{\sigma\,\circ\,\rho}\,,\quad\rho,\sigma\in S_m\ \ \) \(\\\) (note the reverse order of permutations on the right-hand side).

Proof.

\[\begin{split}\boldsymbol{P}_\sigma\,\boldsymbol{I}_m\ =\ \boldsymbol{P}_\sigma\, \left[\begin{array}{c} \boldsymbol{e}_1 \\ \boldsymbol{e}_2 \\ \dots \\ \boldsymbol{e}_m \\ \end{array} \right]\ =\ \left[\begin{array}{c} \boldsymbol{e}_{\sigma(1)} \\ \boldsymbol{e}_{\sigma(2)} \\ \dots \\ \boldsymbol{e}_{\sigma(m)} \\ \end{array} \right]\ =\ \left[\begin{array}{c} \boldsymbol{e}'_1 \\ \boldsymbol{e}'_2 \\ \dots \\ \boldsymbol{e}'_m \\ \end{array} \right]\,, \quad\text{where}\quad \boldsymbol{e}'_i\ =\ \boldsymbol{e}_{\sigma(i)}\,,\ \ i=1,2,\ldots,m.\end{split}\]

\[\begin{split}\boldsymbol{P}_\rho\,\boldsymbol{P}_\sigma\ =\ (\boldsymbol{P}_\rho\,\boldsymbol{P}_\sigma)\,\boldsymbol{I}_m\ =\ \boldsymbol{P}_\rho\,(\boldsymbol{P}_\sigma\,\boldsymbol{I}_m)\ =\ \boldsymbol{P}_\rho\, \left[\begin{array}{c} \boldsymbol{e}'_1 \\ \boldsymbol{e}'_2 \\ \dots \\ \boldsymbol{e}'_m \\ \end{array} \right]\ =\ \left[\begin{array}{c} \boldsymbol{e}'_{\rho(1)} \\ \boldsymbol{e}'_{\rho(2)} \\ \dots \\ \boldsymbol{e}'_{\rho(m)} \\ \end{array} \right]\,.\end{split}\]

Substitution \(\ \ i\rightarrow\rho(i)\ \ \) in equation \(\ \ \boldsymbol{e}'_i\ =\ \boldsymbol{e}_{\sigma(i)}\ \ \) results in

\[\boldsymbol{e}'_{\rho(i)}\ =\ \boldsymbol{e}_{\sigma[\rho(i)]}\ =\ \boldsymbol{e}_{(\sigma\,\circ\,\rho)(i)}\,,\qquad i=1,2,\ldots,m.\]

Therefore

\[\begin{split}\boldsymbol{P}_\rho\,\boldsymbol{P}_\sigma\ =\ \left[\begin{array}{c} \boldsymbol{e}'_{\rho(1)} \\ \boldsymbol{e}'_{\rho(2)} \\ \dots \\ \boldsymbol{e}'_{\rho(m)} \\ \end{array} \right]\ =\ \left[\begin{array}{c} \boldsymbol{e}_{(\sigma\,\circ\,\rho)(1)} \\ \boldsymbol{e}_{(\sigma\,\circ\,\rho)(2)} \\ \dots \\ \boldsymbol{e}_{(\sigma\,\circ\,\rho)(m)} \\ \end{array} \right]\ =\ \boldsymbol{P}_{\sigma\,\circ\,\rho} \left[\begin{array}{c} \boldsymbol{e}_1 \\ \boldsymbol{e}_2 \\ \dots \\ \boldsymbol{e}_m \\ \end{array} \right]\ =\ \boldsymbol{P}_{\sigma\,\circ\,\rho}\ \boldsymbol{I}_m\ =\ \boldsymbol{P}_{\sigma\,\circ\,\rho}\,.\quad\bullet\end{split}\]

Since every permutation can be expressed as a product of transpositions, every permutation matrix is a product of elementary matrices of the first type (corresponding to transpositions of matrix rows).

Another property of permutation matrices is stated by the following

Proposition 5. \(\,\)

Permutation matrices \(\ \boldsymbol{P}_\sigma\ \in M_m(K)\ \) are orthogonal: \(\quad\) \(\\\) \(\boldsymbol{P}_\sigma^{\,T}\,\boldsymbol{P}_\sigma\ = \ \, \boldsymbol{P}_\sigma\,\boldsymbol{P}_\sigma^{\,T}\ = \ \, \boldsymbol{I}_m\,,\quad\sigma\in S_m\,.\)

Proof.

In the framework of unitary spaces, it is enough to notice that rows of a permutation matrix form an orthonormal set of vectors in the space \(\,K^m,\ \) where \(\,K=Q,\,R\ \) or \(\,C.\ \) This is just a necessary and sufficient condition for a matrix to be orthogonal.

A direct proof is simple, too. Each row of \(\boldsymbol{P}_\sigma\ \) consists of one unity and zeroes elsewhere, \(\\\) the unities in different rows being in different positions. Thus for \(\ \boldsymbol{P}_\sigma = [p_{ij}]_{m \times m}\ \) we get

\[\begin{split}\left(\boldsymbol{P}_\sigma\,\boldsymbol{P}_\sigma^{\,T}\right)_{ij}\ =\ \, \displaystyle\sum_{k=1}^m\,p_{ik}\,p_{kj}^T\ =\ \, \displaystyle\sum_{k=1}^m\,p_{ik}\,p_{jk}\ \,=\ \, \left\{\begin{array}{ll} 1 & i=j \\ 0 & i \neq j \end{array}\right. \quad i,j = 1,2,\ldots, m.\end{split}\]

In this way \(\quad\left(\boldsymbol{P}_\sigma\, \boldsymbol{P}_\sigma^{\,T}\right)_{ij}\ =\ \left(\boldsymbol{I}_m\right)_{ij}\,,\ \ i,j = 1,2,\ldots, m,\quad\) hence \(\quad\boldsymbol{P}_\sigma\,\boldsymbol{P}_\sigma^{\,T}\ =\ \boldsymbol{I}_m\,.\quad\bullet\)

Let \(\,P\,\) denote the set of all permutation matrices associated with the symmetric group \(\,S_m:\)

\[P\ :\,=\ \left\{\,\boldsymbol{P}_\sigma\,:\ \ \sigma\in S_m\,\right\}\,.\]

Collecting results of the foregoing discussion, we note that

0. \(\,\) product of two permutation matrices is a permutation matrix:

   \(\,\) matrix multiplication is an internal operation in \(\,P;\)

1. \(\,\) multiplication of permutation matrices is associative;

2. \(\,\) the identity matrix \(\,\boldsymbol{I}_m\,\) is a permutation matrix

   \(\,\) corresponding to the identity permutation id;

3. \(\,\) permutation matrices are invertible, their inverses being also permutation matrices:

   \[\boldsymbol{P}_\sigma^{-1}\ =\ \boldsymbol{P}_{\sigma^{-1}}\ =\ \,\boldsymbol{P}_\sigma^T\,, \qquad\sigma\in S_m\,.\]

These remarks lead to the

Corollary. \(\,\)

The set of permutation matrices \(\ \,\boldsymbol{P}_\sigma\ \in M_m(K)\,,\ \sigma\in S_m\,,\ \) consttutes a group \(\\\) with respect to matrix multiplication. For \(\ m>2\ \) the group is non-commutative.

In Sage, \(\,\) the command \(\,\) SymmetricGroup(n) \(\,\) returns the group \(\ S_n\ \) of all permutations of \(\,n\,\) elements. 3 \(\,\) The members of \(\ S_n\ \) are displayed in the disjoint-cyclic form:

sage: G = SymmetricGroup(4)
sage: L = G.list()
sage: print G; L

Symmetric group of order 4! as a permutation group
[(), (3,4), (2,3), (2,3,4), (2,4,3), (2,4), (1,2), (1,2)(3,4), (1,2,3),
(1,2,3,4), (1,2,4,3), (1,2,4), (1,3,2), (1,3,4,2), (1,3), (1,3,4),
(1,3)(2,4), (1,3,2,4), (1,4,3,2), (1,4,2), (1,4,3), (1,4), (1,4,2,3),
(1,4)(2,3)]

A specific permutation can be selected by indexing the list of permutations in \(\ S_n\) \(\\\) (remembering that counting of elements starts at zero).

A permutation given in the disjoint-cycle form can be written

• as a text string (including quotes);

• as a list of tuples representing cycles.

Using this notation, a permutation may be put as an argument in a function call, in particular when extracting an element from the permutation group. Examples are shown below:

sage: G = SymmetricGroup(4)
sage: L = G.list()

sage: g0 = L[4]
sage: g1 = G('(1,2)(3,4)')
sage: g2 = G([(1,3),(2,4)])
sage: g3 = G(((1,4),(2,3)))

sage: print g0, g1, g2, g3

(2,4,3) (1,2)(3,4) (1,3)(2,4) (1,4)(2,3)

On the other hand, a particular permutation in a symmetric group can be created individually using the function PermutationGroupElement():

sage: p1 = PermutationGroupElement('(1,2)(3,4)')
sage: p2 = PermutationGroupElement([(1,3),(2,4)])
sage: p3 = PermutationGroupElement(((1,4),(2,3)))

sage: print p1.parent(); print p1, p2, p3

Symmetric group of order 4! as a permutation group
(1,2)(3,4) (1,3)(2,4) (1,4)(2,3)

Multiplication of permutations is performed in accordance with the left-to-right convention:

sage: p1 = PermutationGroupElement('(1,2)(3,4)')
sage: p2 = PermutationGroupElement('(2,1,3)')
sage: print p1*p2, p2*p1

(2,3,4) (1,4,3)

Now we shall apply the Sage tools to derive the matrix of the permutation

\[\begin{split}\sigma\ =\ (1,2,3)\ =\ \left(\begin{array}{cccc} 1 & 2 & 3 & 4 \\ 2 & 3 & 1 & 4 \end{array}\right)\ \in S_4\,.\end{split}\]

To that end we apply the method \(\,\) matrix() \(\,\) to a member of the permutation group:

The result reads

(2)\[\begin{split}P_{\sigma}\ \, = \ \ \left[\begin{array}{rrrr} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \end{array}\right] \ \ = \ \ \left[\begin{array}{c} \boldsymbol{e}_2 \\ \boldsymbol{e}_3 \\ \boldsymbol{e}_1 \\ \boldsymbol{e}_4 \end{array}\right] \ \ = \ \ \left[\begin{array}{c} \boldsymbol{e}_{\sigma (1)} \\ \boldsymbol{e}_{\sigma (2)} \\ \boldsymbol{e}_{\sigma (3)} \\ \boldsymbol{e}_{\sigma (4)} \\ \end{array}\right]\,,\end{split}\]

where \(\,\boldsymbol{e}_i\ \) is the \(\ i\)-th \(\,\) row \(\,\) of the identity matrix \(\,\boldsymbol{I}_4\,,\) \(\,i=1,2,3,4.\)

In section Permutations in Sage we have described another approach to permutations in Sage, based on the class of permutations, created by the command Permutations(). Specifically, Permutations(n) returns the class of permutations of \(\,n\,\) initial natural numbers, given in a one-line notation. A particular permutation may be constructed by the function Permutation().

Following that approach, we shall derive the matrix of the permutation \(\,p\,=\,[\,2,3,1,4\,]\sim\sigma\,,\ \) using the method \(\,\) to_matrix() \(\,\) from \(\,\) Permutation_class:

Now the output is

(3)\[\begin{split}Q_{\sigma}\ \, = \ \ \left[\begin{array}{cccc} 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \end{array}\right] \ \ = \ \ \left[\ \boldsymbol{e}_2\,|\,\boldsymbol{e}_3\,|\, \boldsymbol{e}_1\,|\,\boldsymbol{e}_4\ \right] \ \ = \ \ \left[\ \boldsymbol{e}_{\sigma (1)}\,|\ \boldsymbol{e}_{\sigma (2)}\,|\ \boldsymbol{e}_{\sigma (3)}\,|\ \boldsymbol{e}_{\sigma (4)}\ \right]\,,\end{split}\]

where \(\,\boldsymbol{e}_j\ \) is the \(\ j\)-th \(\,\) column \(\,\) of the identity matrix \(\,\boldsymbol{I}_4\,,\) \(\,j=1,2,3,4.\)

The matrix \(\,P_{\sigma}\ \) in (2) is obtained from the identity matrix by the permutation \(\,\sigma\ \) of rows, whereas \(\,Q_{\sigma}\ \) in (1) is obtained by the same permutation of columns. The two matrices are interrelated by transpose: each one is the transpose of another. The Sage code below checks the equivalence of permutations used to construct \(\,P_{\sigma}\ \) and \(\,Q_{\sigma}\ \) as well as the relation \(\,Q_{\sigma}=P_{\sigma}^{\,T}:\)

Conclusion. \(\,\)

The method \(\,\) matrix(), \(\,\) applicable to permutations of a Symmetric group, refers to the matrix representation of permutations in the row version, \(\,\) whereas the method \(\,\) to_matrix() \(\,\) from the \(\,\) Permutation_class \(\,\) pertains to \(\,\) the \(\,\) column version \(\,\) thereof.

3

http://doc.sagemath.org/html/en/thematic_tutorials/group_theory.html#permutation-groups