1
$\begingroup$

The problem takes as input an $m \times 2n$ matrix $A$ over $\mathbb{F}_2$.

Optimization version: find a subset of exactly $n$ columns so that the corresponding submatrix (taking only selected columns) has minimum rank over $\mathbb{F}_2$.

Decisional version: given the matrix $A$ and an integer $k$, is there a subset of $n$ columns of rank less than $k$ over $\mathbb{F}_2$.?

This problem seems NP-hard. The question is: why?

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.