1
$\begingroup$

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?

$\endgroup$

2 Answers 2

4
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ More generally over any field $K$ the symmetric $n \times n$ matrices with entries in $K$ are a linear subspace of the $n \times n$ matrices with entries in $K$, and this arguments shows that this subspace is of dimension $\binom{n+1}{2}$. $\endgroup$ Jan 4, 2016 at 14:05
2
$\begingroup$

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}}$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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