Permutation Matrices And Row Reordering

Permutations as Matrix Operations

Reordering rows or columns is a familiar operation, but it is important to specify exactly which order a matrix records. A permutation matrix turns a reordering into a matrix product. Its determinant records whether the permutation preserves or reverses the sign of the determinant: an even permutation contributes \(1\), while an odd permutation contributes \(-1\).

Throughout, matrices are square of size \(n\times n\) when a determinant is taken, and scalars are in \(\mathbb{R}\). A permutation \(\sigma\) of \(\{1,\dots,n\}\) is a bijection from this set to itself. Its one-line notation is the list \(\sigma(1),\dots,\sigma(n)\). An inversion is a pair \(i<j\) for which \(\sigma(i)>\sigma(j)\). The sign \(\operatorname{sgn}(\sigma)\) is \(1\) if the number of inversions is even and \(-1\) if it is odd. Equivalently, it is \(1\) for a permutation expressible as an even number of transpositions, and \(-1\) for one expressible as an odd number. The standard sign rules are \(\operatorname{sgn}(\alpha\circ\beta)=\operatorname{sgn}(\alpha)\operatorname{sgn}(\beta)\) and \(\operatorname{sgn}(\sigma^{-1})=\operatorname{sgn}(\sigma)\).

This convention determines the order of the rows and columns. If \(\mathbf{A}\) has rows \(\mathbf{r}_1,\dots,\mathbf{r}_n\) and columns \(\mathbf{a}_1,\dots,\mathbf{a}_n\), then left multiplication gives row \(i\) of \(\mathbf{P}_{\sigma}\mathbf{A}\) from row \(\sigma^{-1}(i)\) of \(\mathbf{A}\). Right multiplication gives column \(j\) of \(\mathbf{A}\mathbf{P}_{\sigma}\) as \(\mathbf{a}_{\sigma(j)}\). The inverse appears in the left-multiplication rule because the \(1\) in row \(i\) of \(\mathbf{P}_{\sigma}\) is in column \(\sigma^{-1}(i)\).

Two Basic Identities

Proof. For each standard basis vector \(\mathbf{e}_j\), the definition gives \(\mathbf{P}_{\sigma}\mathbf{P}_{\tau}\mathbf{e}_j=\mathbf{P}_{\sigma}\mathbf{e}_{\tau(j)}=\mathbf{e}_{\sigma(\tau(j))}\). This is also \(\mathbf{P}_{\sigma\circ\tau}\mathbf{e}_j\). The two matrices therefore agree on every standard basis vector. Each column of a matrix is its product with the corresponding standard basis vector, so the matrices have the same columns and are equal. \(\square\)

The order of composition matters: the matrix on the right acts first. This identity also shows how to combine successive reorderings without guessing their order.

Proof. The entry of \(\mathbf{P}_{\sigma}\mathbf{A}\) in row \(i\), column \(j\) is \(\sum_{k=1}^{n}p_{ik}a_{kj}=a_{\sigma^{-1}(i),j}\), since row \(i\) of \(\mathbf{P}_{\sigma}\) has its only \(1\) in column \(\sigma^{-1}(i)\). The entry of \(\mathbf{A}\mathbf{P}_{\sigma}\) in row \(i\), column \(j\) is \(\sum_{k=1}^{n}a_{ik}p_{kj}=a_{i,\sigma(j)}\), since column \(j\) of \(\mathbf{P}_{\sigma}\) has its only \(1\) in row \(\sigma(j)\). These establish the stated row and column orders.

To prove the determinant identities, use the Leibniz formula \(\det(\mathbf{A})=\sum_{\tau}\operatorname{sgn}(\tau)\prod_{i=1}^{n}a_{i,\tau(i)}\), where the sum is over all permutations \(\tau\) of \(\{1,\dots,n\}\). Write \(\mathbf{B}=\mathbf{P}_{\sigma}\mathbf{A}\). Substituting \(b_{ij}=a_{\sigma^{-1}(i),j}\) gives \(\det(\mathbf{B})=\sum_{\tau}\operatorname{sgn}(\tau)\prod_i a_{\sigma^{-1}(i),\tau(i)}\). Set \(k=\sigma^{-1}(i)\), so \(i=\sigma(k)\), and define \(\rho=\tau\circ\sigma\). The product becomes \(\prod_k a_{k,\rho(k)}\). As \(\tau\) ranges over all permutations, so does \(\rho\), and \(\operatorname{sgn}(\tau)=\operatorname{sgn}(\rho)\operatorname{sgn}(\sigma)\). Therefore \(\det(\mathbf{B})=\operatorname{sgn}(\sigma)\det(\mathbf{A})\).

For \(\mathbf{C}=\mathbf{A}\mathbf{P}_{\sigma}\), use \(c_{ij}=a_{i,\sigma(j)}\) in the same formula: \(\det(\mathbf{C})=\sum_{\tau}\operatorname{sgn}(\tau)\prod_i a_{i,\sigma(\tau(i))}\). Set \(\rho=\sigma\circ\tau\). Then \(\operatorname{sgn}(\tau)=\operatorname{sgn}(\sigma)\operatorname{sgn}(\rho)\), and the products are \(\prod_i a_{i,\rho(i)}\). Summing over all \(\rho\) proves \(\det(\mathbf{C})=\operatorname{sgn}(\sigma)\det(\mathbf{A})\).

Finally, apply the Leibniz formula to \(\mathbf{P}_{\sigma}\). A product \(\prod_i p_{i,\tau(i)}\) is nonzero exactly when \(\tau(i)=\sigma^{-1}(i)\) for every \(i\). There is one such permutation, \(\tau=\sigma^{-1}\), and its product is \(1\). Thus \(\det(\mathbf{P}_{\sigma})=\operatorname{sgn}(\sigma^{-1})=\operatorname{sgn}(\sigma)\). \(\square\)

This argument uses the Leibniz formula directly; it does not assume the multiplicative determinant law. In particular, it proves the effect of these specific matrix products without relying on a general formula for the determinant of a product.

Worked Row and Column Reorderings

Common Sign and Indexing Errors

Do not confuse the permutation with its inverse when reading rows. For the three-cycle in the first example, \(\sigma=(2,3,1)\), but left multiplication puts the old rows in the order \((3,1,2)\), not \((2,3,1)\). The latter list describes where the columns of the permutation matrix’s standard basis vectors go; the row order of the product is indexed by \(\sigma^{-1}\). Checking the entries of \(\mathbf{P}_{\sigma}\mathbf{A}\) resolves the ambiguity.

Do not assign a three-cycle the sign of a single swap. A common wrong calculation is to say that a cycle of length three must have sign \(-1\), and therefore to predict \(\det(\mathbf{P}_{\sigma}\mathbf{A})=-5\) in the first example. The one-line notation \((2,3,1)\) has two inversions, so the sign is \(1\); equivalently, a three-cycle can be written using two transpositions. The corrected determinant is \(5\), as direct expansion confirms.

The practical rule is to count inversions or transpositions before changing a determinant. A row or column permutation changes its value only by the sign of that permutation; it does not change the magnitude. If several reorderings are made, compose their permutations in the order the corresponding matrices act, or keep track of each sign separately.