counting symmetric matrices over a finite field $\mathbb{F}_q$ I came across the fact that the number symmetric matrices of order $n$ over a finite field $\mathbb{F}_q$, where $q$ is an odd prime power, is equal to $q^{\binom{n+1}{2}}$, "trivially".
I don't really see why, there are $q$ possibilities for each entry and ofcourse the matrix needs to stay symmetric, but my combinatorial skills are unable to keep up.
Any help?
 A: Note that a symmetric matrix is completely determined by the elements on and below the main diagonal (or, equivalently, on and above the main diagonal). More technically, if $A = [a_{ij}]$ is a square matrix or order $n$, then one can freely choose the elements $a_{ij}$ for which $j \leq i$, the remaining elements (for which $j > i$) can then be found by the symmetricity, as $a_{ij} = a_{ji}$.
How many such positions "on or below the main diagonal" are there? We need to count the number of tuples of natural numbers $(i, j)$ for which $1 \leq j \leq i \leq n$. Fixing $i$, there are exactly $i$ possibilities for $j$: 1, 2, ..., $i$. We get for the total number of positions:
$$
\sum_{i = 1}^{n}i = \frac{n(n+1)}{2} = {n+1 \choose 2}
$$
I think the rest should be clear, but let me know if it's not.
A: Note that, fixing $n$, the "important" elements of a symmetric matrix of order $n$ are $1+2+\cdots+n$ (the number of elements on and above the main diagonal).
But the last is $1+2+\cdots+n=\frac{n(n+1)}{2}=\binom{n+1}{2}$.
For each of the $\binom{n+1}{2}$ elements required, thera are $q$ possible choices. Then, the total of ways to construct a symmetric matrix will be $q^{\binom{n+1}{2}}$ 
