[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](/questions/tagged/code-golf "show questions tagged '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]
# 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!](https://tio.run/##rVVLjqMwEF03p7DYYKfdLZP0YsSIuUHmAjQaOWlQW@IncEZKLp8x5ld2ILAYIbBdfq9c1M/VVX6XxeFHVd/T8POe8fz0xVFOOT3RWzgsA55l@PSrueQ45xVWK3oTFd41hJC0rFGDRIHOZX4SBZeiLBqc/OUZzgnlhAQ3fAzCRtZqTd54ccVKEAUifvV87/UYiSDWSgQ9t2qS4pInNZcJPhKRuswNwzP5mdZljoRMalmWmTour8pa7u7diHgjHVlf5Pc1dF03ilgcIx/5jppRn/oxjXzK@lHN1O4e7ftd1kvbXWbsauyI0JpGVKevRR56pD@eBOesexTyMJ4IHojvkYOE9ScOEja9o2SQ@cBCZkkmawd7xvO0VYb90JLpAVYOMmttWDQ7AoS9CxGMPnkBwt4zEVA/m/Ems3lwDSM8jwQIG2ki4K6lDyAWXo0wPW15ECAWxh4xEzGQgVa0rVzw@yxRheXoMm2LNBWZqkX8uywSirrKe2@qTEjsfRaeqnnnRfcQFCLdMBr5nrXVy7M/bWegSPRwQpyXqhaFxCnWDCXo1t6bt9sz4qQ8a5KrUtQaoFLVKG07LQy3auQBlLk5tr/V6emTE7SFeSdBB04nga8RVDamNbOLCrQGs/AnbY8Jz2YLiY2NCLSXqR1MzWNqLAr9gT5gg4P6Z@Z20m9iGMm5gTEm4kaGldqrDCPRNzCswlhlPBTSCmOh8BYZ8DrZwgD5uYkxxmsjA8RrE8OI1waGFa9VhuWfVcaDf1YYM/55ypj1zxPGgn8WGcb/bmBY/7vKsHrPKqPrQcu3RNfH/98tcf8H)
[Answer]
# [R](https://www.r-project.org/), ~~196~~ ~~166~~ ~~155~~ ~~149~~ 135 bytes
Or **[R](https://www.r-project.org/)>=4.1, 107 bytes** by replacing four `function` occurrences with `\`s.
*Edit: -14 bytes thenks to [@Giuseppe](https://codegolf.stackexchange.com/users/67312/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!](https://tio.run/##fVLLboMwELz3K5qbV9pKdkilVqnFF/jWWxQpBpUIiUBKEgVU9dvphjTGD0BeDPbMmNld110mu@xSpue8KplCjQnu4p3URQFKypM@HouWnb6@2UIB7j9eDDeHH7XJt1Ks40VaHZKSlXV1ZcTSaEgN/ENpVdygZIBaiNWmwXYL8AvxnnHoMnbQ5zpvWEorRIGfgM@CAp5siIDbMG@iRj11SRFQbfoM1VA8ST@T7PUhiwJZOPh9GFk0ZmxOOnw7Pjx3Y16ddEeRexneHsYoHyeh@cJPPiZX4ZeIW17dJkThH3qTRFhONZQ7FRJetQZL4Wyvud2miX2fb5/Cne5Yp5D19@m76F5c4bVk1QtXFND9AQ "R – 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]
# [J](http://jsoftware.com/), 86 bytes
```
1=2#.1-((1 e.,@{@(<@(#~(-:~.)&>)@,@{@#"0;&i./@$)*/@,@{])"1 2],~$$"1,1:`[`]}"{~[:I.1-,)
```
[Try it online!](https://tio.run/##dVLfS8MwEH7fX3G0YW0kze5aBa1OCsJA8El8G4WJrEwRBH88yLD/ek3apLmtypFLLvfd17svfekinTSwLCEBBQilWZmGm/u7VUfLPNaUpSnBVqtqX6VXVRq3aVa2Ws6vZWXv4ggv5896UQl5srA3tYwI8lq1QkSkqNysN/VPtG/X5a0hU7KTs@3T7g2Sh/evz913MkRkrAGlAYc4N9ZAYUyYjmwWzEK3038wdGkLQw4retiZgZHjwZExwPt4KCkcsy@hsQl@xsF8if3KuTEx8v5VOBQBi4i1jmwBQxyqEOqA4UMVsg5w5hRfPb5@TAQnHweJcCIRBkXdvR@ZJvof7/ylrBds/MPshTHhNWUDAIt8xvNzzzv0HphcyKRHJjy/Cxk@Pec7ZgtTnBprei/Yj8Wfjj@rOXe/ "J – 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]
# 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!](https://tio.run/##jVbbbqMwEH3PV1i81KRuZZo@rJDYP8gX0Dw4WdBa4ibsrtT8fNYQY8YTCBYC384ZD@Mz1nQ/@m/bHH51/a3Mvm6VqM9/BKmZYOeUXtNsmkhFVdHzb/Vd01p01IzYVXZ0r@I4LtueKCIbcmnrs2yElm2jaPFPVLSOmTAIekwzpXszjN9E80Ov9Jin8vT6kry8HnOZnkYbkl0GK0XzXRe90AU9xrKMeJRll3hX9m1NpC563baV2a3u2l7vb7pQ@iJUoUhGoija5Tk/nUhCkqHHEpacWJ4wblvTM6sf5MOucjs7rHJvdcQ6xGjJoe72BuTBIhO3E@zz@2OQB7cjeCDeIqcZbnecZvj8uplpLgEecjQzezv54/YbvfL8h57MD/BymkNjz6PFFiDwKkRw9uQFCLzmI6B9vhBNjnlwDE94GQkQGOkj4CqyBxAr74jwI40iCBArrUUsnBhQIDptpIXEqmSQiZdW@Ei8XxqRB5BifjuYvNuxwgApuewgdH7eCXy9gHInKY4FDdLST7rZ2qPY@KKIubsEQGrPqTgn7pzUBv1JPuHlAu0v9LHgghieMAIYTgSBDCSrTYYnsgAGEuUm40HEG4wV0a8y4FUewgD6DGK48wpkgPMKYnjnFcBA57XJQPHZZDzEZ4OxEJ@njMX4PGGsxGeV4f1vAAP97yYD3T2bDHsHmeLn3ZRYpiaL31VXSU2jryYydZMprPRQVrlKKd0R0vWy0bSk@6GYGyo1pi3LVGtEloZSVKog0VsU3/4D "Python 3.8 (pre-release) – Try It Online")
Based on [the Python answer](https://codegolf.stackexchange.com/a/242443) by [Ajax1234](https://codegolf.stackexchange.com/users/74571/ajax1234).
[Answer]
# 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!](https://tio.run/##XVHbbqMwEH3PV7iRltiqQ@2kT6nsPFTbH@hLIkolkjrEK24BFgWV7a9nJ8SAiSywfebMmZnjP0EVFPtcZ@U8Sb/U5SAuOKYB3REhcShwRRP6SjXctJSVG6kkLI9Ng/FRaMAcR/9aPB4xBDkhWJPPpGleYSeOE5rk@Q9cW9FMyBDHHvPpjp6EjN0ijRXeiK3AOa2hRn5DIPEMt0zK2jlJeXZ@Koevz/NNU8@3TfPgbcSZbkXtrxgha74Cza3fNIx4G/9RLKD4wxN7cktVlDgml1yd/upc4dmhmBE3V8HXm47Ue53sMSNumb6XuU5CTNwii3SJpx/JlLiHNP8d7I@4QEKi7wlCkSqRF1MUULTzkUCFoc8QiMZBhlUVROQFmPs0KdJIuVEK06I1OmCTRtAKTafA@UcuHtjgI474BE6UU@5Tj1NmdjhBdIEWJsoMeo2yUbTl9oxWqWfd9K7MpWHyvpJ9ZrcFzGVf0Vo23zA7hJmKHcKGr0c6jFsdsjtk6Lbrp6/XdrWcXAcYGTYemg3WmCTeDt2xxvtV8qZjGrfM7ha3rGT28FYl629X7/7WM/TLMnxs56B2P5mtd6c26pyPTR6eZHguYD@j5/8 "JavaScript (Node.js) – 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]
# [Desmos](https://desmos.com/calculator), ~~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!](https://www.desmos.com/calculator/b3qwdcj0qy) 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\}
```
]