6
$\begingroup$

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?

$\endgroup$
3
  • 1
    $\begingroup$ 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$? $\endgroup$ Feb 1, 2020 at 18:01
  • 1
    $\begingroup$ Hint: The trace is the number of fixed points of the permutation. $\endgroup$
    – saulspatz
    Feb 1, 2020 at 18:08
  • $\begingroup$ @Saulspatz Indeed : duplicate of groupprops.subwiki.org/wiki/… with an elegant proof. $\endgroup$
    – Jean Marie
    Feb 6, 2020 at 12:03

1 Answer 1

10
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ How we can say that expectation of the trace is $\frac{1}{10!}\sum_{A\in G}\text{tr}(A)$. please clarify $\endgroup$
    – vqw7Ad
    Feb 2, 2020 at 9:25
  • 1
    $\begingroup$ 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)$. $\endgroup$
    – user729424
    Feb 2, 2020 at 14:28
  • $\begingroup$ ok. I got it........ $\endgroup$
    – vqw7Ad
    Feb 2, 2020 at 16:39
  • 2
    $\begingroup$ Great! By the way, thanks for posting this really cool problem! $\endgroup$
    – user729424
    Feb 2, 2020 at 16:44

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .