Sum over exponentiated bilinear form in finite-field vector space

Question

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 here since I didn't get any answers there.

Answer 1

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.

Answer 2

Denote $b(X)=X^TAX$, $c(X)=(-1)^{b(X)}$ for $A=[a_{is}]$, $X=[x_1,\dots,x_n]^T$. Replacing $a_{ii}$ and $a_{ji}$ with $a_{ij}+a_{ji}$ and $0$, we may assume $A$ is upper-triangular.

The form $b$ depends on $x_1$ as $$ b(X)=x_1\left(a_{11}+\sum_{I=2}^n a_{1i}x_i\right)+ b_2(x_2,\dots,x_n). $$ If, for some values of $x_2,\dots,x_n$, the large bracket equals $1$, the sum of values of $c$ at two possible values of $x_1$ is $0$. So we are left to consider those values of $(x_2,\dots,x_n)$ where the large bracket vanishes. They form an $(n-2)$-dimensional subspace, and we are to deal with a quadratic form $A’$ on that subspace, obtaining $Z(A)=2Z(A’)$ (nite that $A’$ may have nonzero constant term, as we consider an affine subspace). This already establishes the property in the comment and provides an algorithm of computing $Z$. Possibly, this may also provide an explicit form of $Z$?