Let $A$ be a linear map over the finite-field vector space $(\mathbb F\_2)^n$, i.e., an $\mathbb F\_2$-valued $n\times n$ matrix, not necessarily symmetric. I'm interested in the sum
$$Z(A) = \sum\_{X\in \mathbb F\_2^n} (-1)^{X^T A X}\;,$$
where
$$x\rightarrow (-1)^x$$
should be thought of as a function from $\mathbb F\_2$ to $\mathbb Z$ (or $\mathbb R$ or $\mathbb C$).


Is there a way to efficiently compute $Z(A)$ for large matrices $A$? Can one say anything interesting about for which $A$ we have $Z(A)=0$? For example, one can easily see that $Z(A)=0$ if $A=1\oplus B$ where $1$ is a $1\times 1$ matrix.


The motivation behind this question comes from physics. $Z(A)$ is the partition function of a discrete path integral, $X$ is are the different configurations of degrees of freedom which are summed over, and $X^T A X$ is a quadratic action.


Reposting [this mathematics stackexchange question](https://math.stackexchange.com/q/4454008/487705) here since I didn't get any answers there.



Sum over exponentiated bilinear form in finite-field vector space
This is a multidimensional Gauss sum, and can be handled by the same methods used to handle Gauss sums.


$Z(A)=0$ if and only if $X^T A X$ is nonzero for some $X \in \ker (A + A^T)$, and, if $Z(A) \neq 0$, then $$Z(A) = \pm 2^{ \frac{n + \dim ( ker (A + A^T))}{2}}$$ which implies your divisibility claim.


To prove this, just note that


$$Z(A)^2 = \sum\_{X\_1, X\_2 \in \mathbb F\_2^n} (-1)^{X\_1^T A X\_1 + X\_2^T A X\_2} = \sum\_{X,Y\in \mathbb F\_2^n} (-1)^{ (X+Y)^T A (X+Y) + X^T A X } $$


and the exponent satisfies


$$(X+Y)^T A (X+Y) + X^T A X = X^T A X + X^T A Y + Y^T A X + Y^T A Y + X^T A X$$ $$ = X^T A Y + Y^T A X + Y^T A Y = X^T A Y + X^T A^T Y + Y^T A^T Y $$ so


$$Z(A)^2 = \sum\_{Y \in \mathbb F\_2^n} (-1)^{Y^T A Y} \sum\_{X\in \mathbb F\_2^n} (-1)^{ X^T (A + A^T ) Y } $$


Now the inner sum $\sum\_{X\in \mathbb F\_2^n} (-1)^{ X^T (A + A^T ) Y } $ vanishes unless $(A+A^T) Y =0$, i.e. $Y \in \ker (A+A^T)$, and equals $2^n$ in that case.


Restricted to $\ker (A +A^T)$, $Y^T A Y$ is actually a linear form, so the outer sum vanishes unless it is identically zero on $\ker (A + A^T)$ and is $2^{ \dim (A+A^T)}$ otherwise, giving


$$Z(A)^2 =2^{ n + \dim (\ker(A+A^T))}$$


unless $Y^T A Y$ is nonzero for some $Y \in \ker (A +A^T)$ and $$Z(A)^2= 0$$ if $Y^T A Y$ is nonzero for some $Y \in \ker (A +A^T)$, and thus the claim above.


