Given a matrix $M \in \mathbb{R}^{n \times m}$ and a set $S \subset \{1, \ldots, n\}$, let $M_{S, {\rm row}}$ be the matrix obtained by picking the rows of $M$ from the set $S$. Similarly, given $S' \subset \{1, \ldots, m\}$ we let $M_{S', {\rm col}}$ be the matrix obtained by picking the columns of $M$ in $S'$.

Now the problem is as follows. Given matrices $A, B, C$ what is $$ {\rm min}_{S \subset \{1, \ldots, n\}} ~~~~{\rm rank}~ \left( \begin{array}{cc} A & B_{S, {\rm col}} \\ C_{S^c, {\rm row}} & 0 \end{array} \right) $$

In other words, when you choose columns of $B$ corresponding to a set $S$, you have to choose rows of $C$ corresponding to the complement of $S$.

The dimensions here need to match in order for the question to make sense. In particular, we should have $A \in \mathbb{R}^{n \times n}, B \in \mathbb{R}^{n \times m}, C \in \mathbb{R}^{l \times m}$, and the $0$ in the lower-right-hand-corner has cardinality $|S| \times |S|$ depending on the set $S$.

This feels like it should be NP-hard but I'm having a lot of trouble coming up with a reduction.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.