# Combinatorics of symmetric elements in $M_n(F_m)$

One of my tutees asked me a question about the number of such matrices, and I'm stumped:

In the set of matrices of dimension $n\times n$ over a finite field $F_m$, we want to ask how many are symmetric. My immediate answer to the question is that we consider the upper diagonal matrices instead, since we have the same independent choices.

Then for the first row we can choose $n$, for the second $n-1$, for the third $n-2$, and so on down to just one choice for the $n^\text{th}$ row. Since we can choose up to $m$ elements for any of them, we have $m^{n+(n-1)+(n-2)+\cdots+1}=m^{n(n+1)/2}$.

However, it follows easily from the algebra that $\frac{n(n+1)}{2}$ is simply ${n+1\choose 2}$, so nothing is stopping us from writing the number of symmetric matrices as $m^{n+1\choose 2}$.

But now he wanted a combinatorial interpretation for this formula. So the question is: What in the world is this set of $n+1$ things, and why does choosing two of them tell us anything about decisions we can make to form such matrices?

-

You have $n+1$ balls, where the first $n$ are numbered from $1$ to $n$ and the last one is a joker. Now you draw two of them. If both are numbered, say $i$ and $j$, fill in the pair of entries $(i,j)$ and $(j,i)$. If one of them is numbered, say $i$, and the other is the joker, fill in the $(i,i)$-th entry. So there are $n+1\choose 2$ ways to choose an unordered pair of indices $\{i,j\}$ (with $i$ possibly equal to $j$). For each such pair of indices, there are $m$ ways to fill in the $(i,j)$-th (and hence $(j,i)$-th) entry.