New answers tagged matrices
0
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, ...
1
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 ...
Top 50 recent answers are included
