Let $\psi ,\varphi \in {S_n}$ two permutations.
Let $M$ a matrix such that $a_{i,j}=1$ iff $i=\sigma(j)$ where $\sigma \in S_n$ ($0$, otherwise)
I already showed that $tr(M) = \left| {\left\{ {k \in \{ 1...n\} |k = \sigma (k)} \right\}} \right|$
Now, I've been told to consider the following identity: $tr(XY) = tr(YX)$ and to conclude that for $\psi ,\varphi \in S_n$: the number of fixed points of $\psi\varphi$ equals to the number of fixed points of $\varphi\psi$. I demanded to show it without directly using matrices.
Any idea how?
A Thought:
is that right to say that:
$$tr({M_{\psi \varphi }}) = tr({M_\psi } \cdot {M_\varphi }) = tr({M_\varphi } \cdot {M_\psi }) = tr({M_{\varphi \psi }})$$