2
$\begingroup$

I want to prove that the product of two permutation matrices is itself a permutation matrix. But I don't know how. Please help!

$\endgroup$
  • 1
    $\begingroup$ How have you had a permutation matrix defined? Where are you stuck (when multiplying them, which of the properties are you having trouble verifying?) $\endgroup$ – Tobias Kildetoft May 20 '13 at 14:22
  • 2
    $\begingroup$ Unless you want to explicitly do this with matrix algebra, the most elegant proof would be to show that applying a permutation matrix to a vector permutes the vector's components, and then to use the facts that applying two permutations after each other is equivalent to applying a third permutation, and that applying two matrices to a vector after each other is equivalent to applying their product to the vector. $\endgroup$ – joriki May 20 '13 at 14:28
5
$\begingroup$

Method 1 - Using Matrices:

Suppose you have two permutation matrices $X$ and $Y$. So by definition both $X$ and $Y$ are $n\times n$ matrices having precisely one non-zero entry in each row and column, and these entries all take the value 1.

If the non-zero entry in the first row of $X$ is in the $i$-th column, then what will the first row of the matrix $X\cdot Y$ be? By definition of matrix multiplication it will be

$ \left(\sum_{j=1}^{n}X_{1,j}Y_{j,1}, \sum_{j=1}^{n}X_{1,j}Y_{j,2},\ldots,\sum_{j=1}^{n}X_{1,j}Y_{j,n} \right) $

However, we know that $X_{1,j}=\delta_{i,j}$ (where $\delta_{i,j}$ is the Kronecker delta taking the value $1$ when $i=j$ and $0$ otherwise). Hence the first row of $X\cdot Y$ will be

$ \left(X_{1,i}Y_{i,1}, X_{1,i}Y_{i,2},\ldots,X_{1,i}Y_{i,n} \right) $

which since $X_{1,i}=1$ will be

$ \left(Y_{i,1}, Y_{i,2},\ldots,Y_{i,n} \right). $

So the first row of $X\cdot Y$ corresponds to the $i$-th row of $Y$. Continuing in this way, you see that the $m$-th row of $X\cdot Y$ will be the $l$-th row of $Y$, where the $1$ in the $m$-th row of $X$ appears in the $l$-th position (I hope that makes sense!)

Thus when you multiply two permutation matrices together, you are just rearranging the rows of one of the matrices.

Method 2 - Using Permutations:

A slightly easier approach is to use permutations. Suppose $X$ and $Y$ are $n\times n$ permutation matrices as above. Then define $\sigma_{X}:\{1,\ldots, n\}\rightarrow\{1,\ldots,n\}$ as follows:

$\sigma_{X}(i)=j$ where the $1$ in the $i$-th column of $X$ occurs in the $j$-th position. Similarly you may define $\sigma_{Y}$.

Then you can check that $\sigma:X\mapsto\sigma_{X}$ respects multiplication (in a similar way as above).

Method 3 - Using Vectors:

You can also show this using vectors (see joriki's comment above for more details).

Note: All of these methods are essentially the same, but are just different ways of viewing the problem.

$\endgroup$
3
$\begingroup$

Hint:

If $P$ is a permutation matrix and $A$ any matrix then $AP$ is a matrix consisting of the columns of $A$ permuted. Similarly $PA$ consists the rows of $A$ permuted. Therefore if $A$ is also a permutation matrix ...

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.