# Check if a matrix is Zarankiewicz-maximal

My final-year project at the National University of Singapore is on Zarankiewicz's problem:

What is the maximum number of 1s in an $$\m×n\$$ binary matrix ($$\m\$$ rows and $$\n\$$ columns) with no $$\a×b\$$ minor (intersection of any $$\a\$$ rows and any $$\b\$$ columns) being all 1s?

For example, the matrix below contains a $$\3×3\$$ all-1 minor $$\begin{bmatrix} 0&(1)&1&(1)&(1)&1\\ 1&1&0&1&0&0\\ 0&(1)&0&(1)&(1)&0\\ 0&1&1&0&1&1\\ 1&1&0&0&0&1\\ 1&(1)&0&(1)&(1)&0 \end{bmatrix}$$ but this matrix contains no such minor – the intersection of any 3 rows and 3 columns always has at least one 0: $$\begin{bmatrix} 0&1&1&1&1&1\\ 1&0&0&1&1&1\\ 1&0&1&0&1&1\\ 1&1&0&1&0&1\\ 1&1&1&0&0&1\\ 1&1&1&1&1&0 \end{bmatrix}$$ Now any matrix with the maximum number of 1s is also maximal in the sense that adding another 1 anywhere in the matrix will create an $$\a×b\$$ minor. This task concerns itself with checking maximal matrices, not necessarily with the maximum number of 1s.

Given a non-empty binary matrix $$\M\$$ of size $$\m×n\$$ and two positive integers $$\a\$$ and $$\b\$$ where $$\a\le m\$$ and $$\b\le n\$$, determine whether $$\M\$$ has no $$\a×b\$$ all-1 minor, but has at least one such minor if any 0 in $$\M\$$ is changed to a 1. Output "true" or "false"; any two distinct values may be used for them. Formatting is also flexible for $$\M\$$.

This is ; fewest bytes wins.

## Test inputs

These are given in the form M a b.

"True" output:

[[0]] 1 1
[[0,1,1],[1,0,1],[1,1,0]] 2 2
[[0,1,0],[1,1,1],[0,1,0]] 2 2
[[1,1,0,1,0],[1,0,1,1,1],[0,1,1,0,1]] 2 3
[[1,1,1,1,1],[1,1,1,1,1],[1,0,0,0,0]] 3 2
[[0,1,1,1,1,1,1,1],[1,1,1,1,1,0,0,0],[1,1,1,0,0,1,1,0],[1,1,0,1,0,1,0,1],[1,1,0,0,1,0,1,1],[1,0,1,1,0,0,1,1],[1,0,1,0,1,1,0,1],[1,0,0,1,1,1,1,0]] 3 3
[[1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0],[1,1,1,1,0,0,0,0,1,1,1,1,0,0,0,0],[1,1,0,0,1,1,0,0,1,1,0,0,1,1,0,0],[1,1,0,0,0,0,1,1,0,0,1,1,1,1,0,0],[1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0],[1,0,1,0,0,1,0,1,0,1,0,1,1,0,1,0],[1,0,0,1,1,0,0,1,0,1,1,0,0,1,1,0],[1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,0],[0,1,1,0,1,0,0,1,0,1,1,0,1,0,0,1],[0,1,1,0,0,1,1,0,1,0,0,1,1,0,0,1],[0,1,0,1,1,0,1,0,1,0,1,0,0,1,0,1],[0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1],[0,0,1,1,1,1,0,0,1,1,0,0,0,0,1,1],[0,0,1,1,0,0,1,1,0,0,1,1,0,0,1,1],[0,0,0,0,1,1,1,1,0,0,0,0,1,1,1,1],[0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1]] 3 3


"False" output:

[[1]] 1 1
[[0,1,0,1,0],[1,0,1,0,1],[0,1,0,1,0]] 1 3
[[0,1,0],[0,1,0],[0,1,0]] 3 1
[[0,0],[1,1]] 2 2
[[0,0,0,0,0,1,1,1,1],[0,0,1,1,1,0,0,0,1],[0,1,0,0,1,0,0,1,0],[0,1,0,1,0,0,1,0,0],[0,1,1,0,0,0,0,0,0],[1,0,0,0,1,1,0,0,0],[1,0,0,1,0,0,0,1,0],[1,0,1,0,0,0,1,0,0],[1,1,0,0,0,0,0,0,1]] 2 2
[[0,1,1,1],[1,0,1,1],[1,1,0,1],[1,1,1,0]] 4 4
[[1,1,0,1,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,1],[0,1,1,0,1,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0],[0,0,1,1,0,1,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0],[0,0,0,1,1,0,1,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,1,1,0,1,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0],[0,0,0,0,0,1,1,0,1,0,0,0,0,1,0,0,0,0,0,1,0,0,0],[0,0,0,0,0,0,1,1,0,1,0,0,0,0,1,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,0,1,0,0,0,0,1,0,0,0,0,0,1,0],[0,0,0,0,0,0,0,0,1,1,0,1,0,0,0,0,1,0,0,0,0,0,1],[1,0,0,0,0,0,0,0,0,1,1,0,1,0,0,0,0,1,0,0,0,0,0],[0,1,0,0,0,0,0,0,0,0,1,1,0,1,0,0,0,0,1,0,0,0,0],[0,0,1,0,0,0,0,0,0,0,0,1,1,0,1,0,0,0,0,1,0,0,0],[0,0,0,1,0,0,0,0,0,0,0,0,1,1,0,1,0,0,0,0,1,0,0],[0,0,0,0,1,0,0,0,0,0,0,0,0,1,1,0,1,0,0,0,0,1,0],[0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,1,0,1,0,0,0,0,1],[1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,1,0,1,0,0,0,0],[0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,1,0,1,0,0,0],[0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,1,0,1,0,0],[0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,1,0,1,0],[0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,1,0,1],[1,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,1,0],[0,1,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,1],[1,0,1,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1]] 2 2


The fifth "false" test case is indeed false since flipping the $$\(4,5)\$$ entry from 0 to 1 does not make a $$\2×2\$$ minor.

• You can confirm that your fifth "False" solution is, indeed, false? When you change M[0][0] to 1, the intersection of rows (0, 5) and columns (0, 5) are all 1s. Feb 6 at 20:24
• @Ajax1234 It is indeed false – there is still no 2×2 minor after flipping M[4,5]. Feb 7 at 2:05
• May I input the matrix as an array of integers whose binary representation is each rows? For example, [[1, 0, 0, 0], [0, 1, 1, 1], [0, 1, 0, 1]] -> [8, 7, 5], as 8=1000(2), 7=0111(2), 5=0101(2).
– tsh
Feb 7 at 7:40
• @tsh I told you input was flexible, but if not a common method please specify the format used in the answer. Feb 7 at 7:42

# Python3, 175 bytes:

lambda m,a,b,z=lambda m:all(b>sum(map(all,zip(*s)))for s in combinations(eval(m),a)):z(M:=str(m))-any(z(M[:i]+'1'+M[i:])for i,c in enumerate(M)if"0"==c);from itertools import*


Try it online!

• z=lambda m,a,b:any(b<=sum(map(all,zip(*s)))for s in I.combinations(m,a))
– tsh
Feb 7 at 8:16
• (I:=i.span())[0], I[1] -> (I:=i.start()), I+1 -> (I:=i.end())-1, I -> str(m)[:(I:=i.end())]+'+1'+str(m)[I:]
– tsh
Feb 7 at 8:21
• not z(m,*c)and all(...) -> all(...)-z(m,*c)
– tsh
Feb 7 at 8:23
• 195 bytes: lambda m,a,b,z=lambda m:any(b<=sum(map(all,zip(*s)))for s in t.combinations(m,a)):all(z(eval(str(m)[:(I:=i.end())]+'+1'+str(m)[I:]))for i in re.finditer('0',str(m)))-z(m);import itertools as t,re
– tsh
Feb 7 at 8:33
• 175 bytes: lambda m,a,b,z=lambda m:all(b>sum(map(all,zip(*s)))for s in combinations(eval(m),a)):z(M:=str(m))-any(z(M[:i]+'1'+M[i:])for i,c in enumerate(M)if"0"==c);from itertools import*
– tsh
Feb 7 at 8:46

# R, 196166155149 135 bytes

Or R>=4.1, 107 bytes by replacing four function occurrences with \s.

Edit: -14 bytes thenks to @Giuseppe.

function(M,a,b,?=all)M==sapply(seq(!M),g<-function(i){M[i]=1;?!combn(nrow(M),a,function(x)combn(ncol(M),b,function(y)?M[x,y]))})?g(0)


Try it online!

Straightforward brute-force.

Takes advantage of redefining ?=all and operator precedence (? has the lowest and is both unary and binary operator).

• Feb 7 at 20:51
• @Giuseppe, aarghhh, forgot again!!! Feb 7 at 21:01

# J, 86 bytes

1=2#.1-((1 e.,@{@(<@(#~(-:~.)&>)@,@{@#"0;&i./@$)*/@,@{])"1 2],~$\$"1,1:[]}"{~[:I.1-,)


Try it online!

The 2 long test cases time out on TIO, so I've removed them.

• Creates a list of all 0-to-1 mutated versions of the input, with the input itself as the final element in that list.
• For each of those, checks for the required minor, using brute force, returning 1 if a minor is found, 0 otherwise.
• Swaps those zeros and ones
• Convert to a binary number
• Checks if the number is 1.
• This will only be true of every 0-to-1 mutation has the minor, but the input does not.

# Python 3, 176 bytes

lambda m,a,b:(z:=lambda m:all(b>sum(map(all,zip(*s)))for s in combinations(eval(m),a)))(M:=str(m))-any(z(M[:i]+'1'+M[i:])for i,c in enumerate(M)if"0"==c)
from itertools import*


Try it online!

Based on the Python answer by Ajax1234.

# JavaScript (ES6), 208 bytes

Returns $$\0\$$ or $$\1\$$.

Even though we don't have any combination built-in, this seems a bit too long. :-/

(m,a,b)=>(g=(v,n,C,i)=>i>>v.length||((h=i=>i&&i%2+h(i>>1))(i)^n||C(i))&&g(v,n,C,-~i))(m,a,p=>g(m[0],b,q=>m.some(X=Y=(r,y)=>r.some((v,x)=>p>>y&q>>x&~v&1?x-X|y-Y||![X=x,Y=y]:0))?1:(m[Y]||0)[X]+=2))&!/0/.test(m)


Try it online!

### Commented

(m, a, b) =>                 // m[] = binary matrix, a = rows, b = columns
( g = (v, n, C, i) =>        // g is a helper function:
i >> v.length || (         //   for each i >= 0 and less than 2 ** L,
( h = i =>               //   where L is the length of the vector v,
i && i % 2 + h(i >> 1) //   count the number of set bits in i
)(i) ^ n ||              //   if it's exactly equal to n:
C(i)                   //     invoke C(i)
)                          //
&& g(v, n, C, -~i)         //   keep going while the above is truthy
)(                           //
m, a,                      // outer call to g: pick the rows
p => g(                    // for each row bitmask p:
m[0], b,                 //   inner call to g: pick the columns
q =>                     //   for each column bitmask q:
m.some(X = Y =         //     initialize X and Y to non-numeric values
(r, y) =>              //     for each row r[] at position y in m[]:
r.some((v, x) =>     //       for each value v at position x in r[]:
p >> y &           //         if (x,y) belongs to a selected row
q >> x &           //         and a selected column
~v & 1 ?           //         and v is even:
x - X | y - Y || //           abort if (X,Y) is set and ≠ (x,y)
![X = x, Y = y]  //           otherwise set (X,Y) = (x,y)
:                  //         else:
0                //           do nothing
)                    //       end of inner some()
) ?                    //     end of outer some(); if truthy:
1                    //       do nothing
:                      //     else:
(m[Y] || 0)[X] += 2  //       add 2 to m[Y][X] (results in NaN if Y
//       is still non-numeric)
)                          //   end of inner call to g()
) &                          // end of outer call to g()
!/0/.test(m)                 // make sure that all 0's in m[] are gone


# Desmos, 247 241 bytes

B(n,i)=mod(floor(n/2^i),2)
P(n)=∑_{i=0}^nB(n,i)

f(L,w,h,a,b)=\{\sum_{X=0}^w\sum_{Y=0}^h\{0<\sum_{s=0}^{2^h-1}\sum_{t=0}^{2^w-1}\{P(t)=b,0\}\{P(s)=a,0\}\prod_{x=0}^w\prod_{y=0}^h\{B(t,x)B(s,y)=0,L[yw+x+1]=1,\{x=X\}\{y=Y\}=1,0\},0\}=0^L.\total\}


Extra newline needed for pasting of the piecewise inside f.

Takes input as a flattened list L, width&height w,h, and the a,b of the submatrices given in the problem.

Returns 1 for Zarankiewicz-minimal matrices, otherwise NaN.

Try it on Desmos! Takes too long for the larger test cases, so I commented them out.

Considering Desmos doesn't have 2d lists, combination built-in, or bit extract built-ins, this is decently good. Maybe the condition at the inside can be golfed (\{B(t,x)B(s,y)=0,L[yw+x+1]=1,\{x=X\}\{y=Y\}=1,0\}), or some conditions can be negated to simplify arithmetic, but I keep ending up longer.

## How it works

Since there's no combination built-in, we iterate over the powerset of rows+columns given by u in binary, then filter for those with hamming weight a and b respectively.

We have a big summation that gets compared with 0^L.\total (number of 0s). If the matrix already has an a×b submatrix, then every summand is 1, so the comparison is (w+1)(h+1)=total(1-L), which is always false. If the matrix does not have an a×b all-1s submatrix, then summands are 1 only for entries that are 0 and lead to an a×b all-1s submatrix when changed to 1. Hence the condition is met only if every 0 entry leads to an a×b all-1s submatrix when changed to 1.

I have since merged s and t into u as u=2^w*s+t for -5 bytes.

B(n,i): the i'th bit of n, where the 0th bit is the LSB
B(n,i)=mod(floor(n/2^i),2)
# P(n): hamming weight of n, the number of 1 bits
P(n)=∑_{i=0}^nB(n,i)

f(L,w,h,a,b)=\{
\sum_{X=0}^w\sum_{Y=0}^h # sum over all (X,Y)
\{  # does the matrix has an a×b all-1 minor if (X,Y) is changed to 1?
0<
\sum_{s=0}^{2^h-1}\sum_{t=0}^{2^w-1} # sum over powerset of rows and columns
\{P(t)=b,0\}\{P(s)=a,0\} # 1 if the number of rows = a and number of columns = b, so s,t defines an a×b submatrix
\prod_{x=0}^w\prod_{y=0}^h # for all entries (x,y) in the matrix, is the following true?
\{
B(t,x)B(s,y)=0, # (x,y) is not in the selected submatrix, or
L[yw+x+1]=1,    # the entry at (x,y) is 1, or
\{x=X\}\{y=Y\}=1, # (x,y)==(X,Y), so the entry is changed to 1
0
\},
0
\}
= 0^L.\total # is this sum equal to the number of 0s?
\}


## Proper rendering of f for +9 bytes

(I have not kept this up to date with the latest golfs)

B(n,i)=mod(floor(n/2^i),2)
P(n)=\sum_{i=0}^nB(n,i)

Q=\{B(t,x)B(s,y)=0,L[yw+x+1]=1,\{x=X\}\{y=Y\}=1,0\}
f(L,w,h,a,b)=\left\{∑_{X=0}^w∑_{Y=0}^hsign(∑_{s=0}^{2^h-1}∑_{t=0}^{2^w-1}0^{(P(t)-b)^2}0^{(P(s)-a)^2}∏_{x=0}^w∏_{y=0}^hQ)=total(1-L)\right\}

• I have no idea what's going on here but it's very impressive! May 8 at 23:05