Question

The graduate students here at MIT have been thinking about questions like the following: Over $\mathbb{F}_q$, how many symmetric matrices are there with nonzero determinant and $0$'s on the diagonal? They are doing brute force computer searches; checking every point in $\mathbb{A}^N(\mathbb{F}_q)$ and seeing whether it is in the variety.

Is there a better way? Their examples are, like the above, low codimension subvarieties of high dimensional affine spaces. I think they are usually looking at smooth varieties, but I wouldn't swear to it in every case. The ideal answer, of course, would be preexisting software.

Answer 1

For a general variety and for a fixed small value of $q$, there isn't going to be a very good algorithm. That is because you can encode a Boolean formula in a single polynomial equation with minimal overhead. You are therefore counting solutions to a general logical expression, which is not only #P-hard, but also morally there is often nothing much better than exhaustive search.

On the other hand, if $q$ grows for a fixed formula, then you can use zeta function facts that algebraic geometers and number theorists know or conjecture to extrapolate from small values of $q$. For instance if $q = p^k$, you can use the Weil conjectures.

Since your example variety is far from general, you can try to exploit special structure to chip away at an exponential search (or count) and make it a better exponential search or count. I'll stick to your example problem, on the assumption that the others that they are looking at are similar.

First idea: There is a torus action on the set of symmetric matrices with vanishing diagonal. Thus you can assume that the first row and column is entirely 0s and 1s, and multiply by the size of the orbit. (Refinement: You can assume that the leading term in each row and column is 1.)

Second idea: Quadratic hypersurfaces in $\mathbb{A}^n$ are classified and you know how many points they have. So you do not have to complete the matrix; you can instead complete all but one row and column of the matrix. This idea combines with the first idea.

Third idea, much better than the other two: For each vector subspace $V \subseteq \mathbb{A}^n$, you can count the symmetric matrices which vanish on the diagonal and which annihilate $V$ (and maybe other vectors), because the equations for that are linear. You can then apply Möbius inversion on the lattice of subspaces to count the matrices that do not annihilate any vectors. You can loop over the vector spaces $V$ by assuming the unique basis in RREF form. Moreover, many subspaces with the same RREF pivot positions have to give you the same answer, for one reason because of the torus action.

Answer 2

You could try using p-adic cohomology (e.g. compute the action of Frobenius on the rigid cohomology of the moduli space of these matrices [which you have explicit equations for] and use the trace formula). There's a paper here which does this for various surfaces.

(This suggestion is kind of a long shot though.)