Raising the bar

Properties of permutation matrices

Shortcut for permutations

A permutation matrix permutes (changes orders of) rows of a matrix. The precise meaning of this statement is given in equation (1) below.

Partitioning the matrix $latex A$ into rows $latex A_i$ we have

$latex e_iA=(0,...,0,1,0,...0)\left(\begin{array}{c}A_1 \\... \\A_i \\... \\A_n\end{array}\right)=A_i.$

Stacking these equations we get

$latex P_{j_1,...,j_n}A=\left(\begin{array}{c}e_{j_1} \\... \\e_{j_n}\end{array}\right) A=\left(\begin{array}{c}e_{j_1}A \\... \\e_{j_n}A\end{array}\right) =\left(\begin{array}{c}A_{j_1} \\... \\A_{j_n}\end{array}\right).$

By analogy with $latex P_{j_1,...,j_n}$ we denote the last matrix

$latex A_{j_1,...,j_n}=\left(\begin{array}{c}A_{j_1} \\... \\A_{j_n}\end{array}\right).$

Thus, pre-multiplication by $latex P_{j_1,...,j_n}$ transforms $latex A$ to $latex A_{j_1,...,j_n}:$

(1) $latex P_{j_1,...,j_n}A=A_{j_1,...,j_n}.$

If we had proven the multiplication rule for determinants, we could have concluded from (1) that

(2) $latex \det (P_{j_1,...,j_n})\det A=\det A_{j_1,...,j_n}.$

As we know, changing places of two rows changes the sign of $latex \det A$ by -1. (2) tells us that permutation by $latex P_{j_1,...,j_n}$ changes the sign of $latex \det A$ by $latex \det (P_{j_1,...,j_n}).$ In the rigorous algebra course (2) is proved using the theory of permutations, without employing the multiplication rule for determinants.

I am going to call (2) a shortcut for permutations and use it without a proof. In general, I prefer to use such shortcuts, to see what is going on and bypass tedious proofs.

Other properties of permutation matrices

Exercise 1. Prove that Definition 1 is equivalent to the following: A permutation matrix $latex P$ is defined by two conditions: a) all its columns are unit column-vectors and b) no two columns are equal.

Proof. Take the $latex j$th column. It contains one unity (the one that comes from the $latex j$th unit row-vector). It cannot contain more than one unity because all rows are different. Hence, the $latex j$th column is a unit column-vector. Different columns are different unit vectors because otherwise some row would contain at least two unities and would not be a unit vector.

Exercise 2. Prove that a permutation matrix is an orthogonal matrix.

Proof. By Exercise 1 we can write a permutation matrix as a matrix of unit column-vectors:

$latex P=\left( u_{j_1},...,u_{j_n}\right).$ Then

$latex P^TP=\left(\begin{array}{c}u_{j_1}^T \\... \\u_{j_n}^T\end{array}\right)\left(u_{j_1},...,u_{j_n}\right) =\left(\begin{array}{ccc}u_{j_1}^Tu_{j_1}&...&u_{j_1}^Tu_{j_n} \\...&...&... \\u_{j_n}^Tu_{j_1}&...&u_{j_n}^Tu_{j_n}
\end{array}\right)=I,$

which proves orthogonality. It follows that $latex \det P=\pm 1$ (be careful with this equation, it follows from multiplicativity of determinants which we have not derived from our axioms).

← Previous: Permutation matrices | Next: Leibniz formula for determinants →

Get the PDF book “Matrix Algebra” on Lulu