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 \$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.

Task

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 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×2\$ minor.

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!

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).

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