[[UPDATE: This work has now been published at SIAM J Discrete Math.: [Formulae for the Alon–Tarsi Conjecture](http://epubs.siam.org/sidma/resource/1/sjdmec/v26/i1/p65_s1).]]


By equating two formulae (one congruence by Glynn (1) (which has just appeared) and one unpublished formula) for the number of even Latin squares minus the number of odd Latin squares, we find the following result.


For odd primes $p$ we have \[\sum\_{A \in B} (-1)^{\sigma\_0(A)} \equiv 1 \pmod p\] where $B$ is the set of $(p-1) \times (p-1)$ $\\,(0,1)$-matrices whose determinant is indivisible by $p$ and $\sigma\_0(A)$ is the number of zeroes in $A$. It happens to be true for $p=2$ also (but it does not follow from Glynn's result).



> 
> Is this result already known? If so, it would provide an alternate proof of Glynn's result.
> 
> 
> 


To illustrate, consider when $p=3$. The (0,1)-matrices whose determinants are indivisible by $p$ are



```
01 10       01 10 11 11
10 01  and  11 11 01 10

```

So the sum becomes $+2-4=-2 \equiv 1 \pmod 3$.


It is equivalent to the congruence \[\sum\_{A \in C} (-1)^{\sigma\_0(A)} \det(A)^{p-1} \equiv 1 \pmod p\] where $C$ is the set of all $(p-1) \times (p-1)$ $\\,(0,1)$-matrices (via Fermat's Little Theorem).


(1) Glynn, D., 2010. [The conjectures of Alon-Tarsi and Rota in dimension prime minus one](http://epubs.siam.org/sidma/resource/1/sjdmec/v24/i2/p394_s1). SIAM J. Discrete Math., 24 (2010), 394-399.



(0,1)-matrix congruence: is it known?
Darij's proof was wrong but both his claims (that it is next to trivial and that it requires some long formulae) were actually correct. Here is the demonstration.


To start with, we'll count the sum over degenerate (in $\mathbb Z\_p$) matrices instead because the sum over all matrices is clearly $0$. Also, I'll prefer to use $\sigma\_1$ instead of $\sigma\_0$ as the exponent of $(-1)$ (they have the same parity if $p>2$). Now, let us observe that the degenerate matrices are exactly those that kill some non-zero vector $x\in\mathbb Z\_p^{p-1}$. Moreover, the total number of vectors they kill is $-1$ (I'm counting modulo $p$, of course). Thus, we can just cound the sum over all $x\ne 0$ of the "signatures" of matrices that kill $x$. Now, a matrix kills $x$ if and only if each row kills $x$, so this sum is just the sum of signatures of all rows killing $x$ to the power $p-1$. The sum of row signatures over all possible rows is $0$, so we can again replace it with the sul over all rows not killing $x$ to the power $p-1$, which is the same as the sum over all matrices not killing $x$ in any row. Now, if we count modulo $p$, this sum can be written as
$$
\begin{aligned}
&\sum\_x\sum\_{\varepsilon}\prod\_{i,j}(-1)^{\varepsilon\_{ij}}\prod\_i\left(\sum\_j\varepsilon\_{ij}x\_j\right)^{p-1}
\\
&=\sum\_{x,\varepsilon}\sum\_\lambda\frac{(p-1)!^{p-1}}{\prod\_{i,j}\lambda\_{jj}!}\prod\_{i,j}(-1)^{\varepsilon\_{ij}}\varepsilon\_{ij}^{\lambda\_{ij}}x\_j^{\lambda\_{ij}}
\\
&=\sum\_{x,\lambda}\frac{(p-1)!^{p-1}}{\prod\_{i,j}\lambda\_{jj}!}\prod\_{i,j}x\_j^{\lambda\_{ij}}(0^{\lambda\_{ij}}-1)
\end{aligned}
$$ 
($\lambda$ here runs over all matrices with non-negative entries such that $\sum\_j\lambda\_{ij}=p-1$, $x$ runs over non-zero vectors in $\mathbb Z\_p$ and $\varepsilon$ runs over all $0,1$ matrices)


Now we use the deep formula $0^0=1$, which tells us that the only $\lambda$ for which the product is not $0$ is the one consisting of all ones. This reduces the sum to 
$$
(p-1)!^{p-1}\sum\_x\prod\_j x\_j^{p-1}=(p-1)!^{p-1}\left(\sum\_{a\in\mathbb Z\_p}a^{p-1}\right)^{p-1}\equiv (p-1)!^{p-1}(p-1)^{p-1}\equiv 1\mod p
$$
(we can now include the $0$ vector in the sum, it doesn't contribute anything).


The end.


