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