# (0,1)-matrix congruence: is it known?

[[UPDATE: This work has now been published at SIAM J Discrete Math.: Formulae for the Alon–Tarsi Conjecture.]]

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. SIAM J. Discrete Math., 24 (2010), 394-399.

-
Stupid remark: Why does $p$ have to be odd? –  darij grinberg Apr 14 '10 at 14:02
since $2$ is not considered here. –  Sunni Apr 14 '10 at 16:12
I added a response to p=2 case in the question. @darij: I think the equivalent congruence is what you were heading towards in your original response. It's also possible to modify it in many ways that cancel out in the inclusion-exclusion. –  Douglas S. Stones Apr 16 '10 at 1:47

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.

-
I've read through your proof and am convinced it is correct. Thank you very much! I would like to add this proof (and the new proof of Glynn's congruence) in a paper I'm writing -- could you please send me an email: the_empty_element (at) yahoo.com so we can get in contact in private. –  Douglas S. Stones Apr 17 '10 at 4:09
Done. Needless to say, you are welcome to use this argument for whatever purposes you wish (that was the whole point of posting it). –  fedja Apr 17 '10 at 11:27
I'm trying to get in contact with you again about this work. Would you be able to contact me please? –  Douglas S. Stones Jul 5 '11 at 15:52
I sent you an e-mail. –  fedja Jul 5 '11 at 16:50