11
Feb 19

Properties of permutation matrices

category: Matrix algebra, MT2175 Further linear algebra No Comments

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 A into rows A_i we have

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

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 P_{j_1,...,j_n} we denote the last matrix

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

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

(1) 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) \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 \det A by -1. (2) tells us that permutation by P_{j_1,...,j_n} changes the sign of \det A by \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 P is defined by two conditions: a) all its columns are unit column-vectors and b) no two columns are equal.

Proof. Take the jth column. It contains one unity (the one that comes from the jth unit row-vector). It cannot contain more than one unity because all rows are different. Hence, the jth 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:

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

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 \det P=\pm 1 (be careful with this equation, it follows from multiplicativity of determinants which we have not derived from our axioms).

Post Views: 380

Leave a Reply

You must be logged in to post a comment.