# From the collection of all permutation matrices of size $10\times10$, one such matrix is randomly picked. What is the expected value of its trace?

From the collection of all permutation matrices of size $$10\times10$$, one such matrix is randomly picked. What is the expected value of its trace? (A permutation matrix is one that has precisely one non-zero entry in each column and in each row, that non-zero entry being 1.)

I know that possible options for traces are $$0,1,2,3,4,5,6,7,8,9,10$$. Now from this how to find the expectation of the trace?

• What have you tried so far? Can you state how many $10 \times 10$ permutation matrices there are? How many with trace $0$? What about trace $1$? Feb 1, 2020 at 18:01
• Hint: The trace is the number of fixed points of the permutation. Feb 1, 2020 at 18:08
• @Saulspatz Indeed : duplicate of groupprops.subwiki.org/wiki/… with an elegant proof. Feb 6, 2020 at 12:03

Let $$A_{ij}$$ denote row $$i$$, column $$j$$, of matrix $$A$$.
Let $$G$$ be the set of $$10\times10$$ permutation matrices. Then the expected trace is
\begin{align*} \frac{1}{10!}\sum_{A\in G}\text{tr}(A) &= \frac{1}{10!}\sum_{A\in G}\sum_{i=1}^{10}A_{ii} \\ &= \frac{1}{10!}\sum_{i=1}^{10}\sum_{A\in G}A_{ii} \\ &= \frac{1}{10!}\sum_{i=1}^{10}9! \\ &= \frac{10\cdot9!}{10!} \\ &= 1 \end{align*}
Note that $$\underset{A\in G}{\sum}A_{ii}=9!$$, because each permutation matrix $$A$$ has $$A_{ii}=0$$ or $$A_{ii}=1$$. The ones with $$A_{ii}=1$$ are the ones that correspond to the permutations which send $$i\mapsto i$$, and there are $$9!$$ of those.
• How we can say that expectation of the trace is $\frac{1}{10!}\sum_{A\in G}\text{tr}(A)$. please clarify Feb 2, 2020 at 9:25
• The number of $10\times10$ permutation matrices is $10!$. Since we're randomly picking one, each of the $10!$ matrices is equally likely. So for each $A\in G$, the probability of picking $A$ is $\frac{1}{10!}$. Hence the expected value is $\underset{A\in G}{\sum}\frac{\text{tr}(A)}{10!}=\frac{1}{10!}\underset{A\in G}{\sum}\text{tr}(A)$. Feb 2, 2020 at 14:28