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](https://mathoverflow.net/questions/360651/sum-over-0-1-matrices#comment910624_360651)) was able to check its correctness up to $N=8$.


This question was first asked on [Maths StackExchange](https://math.stackexchange.com/questions/3653702) 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](https://oeis.org/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](https://mathoverflow.net/questions/360651/sum-over-0-1-matrices#comment910449_360651)) 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.



Sum over 0-1 matrices
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.


