How do one solve a nonlinear combinatoric problem?

Question

I am an undergraduate CS student and I am struggling with a problem.

$Qx = b$ where $Q$ is a constant $m \times n$ matrix (with $m>n$), $x$ is a $n \times 1$ vector and $b$ is a $m\times 1$ vector.

I want to maximize the number of zeros in vector $b$.

subject to: $x(i)>0$ for $i=1,2, \ldots,n$

How do one tackle a problem like this ?

Answer 1

Here's a slow way to do it.

• Find a parametrization for $\operatorname{Nul} Q$, and see if it contains a positive vector (which is a matter of examining some inequalities that fall out of the parametrization). If so, this is such an $x$.
• Failing that, one at a time, check if each standard basis vector $e_i$ is in $\operatorname{Col} Q$. If it is, Find a parametrization of $Q^{-1}e_i$ (the preimage of $e_i$ - not implying that $Q$ is invertible here), and again see if it contains a positive vector. If so, this is such an $x$.
• Failing that, one at a time, find a parametrization of $Q^{-1}\operatorname{Span}(e_i,e_j)$, and again see if it contains a positive vector. If so, this is such an $x$.
• Continue with $Q^{-1}\operatorname{Span}(e_i,e_j,e_k)$, etc.

Answer 2

For any given subset $S$ of $\{1\ldots m\}$, making $b_j = 0$ for all $j \in S$ corresponds to solving $Q_S x = 0, x > 0$ where $Q_S$ is the submatrix of $Q$ corresponding to the rows in $S$. By homogeneity, if there is a solution there will be one with all $x_j \ge 1$. Linear programming software may be helpful.

Of course there may be a lot of subsets to consider. Fortunately, you didn't ask for an efficient solution.

Answer 3

Note that there is no guarantee that you will be able to create any zeros at all, for instance if all entries of $Q$ are strictly positive. So a first thing I would do is to forget about those coordinates $b_j$ that cannot ever be made zero, namely those for which row $j$ of $Q$ does not have both a positive and a negative entry (this includes the rows that are entirely zero, which are uninteresting for a different reason). Then for each remaining row you've got a linear equation in $x$ that gives the condition for that coordinate to become zero, and which is such that the hyperplane of its solutions meets the strictly positive cone given by $x_i>0$ for all $i$. Now the task is to find the largest collection of rows so that the intersection of their solution hyperplanes still meets that cone. You might search for sets of $n$ rows whose equations are linearly dependent, as that is a necessary condition for having a collection of at least $n$ coordinates that can be made zero simultaneously. It there are no sets of $n$ linearly dependent rows, then you just need to find the largest collection of at most $n-1$ rows whose intersection of hyperplanes meets the positive cone. If sets of $n$ linearly dependent rows do exist, you could check their intersection of hyperplanes, and see if it meets the positive cone; if it does you can get those $n$ coordinates to be zero, if it doesn't then that set of $n$ linearly dependent rows is not productive after all. You are probably left with a few productive $n$-tuples at best, which you might compare to see if even more than $n$ simultaneous zeros can be achieved.