# Tag Info

I will assume the original matrix has $n-1$ rows, $n$ columns, and the rows are linearly independent (this is easy to check; and if it is not the case, then the problem is trivial). Adding a new row $r$ will leave the matrix rank-deficient if and only if $r$ can be expressed as a linear combination of the existing $n-1$ rows. So, in a precomputation stage, ...
Based on the, apparently famous paper on the field, Ryser 56, and the thesis recommended by @orlp, the test to know if a row and column sum vectors forms a match, e.g., a matrix $M_{h,w}$ exists having these row and column sum vectors, is the following one: Let $R_h$ be a vector of $h$ elements sorted in a non-increasing order ($r_1\geq r_2\geq\ldots\geq ... 6 This problem is known as discrete tomography, and in your case two-dimensional discrete tomography. A nice approachable introduction is written Arjen Pieter Stolk's thesis Discrete tomography for integer-valued functions in Chapter 1. It gives a simple greedy algorithm for solving this problem: While the proof of theorem (1.1.13) is somewhat involved, the ... 4 The problem is NP-hard; it is at least as hard as the biclique problem. If you can solve the problem for a single shaped box, you can solve for all boxes by just iterating over all the boxes. So your problem reduces to: Given a matrix$M$and integers$h', w'$, find a$h'\times w'$submatrix of$M\$ that is all ones, or report that none exists. This ...