Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

up vote 2 down vote accepted

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.

Frankly, although it is possible to give a combinatorial interpretation, I don't think this kind of interpretations are useful in this case, and perhaps you should tell your student so.

share|improve this answer
    
I completely agree with the last sentence in that answer. Combinatorics should never be forced or systematized. –  Ewan Delanoy Feb 16 '13 at 9:21

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.