Consider the low-rank matrix completion problem: Given an integer $k$ and a subset of entries of some $n \times n$ matrix, fill in the rest of the entries so that the resulting matrix has rank at most $k$.This problem is clearly in NP, since the set of additional entries is the required certificate. Therefore, it can be written as an integer program. How can one do this? I'm having trouble seeing how to get rid of a rank constraint, even at the expense of adding integer constraints.
How to reduce the low-rank matrix completion problem to integer programming?
complexity theory;reductions;decision problem;matrices;integer programming