Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

$C_i$ is a $k_i\times N$ matrix over finite field $\mathbb{F}_q$, where $i\in \{1,2,\ldots,K\}$, $k_i<N$, and $q<K$. My questions are 1) how to determine whether there is a $1\times N$ vector $\mathbf{v}$ in $\mathbb{F}_q$ which makes $\mathbf{v}C_i^T\neq \mathbf{0}$ hold for all $i$'s simultaneously, and 2) If there exists one, how to find it? Thanks.


The following is a reformulation of question (1) by Martin Sleziak.

$\mathbf{v}C_i^T=\mathbf{0}$ $\Leftrightarrow$ $\mathbf{v}\in \operatorname{Ker}(C_i^T)$

This means the question can be reformulated as: Is there a vector $\mathbf v$ such that $\mathbf{v}\notin \operatorname{Ker}(C_i^T)$ for $i=1,\dots, K$?

This is the same as asking whether $\mathbf{v}\in \mathbb F^q\setminus \operatorname{Ker}(C_i^T)$ for each $i$, i.e. $\mathbf{v}\in \bigcap_{i=1}^K (\mathbb F^q\setminus \operatorname{Ker}(C_i^T))=\mathbb F^q \setminus \bigcup_{i=1}^k \operatorname{Ker}(C_i^T)$.

So you are asking whether $\bigcup_{i=1}^k \operatorname{Ker}(C_i^T)$ is the whole space.

share|improve this question
    
$\mathbf{v}C_i^T=\mathbf{0}$ $\Leftrightarrow$ $\mathbf{v}\in \operatorname{Ker}(C_i^T)$. So you are in fact asking whether the linear sum $\operatorname{Ker}(C_1^T)+\operatorname{Ker}(C_2^T)+\dots+\operatorname{Ker}(C_‌​K^T)$ is the whole space $\mathbf (F_q)^N$. I do not see an easier approach as computing these kernels (which means solving system given by $C_i$ for each $i$) and then finding their linear span. Perhaps someone can come up with a cleverer idea. –  Martin Sleziak Nov 1 '11 at 8:11
    
Thanks for asking my question. Actually, I want to find a polynominal time algorithm. Is it possible? –  Leon Nov 1 '11 at 9:35
    
I should have said this:\\ $\mathbf{v}C_i^T=\mathbf{0}$ $\Leftrightarrow$ $\mathbf{v}\in \operatorname{Ker}(C_i^T)$\\ New reformulation: Is there a vector $\mathbf v$ such that $\mathbf{v}\notin \operatorname{Ker}(C_i^T)$ for all $i$?\\ This is the same as asking whether $\mathbf{v}\in \mathbb F^q\setminus \operatorname{Ker}(C_i^T)$ for each $i$, i.e. $\mathbf{v}\in \bigcap_{i=1}^K (\mathbb F^q\setminus \operatorname{Ker}(C_i^T))=\mathbb F^q \setminus \bigcup_{i=1}^k \operatorname{Ker}(C_i^T)$.\\ So you are asking whether $\bigcup_{i=1}^k \operatorname{Ker}(C_i^T)$ is the whole space. –  Martin Sleziak Nov 3 '11 at 8:57
    
See also this later question, which asks about the special case $k_i=1$. –  joriki Nov 3 '11 at 9:02

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.