I want to prove that the product of two permutation matrices equals the matrix of the composition of the two permutations:
$M(\sigma).M(\tau)=M(\sigma \circ \tau)$, where both $M(\sigma)$ and $M(\tau)$ are $n\times n$
So far this is what I got:
$M(\sigma) = (s_{ij})$ and $M(\tau)= (t_{ij})$
$M(\sigma).M(\tau)=A$
$A=(a_{ij})$, where:
$a_{ij} = \sum_{k=1}^{n}s_{ik}\times t_{kj}$
Now is where I'm kind of lost. I also know that:
$M(\sigma \circ \tau) = (u_{ij})$, where:
$u_{ij} =
\begin{cases}
1 & \quad \text{if } \sigma(\tau(j))=i\\
0 & \quad \text{if not}\\
\end{cases}
$
Actually, I have problems proving stuff in general, so it would be also helpful if you could point me in the direction of understanding proofs.
Thank you for your help!
Best Answer
I'm going to use a slightly different approach, just because I have an aversion to $\sum_k a_{ik}b_{kj}$ type formulas!
Note: I realized about halfway through that I write permutation matrices "backwards;" with nice rows and messy columns. I did rewrite to match what I suspect is your convention, but if you see any funniness that seems to clash with the rest of the notation, that's probably the blame. For that, and other reasons, I'd advise you to not follow the details too closely; try and pick up the main idea that it's much nicer to work with rows/columns of matrices: Get the "individual entry stuff" out of the way at the beginning, to understand the rows/columns of the given matrices, then use rows/columns from that point on.
For my approach, remember that to multiply matrices $A$ and $B$, we take the dot product of row $R_i$ from matrix $A$, and column $C_j$ of matrix $B$, to get the entry $(AB)_{ij}$.
Now, the columns of permutation matrix $M_\pi$ are pretty straightforward; column $j$ is just $e_{\pi(j)}$, the $\pi(j)$th basis vector with a $1$ in position $\pi(j)$ and $0$ everywhere else.
The rows are a bit less straightforward. If we look at $M_\pi$, where is the $1$ in row $i$? Turning around the previous example, we saw $1$ in entry $(M_\pi)_{\pi(j)j}$; that is, in row $\pi(j)$ and column $j$. This suggests that, to find the $1$ in row $i$, we need to look in column $\pi^{-1}(i)$.
Thus, the $i$th row of matrix $M_\pi$ is the transpose $e^t_{\pi^{-1}i}$ of the $\pi^{-1}(i)$th basis vector, where I've dropped parentheses in $\pi^{-1}(i)$ for readability, and will continue to do so for indices.
Now, write $M_\sigma$ as a column of rows $e^t_{\sigma^{-1}i}$ and $M_\tau$ as a row of columns $e_{\tau j}$. We compute
$$M_\sigma M_\tau = \begin{pmatrix}e^t_{\sigma^{-1} 1} \\ e^t_{\sigma^{-1} 2} \\ \vdots \\ e^t_{\sigma^{-1} n}\end{pmatrix} \begin{pmatrix}e_{\tau 1} & e_{\tau 2} & \cdots & e_{\tau n}\end{pmatrix},$$
where the entry at position $(i, j)$ is just the dot product $e_{\sigma^{-1} i} \cdot e_{\tau j}.$ Breaking into cases, we have
$$e_{\sigma^{-1} i} \cdot e_{\tau j} = \begin{cases} 1, & \sigma^{-1}(i) = \tau (j) \\ 0&\rm{otherwise} \end{cases}.$$
Investigating $\sigma^{-1}(i) = \tau (j)$ a bit more, apply $\sigma$ to both sides to get $i = \sigma(\tau(j)) = (\sigma \circ \tau)(j)$. This is indeed the permutation matrix $M_{\sigma \circ \tau}$!