From the collection of all permutation matrices of size $10×10$, 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).

**Solution**:

**Direct method**: Expectation is nothing but the average. We will calculate the avarage. Let $P_n$ be the set of all $n \times n$ permutation matrices, then there are $n!$ many permuation matrices one for each permuation in $S_n$ (see below for the precise definition). We get the average (expected) trace as,

$$\begin{align*}\frac{1}{10!}\sum_{A\in P_{10}}\text{tr}(A) &= \frac{1}{10!}\sum_{A\in P_{10}}\sum_{i=1}^{10}A_{ii} \\&= \frac{1}{10!}\sum_{i=1}^{10}\sum_{A\in P_{10}}A_{ii} \\&= \frac{1}{10!}\sum_{i=1}^{10}9! \\&= \frac{10\cdot9!}{10!} \\&= 1\end{align*}$$

**Probabilistic method**:

Let $\sigma$ be a permutation in $S_n$ and $A_{\sigma}$ be the associated permutation matrix. For example, consider the permutation $\sigma = (1)(234)(5)$ in $S_5$, then the associated permutation matrix is obtained by permuting the rows (or colums (fix a convention)) of the $5 \times 5$ identity matrix. Hence $$A_{\sigma} = \begin{bmatrix} 1&0&0&0&0\\0&0&0&1&0\\ 0&1&0&0&0\\0&0&1&0&0\\0&0&0&0&1\\\end{bmatrix}.$$ Note that the second row of the identity matrix moved to third row, third row moved to fourth row and fourth row moved to second row as in the permutation $\sigma$. Other rows are not disturbed bacause they are not permuted by the permutation $\sigma$.

**Observation**: $\text{Trace } A_{\sigma} = \text{the number of fixed points of } \sigma$.

Proof: $i$ th row contribute to trace iff $i$ th row is not disturbed iff $\sigma(i)=i$.

So we can rephrase the given question as, from the set of all $10 \times 10$ permutations $S_{10}$ one permutation is randomly picked. What is the expected value of its number of fixed points?

Consider $1 \le i \le 10$, then the set $\{\sigma \in S_{10} : \sigma(i) = i\}$ has $9!$ number of elements. We get that the probability $p_i$ of $i$ being fixed is $\frac{9!}{10!} = \frac{1}{10}$. This probability is same for any $1 \le i \le 10$. Now, the required expected number of fixed points is equal to $\sum_{i=1}^{10} p_i = \sum_{i=1}^{10} \frac{1}{10} = 1$ (By the linearity of the expectation).

**Share to your groups:**

**FOLLOW BY EMAIL TO GET NOTIFICATION OF NEW PROBLEMS. SHARE YOUR DOUBTS AND COMMENTS BELOW IN THE COMMENTS SECTION. ALSO, SUGGEST PROBLEMS TO SOLVE.**

## No comments:

## Post a Comment