# Sum over 0-1 matrices

I stumbled across the following formula when working on a research problem in theoretical computer science. I am looking for a simple proof of it, or any idea which might prove useful.

I checked its correctness up to $$N=5$$ with a computer. Brendan McKay (see comment) was able to check its correctness up to $$N=8$$.

This question was first asked on Maths StackExchange two weeks ago.

Basic version

Let $$\mathcal M_N$$ be the set of all 0-1 square matrices without any row/column of zeros (we want all the denominators to be non-zero in the formula below). One could also define $$\mathcal M_N$$ to be A227414. $$\sum_{M \in \mathcal M_N} \frac{\det(M)^2 \cdot (-1)^{\|M\|_0 - N}} {\prod_{i=1}^N\Big(\sum_{j=1}^N M_{i,j}\Big)\prod_{j=1}^N\Big(\sum_{i=1}^N M_{i,j}\Big)} = 1$$ where $$\|M\|_0 = \sum_{i,j} M_{i,j}$$ is the number of non-zero entry of $$M$$.

Weighted generalization

Note that the formula is also true when "positive weights" are associated to every coefficient. Let $$P$$ and $$Q$$ be two matrices with positive coefficients. Alternatively one can think of $$P$$ and $$Q$$'s coefficients to be indeterminates ($$P_{i,j} = x_{i,j}$$ and $$Q_{i,j} = y_{i,j}$$ for all $$i,j$$).

Let $$M \circ P$$ (resp. $$M \circ Q$$) be the elementwise product of $$M$$ and $$P$$ (resp. $$Q$$).

$$\sum_{M \in \mathcal M_N} (-1)^{\|M\|_0 - N} \cdot \frac{\det(P \circ M)} {\prod_{j=1}^N\sum_{i=1}^N [P \circ M]_{i,j}} \cdot \frac{\det(Q \circ M)} {\prod_{i=1}^N\sum_{j=1}^N [Q \circ M]_{i,j}} = 1$$

This version might help to understand how the sum does simplify. When $$P$$ and $$Q$$'s coefficients are indeterminates, the sum is a rational function which is identically equal to 1.

Here is some python code to check (empirically) my claim (slow when $$N > 4$$).

from sympy import Matrix, Symbol
from itertools import product
import random

N = 2
P = Matrix([random.randint(1,100) for _ in range(N*N)]).reshape(N,N)
Q = Matrix([random.randint(1,100) for _ in range(N*N)]).reshape(N,N)
print(P)
print(Q)

prettyprint = "= (-1)^%d * (%d / %d) * (%d / %d)"

result = 0
for p in product([0,1], repeat=N**2):
MP = Matrix(p).reshape(N, N).multiply_elementwise(P)
MQ = Matrix(p).reshape(N, N).multiply_elementwise(Q)
dP, dQ = MP.det(), MQ.det()
if dP * dQ != 0:
vP, vQ = 1, 1
for i in range(N):
vP *= sum(MP[:,i])
vQ *= sum(MQ[i,:])
val = (-1) ** (sum(p)-N) * dP * dQ / (vP * vQ)
print(p, val, prettyprint%(sum(p)-N, dP, vP, dQ, vQ))
result +=  val
print(result)


And for those of you who don't want to run this program, here is one output.

Matrix([[19, 33], [49, 7]])
Matrix([[11, 53], [7, 86]])
(0, 1, 1, 0) 1             = (-1)^0 * (-1617 / 1617) * (-371 / 371)
(0, 1, 1, 1) -77/1240      = (-1)^1 * (-1617 / 1960) * (-371 / 4929)
(1, 0, 0, 1) 1             = (-1)^0 * (133 / 133) * (946 / 946)
(1, 0, 1, 1) -817/3162     = (-1)^1 * (133 / 476) * (946 / 1023)
(1, 1, 0, 1) -77/2560      = (-1)^1 * (133 / 760) * (946 / 5504)
(1, 1, 1, 0) -2597/4352    = (-1)^1 * (-1617 / 2244) * (-371 / 448)
(1, 1, 1, 1) -42665/809472 = (-1)^2 * (-1484 / 2720) * (575 / 5952)
1


An easier/intermediate formula?

The two formula above are not entirely satisfying, because of the no-zero-row/column constraint in the sum.

Let $$\mathcal H_N$$ be the set of all $$N$$ by $$N$$ matrices, such that coefficient $$(i,j)$$ is either $$a_{i,j}$$ or $$b_{i,j}$$.

For all $$M \in \mathcal H_N$$, define $$A(M)$$ to be the number of $$a_{i,j}$$ coefficients in $$M$$.

Intuitively, $$\mathcal H_N$$ is an hypercube and $$(-1)^{A(M)}$$ tells you if you are on an even or an odd "level".

Let $$P$$ and $$Q$$ be two square matrices of size $$N$$, where $$P_{i,j} = x_{i,j}$$ and $$Q_{i,j} = y_{i,j}$$.

$$\sum_{M \in \mathcal H_N} (-1)^{A(M)} \cdot \frac{\det(P \circ M)} {\prod_{j=1}^N\sum_{i=1}^N [P \circ M]_{i,j}} \cdot \frac{\det(Q \circ M)} {\prod_{i=1}^N\sum_{j=1}^N [Q \circ M]_{i,j}} = 0$$

Which means that the sum on the odd and even "levels" of the hypercube are equal.

I believe this formula might be easier to prove, because of additionnal symmetries. Sam Hopkins' idea to use a sign reversing involution (see comment) might be helpful.

And perhaps it is a first step towards one of the formula above (where we need to subtract the terms with a row/column of $$a$$'s).

Here is some python code to check (empirically) my claim (slow when $$N > 4$$).

from sympy import Matrix
from itertools import product
import random

prettyprint = "= (%d / %d) * (%d / %d)"
def getVal(v):
global P, Q, prettyprint
MP = Matrix(v).reshape(N, N).multiply_elementwise(P)
MQ = Matrix(v).reshape(N, N).multiply_elementwise(Q)
dP, dQ = MP.det(), MQ.det()
if dP * dQ == 0: return 0
vP, vQ = 1, 1
for i in range(N):
vP *= sum(MP[:,i])
vQ *= sum(MQ[i,:])
val =  dP * dQ / (vP * vQ)
print(val, prettyprint%(dP, vP, dQ, vQ))
return val

N = 2
H = [[random.randint(1,100) for _ in range(2)] for i in range(N*N)]
P = Matrix([random.randint(1,100) for _ in range(N*N)]).reshape(N,N)
Q = Matrix([random.randint(1,100) for _ in range(N*N)]).reshape(N,N)
print(H)
print(P)
print(Q)

result = 0
for p in product([0,1], repeat=N**2):
print(p, end=" ")
v = [ H[i][x] for i,x in enumerate(p)]
result += getVal(v) * (-1) ** int(sum(p))
print(result)


And for those of you who don't want to run this program, here is one output.

[[9, 52], [11, 59], [14, 41], [34, 93]]
Matrix([[26, 19], [46, 29]])
Matrix([[83, 21], [36, 24]])
(0, 0, 0, 0) 164595168/4703083825       = (96128 / 1049210) * (493128 / 1290960)
(0, 0, 0, 1) 445610545/3950948198       = (496502 / 2551468) * (1550880 / 2675808)
(0, 0, 1, 0) -24390009/3154893688       = (-163450 / 2533400) * (268596 / 2241576)
(0, 0, 1, 1) 727415911/51716164040      = (236924 / 6160720) * (1326348 / 3626424)
(0, 1, 0, 0) 5083920/3367826693         = (-491200 / 1849946) * (-14904 / 2621520)
(0, 1, 0, 1) -54813491/10541005478      = (-90826 / 3352204) * (1042848 / 5433696)
(0, 1, 1, 0) 601772499/5328265880       = (-1883482 / 4466840) * (-1219212 / 4551912)
(0, 1, 1, 1) 4820101/1199800856         = (-1483108 / 8094160) * (-161460 / 7364088)
(1, 0, 0, 0) 42513838767/149126935925   = (1198476 / 2385220) * (3405432 / 6002040)
(1, 0, 0, 1) 116044834723/250555941884  = (3511748 / 5800376) * (9516888 / 12440592)
(1, 0, 1, 0) 24887838735/336049358857   = (938898 / 3869410) * (3180900 / 10421724)
(1, 0, 1, 1) 419726686285/2203457293574 = (3252170 / 9409628) * (9292356 / 16860276)
(1, 1, 0, 0) 67073493/1168097623        = (611148 / 4205572) * (2897400 / 7332600)
(1, 1, 0, 1) 18295610183/80432973676    = (2924420 / 7620728) * (9008856 / 15198480)
(1, 1, 1, 0) -545598897/35835002665     = (-781134 / 6822466) * (1693092 / 12732060)
(1, 1, 1, 1) 166078396717/3536747545430 = (1532138 / 12362684) * (7804548 / 20597940)
0


[Edit 05/20] I realized that the formula is true with two different weights (before we had $$P = Q$$). The description has been updated accordingly.

[Edit 05/24] I included Timothy Chow's remark (we can choose $$P$$ and $$Q$$'s coefficients to be indeterminates, and get a rational function identically equal to 1).

[Edit 05/24] I updated the description of the basic version to adress Brendan McKay's comment. Before the set $$\mathcal M_N$$ was (awkwardly) defined as the set of invertible 0-1 matrices.

[Edit 05/25] I included a new formula, which might be an easier/intermediate step.

• The invertibility in the basic version is a red herring and it would look simpler using the no-zero-rows/columns condition there too. Also, testing the basic version for $n$ up to 7 would be easy and for $n=8$ doable. I can do it after a few days if nobody solves it by then. – Brendan McKay May 24 at 9:02
• A basic idea is to try to use a sign-reversing involution. – Sam Hopkins May 24 at 12:20
• I checked the basic version up to $n=8$. It took 6 hours. The estimate for $n=9$ is 1 year, so I won't do it. I also looked at the sums of the positive and negative terms separately, but they aren't even integer and I didn't notice anything interesting. Speaking of which, why should the value of the whole sum be integer? – Brendan McKay May 25 at 4:43
• A slightly smarter program takes 4 hours for $n=8$ with maybe 5 months estimate for $n=9$. I still won't do it, but if someone has bulk cpu time on their hands and nothing better to use it for I can provide the program. – Brendan McKay May 25 at 6:09
• What bothers me is that this identity looks like it should have a one line proof using the Jacobi residue formula or something like that, but I haven't been able to quite make it work. Perhaps someone more knowledgeable in complex functions in several variables can recognize this identity as a corollary of computing residues in two different ways? – Gjergji Zaimi May 27 at 16:25

This is a result of joint efforts with Fedor Petrov.

First, we show that the L.H.S. of the general version does not depend on $$P$$ and $$Q$$, and then we compute that constant for some properly chosen $$P$$ and $$Q$$. The elements of $$\mathcal M$$ are called admissible matrices.

Part 1. We show that the L.H.S. does not depend on $$P_{11}$$ and $$Q_{11}$$; the rest is similar.

Perform the following transform. In each matrix $$P\circ M$$, add to the first row all other rows (the determinant does not change) --- denote the resulting matrix by $$(P\circ M)^r$$. Then expand the determinant of $$(P\circ M)^r$$ by the first row; for this purpose, denote by $$(P\circ M)^r_{[ij]}$$ the cofactor of $$(P\circ M)^r_{ij}$$. The profit is that in each summand, one of the factors in the denominator cancels out. Notice here that $$(P\circ M)^r_{[1j]}=(P\circ M)_{[1j]}$$.

Perform the same with the columns of $$Q\circ M$$, denoting by $$(Q\circ M)^c$$ the matrix obtained by adding all columns to the first one.

We get $$\sum_{M \in \mathcal M_N} (-1)^{\|M\|_0 - N} \cdot \frac{\det(P \circ M)} {\prod_{j=1}^N\sum_{i=1}^N (P \circ M)_{ij}} \cdot \frac{\det(Q \circ M)} {\prod_{i=1}^N\sum_{j=1}^N (Q \circ M)_{ij}}\\ =\sum_{M \in \mathcal M_N} (-1)^{\|M\|_0 - N} \cdot \frac{\det(P \circ M)^r} {\prod_{j=1}^N(P\circ M)^r_{1j}} \cdot \frac{\det(Q \circ M)^c} {\prod_{i=1}^N(Q\circ M)^c_{i1}}\\ =\sum_{M \in \mathcal M_N} (-1)^{\|M\|_0 - N} \cdot \sum_{s=1}^N \frac{(P\circ M)^r_{1s}(P\circ M)^r_{[1s]}} {\prod_j(P\circ M)^r_{1j}} \cdot \sum_{t=1}^N \frac{(Q\circ M)^c_{t1}(Q\circ M)^c_{[t1]}} {\prod_i(Q\circ M)^c_{i1}}\\ =\sum_{s=1}^N\sum_{t=1}^N \Sigma_{st},$$ where $$\Sigma_{st}=\sum_{M \in \mathcal M_N} (-1)^{\|M\|_0 - N} \cdot \frac{(P\circ M)_{[1s]}} {\prod_{j\neq s}(P\circ M)^r_{1j}} \cdot \frac{(Q\circ M)_{[t1]}} {\prod_{i\neq t}(Q\circ M)^c_{i1}}. \qquad\qquad(*)$$ In fact, we show that none of the $$\Sigma_{st}$$ depends on $$P_{11}$$ or $$Q_{11}$$.

If $$s=t=1$$, this is clear: in this case no term in $$(*)$$ depends on those entries.

Assume now that $$(s,t)\neq (1,1)$$. The only part in a summand in~$$(*)$$ which depends on $$m_{ts}$$ is its sign. So we may pair up the matrices differing in the $$(t,s)$$th entries: the sum of corresponding terms is $$0$$. There is an exception, when $$m_{ts}$$ is the unique non-zero element in the $$t$$th row or in the $$s$$th column of $$M$$: in this situation the pair is not admissible. We consider the first case; the second is similar.

If $$t>1$$ (and $$m_{ts}$$ is the unique non-zero is the $$t$$th row), then $$(P\circ M)_{[1s]}=0$$, so the term vanishes.

Assume that $$t=1$$ (and hence $$s>1$$). Then $$(P\circ M)^r_{11}$$ does not depend on $$P_{11}$$, as $$m_{11}=0$$. Hence the term does not depend on $$P_{11}$$. Also, it clearly does not depend on $$Q_{11}$$. This finishes part 1.

$$\\$$

$$\let\eps\varepsilon$$ Part 2. It remains to compute the value of the L.H.S. for some pair of matrices $$P$$ and $$Q$$. We set $$P_{ij}=Q_{ij}=\eps^{i+j}$$ and check the limit of the L.H.S. as $$\eps\to+0$$.

In this case, the only term in the expansion of $$\det(P\circ M)$$ that counts is the product of the topmost nonzero elements in all columns (if this term exists in that expansion). Indeed, this term, when divided by $$\prod_{j=1}^N(P\circ M)^r_{1j}$$, tends to $$\pm1$$, while all other terms tend to $$0$$.

Hence, we are interested only in those matrices $$M\in\mathcal M$$ in which the topmost $$1$$s of the columns stand in different rows, and, similarly, the leftmost $$1$$s of the rows stand in different columns. Call these matrices good.

Take any good matrix. In contains the unique $$1$$ in the first row (say, $$m_{1s}=1$$) and the unique $$1$$ in the first column (say, $$m_{t1}=1$$). If $$s,t>1$$, then $$\lim_{\eps\to+0}\frac{\det(P \circ M)} {\prod_{j=1}^N(P\circ M)^r_{1j}} \cdot \frac{\det(Q \circ M)}{\prod_{i=1}^N(Q\circ M)^c_{i1}}$$ does not depend on $$m_{ts}$$, so we may again pair up such (good!) matrices differing in the $$(t,s)$$th entry; the sum of the corresponding two terms is $$0$$.

Otherwise, $$s=t=1$$, and we know the first row $$[1,0,\dots,0]$$ and the first column $$[1,0,\dots,0]^T$$ of $$M$$. Consider now the unique ones in the second row/column, and proceed in the same way further. At the end, the only unpaired good matrix will be $$M=I$$, for which the limit is $$1$$. Hence, the sought value is $$1$$ as well.

• If this answer gets a positive credit, is there a way to share it with Fedor? – Ilya Bogdanov May 26 at 21:12
• Impressive, thank you! As it expires in less than 2h, I directly clicked on "award the bounty". Now I'll carefully read the answer, and accept it in a few hours ;-) – Simon Mauras May 27 at 6:43