Given a matrix $n \times m$, I want to find the submatrices $a \times m$ by selecting $a$ columns such that their rank is minimal. Can this problem be solved efficiently?
$\begingroup$
$\endgroup$
5
-
2$\begingroup$ Selecting one arbitrary column gives you rank 1. $\endgroup$– Alexandre EremenkoCommented Nov 7 at 0:09
-
$\begingroup$ Do you want to find one submatrix of all submatrices $a \times m$ with smallest rank? Is $a$ fixed too? $\endgroup$– Christophe LeuridanCommented Nov 7 at 8:12
-
1$\begingroup$ What's the size of $a$ compared to $n$? I haven't thought of this much, but it has an LWE/code decoding feel, so I'm not very hopeful $\endgroup$– Daniel WeberCommented Nov 7 at 9:30
-
$\begingroup$ In a previous comment, now deleted, I said that the number of columns is fixed. I meant the number of row, that is $a$. $\endgroup$– AlmCommented Nov 7 at 9:36
-
$\begingroup$ Let me say that a is between square root of n and n/2. $\endgroup$– AlmCommented Nov 7 at 9:40
Add a comment
|