2
$\begingroup$

In a finite field $q$, $M$ is an $m\times K$ matrix, where $m$U$ is a sub-space spanned by the row vectors of $M$. $A$ is a $4\times K$ matrix which consists of four non-zero row vectors $a$, $b$, $c$, $d$. Assume we've already known that there always exists at least one $u\in U$ which makes the four inequalities hold simultaneously. I need to find a vector $u\in U$ such that the cardinality (number of non-zero elements) of $u$ is minimized, meanwhile, $au\neq 0$, $bu\neq 0$, $cu\neq 0$ and $du\neq 0$ (inner product) hold simultaneously.

i.e.

minimize $\text{card}(u)$

subject to

$au\neq 0$, $bu\neq 0$, $cu\neq 0$, $du\neq 0$, $u\in U$

How can I solve such a problem?

Thanks.

  • 0
    There is nothing in the question saying $A$ can't be the zero matrix, and if it is then you won't get even one of your four inequalities, let alone all four. Please rethink your question and see what additional hypotheses it might need in order for it to be a sensible question.2011-08-19
  • 0
    Thanks for your comments. I've aleady updated the question.2011-08-19
  • 0
    It seems like a very difficult problem~~ mark2011-08-23
  • 0
    @Bruce Lau: I have converted your answer to a comment. *Answers should be reserved for posts that answer the question.* But because you do not have 50 reputation points yet, [you can only comment on your own questions and answers](http://meta.stackexchange.com/questions/19756/how-do-comments-work/19757#19757). So, you didn't do anything wrong; the "add comment" button will only appear for you once you gain 50 points. Here is an [explanation of reputation points](http://meta.stackexchange.com/questions/7237/how-does-reputation-work/7238#7238).2011-08-23
  • 0
    The problem is still not solved. Can somebody help me?2011-08-31
  • 0
    @Eric: I have converted your answer to a comment. *Answers should be reserved for posts that answer the question.* If you want to bring your question to the front page again so that more people will see it, you can do so by making any edit whatsoever to the body of the question. However, if you do this too many times, the question will go into Community Wiki mode and you won't get any reputation from it.2011-08-31

2 Answers 2