In a finite field $q$, $M$ is an $m\times K$ matrix, where $m 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.
For a sub-space $U$, find $u\in U$ such that $\text{card}(u)$ is minimized and $Au\neq 0$
-
0There 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
-
0Thanks for your comments. I've aleady updated the question. – 2011-08-19
-
0It seems like a very difficult problem~~ mark – 2011-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
-
0The 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
Since everything is finite, you could just try all the vectors $\bf u$ of Hamming weight 1 (I've never seen the word cardinality used the way you use it; I think Hamming weight means what you mean by cardinality), then all the vectors of Hamming weight 2, etc., until you find one that works. Were you maybe after something more efficient? Do you have some reason to believe there is a more efficient method?
-
0Thanks for answering my question. I think your method works when the dimension $K$ is small. But this is just a toy example of my real problem. In fact, the dimension $K$ could be larger than 100. So, I think the computaion complexity is unaccepted. – 2011-08-19
-
0BTW, cardinality means Hamming weight here. It's defined as "the cardinality of $x\in R^n$, denoted card(x), is the number of nonzero components of x" in the 3rd slide of [link](http://www.stanford.edu/class/ee364b/lectures/l1_slides.pdf). – 2011-08-19
Here is a remark: if you were working over the reals and $U = {\mathbb R}^K$, your problem would be equivalent to the minimum hitting set problem:
MINIMUM HITTING SET: Given a collection of sets, find a set of the smallest possible size which intersects all of them.
Specifically, if we associate the $i$'th row $a_i$ of your matrix with the set $A_i$ of its nonzero entries, then the cardinality you would be asking for would be exactly the size of the minimum hitting set of the collection $A_i$.
Proof: suppose a vector $u$ exists with $a_i^T u \neq 0$ for all $i$. Let $U$ be the set of nonzero entries of the vector $u$. Then naturally $U$ and $A_i$ intersect - if they didn't, $a_i^T u$ would equal zero. So the optimal value you seek is at least the size of the minimum hitting set.
Conversely, suppose a hitting set $U$ of size $k$ existed. Let $u$ be the vector which takes the values of $0$ outside this hitting set, and generate the values on $U$ randomly from the uniform distribution at $[0,1]$. The probability that $a_1^T u = 0$ is zero, and consequently the probability that for at least one $i$, we have $a_i^T u = 0$ is zero. Thus a vector $u$ of cardinality $k$ satisfying your conditions exists.
I believe possible to modify this argument to work over a large enough finite field.
Minimum hitting set is NP-complete, by the way. However, because you have only four sets, you could solve this variation in linear time in $K$.
-
0Thanks for answering my question. I tried this way before. But I get stucked when solving the inequalities only considering the entries in the minimum hitting set. I don't know how to find such an $u$ which takes the values of $0$ outside the minimum hitting set. I mean, $u$ is a linear combination of row vectors of $M$. Sometimes such an $u$ even doesn't exist. For example:$ M=[1~1~0~0;0~0~0~1],A=[1~0~1~1;1~1~0~1]$. Obviously,I can find one minimum hitting set solution is $u_1=[x~0~0~0]$, where $x$ is non-zero. But it cannot be obtained by combining the row vectors of $M$. – 2011-08-20
-
0Then I have to relax the condition and select $u_1=[1~1~0~0]$ as the sub-optimal solution. However, there exists another minimum hitting set solution $u_2=[0~0~0~1]$, which is optimal. My point is, after I find a minimum hitting set, I don't know whether such an optimal solution can be obained or not by combining the row vecotors or $M$. Because I cannot find out all the minimum hitting set and try them one by one. – 2011-08-20