30
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Brendan McKay May 24 at 9:02
  • 2
    $\begingroup$ A basic idea is to try to use a sign-reversing involution. $\endgroup$ – Sam Hopkins May 24 at 12:20
  • 3
    $\begingroup$ 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? $\endgroup$ – Brendan McKay May 25 at 4:43
  • 3
    $\begingroup$ 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. $\endgroup$ – Brendan McKay May 25 at 6:09
  • 2
    $\begingroup$ 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? $\endgroup$ – Gjergji Zaimi May 27 at 16:25
10
+100
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ If this answer gets a positive credit, is there a way to share it with Fedor? $\endgroup$ – Ilya Bogdanov May 26 at 21:12
  • $\begingroup$ 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 ;-) $\endgroup$ – Simon Mauras May 27 at 6:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.