Check if a matrix is Zarankiewicz-maximal

Question

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

What is the maximum number of 1s in an ×ばつ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\$ 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.

Task

Given a non-empty binary matrix \$M\$ of size ×ばつ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 code-golf; 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\$ minor.

• Ajax1234: 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.
• Parcly Taxel: @Ajax1234 It is indeed false – there is still no 2×2 minor after flipping M[4,5].
• tsh: 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).
• Parcly Taxel: @tsh I told you input was flexible, but if not a common method please specify the format used in the answer.

Answer 1

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!

• tsh: z=lambda m,a,b:any(b<=sum(map(all,zip(*s)))for s in I.combinations(m,a))
• tsh: (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: not z(m,*c)and all(...) -> all(...)-z(m,*c)
• tsh: 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: 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*

Answer 2

R, (削除) 196 (削除ここまで) (削除) 166 (削除ここまで) (削除) 155 (削除ここまで) (削除) 149 (削除ここまで) 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).

• Giuseppe: combn does apply for you :-).
• pajonk: @Giuseppe, aarghhh, forgot again!!!

Answer 3

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.

Answer 4

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.

Answer 5

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

Answer 6

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\}

• Aiden Chow: I have no idea what's going on here but it's very impressive!