Product of permutation matrices I want to prove that the product of two permutation matrices is itself a permutation matrix. But I don't know how. Please help!
 A: 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.
A: 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 ...
