# For a sub-space $U$, find $u\in U$ such that $\text{card}(u)$ is minimized and $Au\neq 0$

In a finite field $q$, $M$ is an $m\times K$ matrix, where $m<K<q$, $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.

-
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. –  Gerry Myerson Aug 19 '11 at 13:27
It seems like a very difficult problem~~ mark –  user14939 Aug 23 '11 at 14:07
@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. 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. –  Zev Chonoles Aug 23 '11 at 14:27
The problem is still not solved. Can somebody help me? –  Eric Aug 31 '11 at 11:39

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?

-
Thanks 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. –  Eric Aug 19 '11 at 18:26
BTW, 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. –  Eric Aug 19 '11 at 18:38

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$.

-
Thanks 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$. –  Eric Aug 20 '11 at 3:18
Then 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. –  Eric Aug 20 '11 at 3:19