# Finding a subspace disjoint from a union of subspaces

Let $k$ be a finite field (I care about $\mathbb F_p$, especially $\mathbb F_2$) and let $V_1,...,V_N\subset k^n$ be subspaces.
I want to find a subspace $S\subset k^n$ such that $S\cap V_i=0$ for each $i$, with $dim(S)$ as large as possible, and I want to do this in polynomial time (in exponential time we can try every possibility, as this is a finite vector space).

In $\mathbb{R}^n$ this is easy since if we pick $S$ randomly of dimension $n-\max dim(V_i)$ it will almost always be disjoint from the $V_i$. Of course, in a finite field you can fill up all of $k^n$ with just 1-dimensional $V_i$, so this approach fails.

Thanks

EDIT: What if $N\lt \lt n$, though $dim(V_i)$ can be around $n/2$ or so.

-
I wonder if one can encode 3SAT (satisfiability), but that is just a guess. In the special case that the $V_i$ all have dimension 1 (lines) it would be equivalent (in some sense) to find the largest dimension subspace completely covered by lines (the complementary set of one dimensional subspaces). Of course if you mean polynomial in $N$ that would be another matter. –  Aaron Meyerowitz Jan 3 '13 at 6:53
3Sat is probably a pretty easy way to do this, especially for Z/2, but boy is that unsatisfying. I'd rather have a nice lil algorithm. –  Joseph Victor Jan 3 '13 at 9:33
My thought was that 3SAT would say NP complete, or do you want an efficient algorithm for small $N$? –  Aaron Meyerowitz Jan 3 '13 at 10:20
The case where $k=\mathbb F_2$ was asked previously, at mathoverflow.net/questions/33035 . My answer there was essentially the last paragraph of Chris Godsil's answer here. –  Andreas Blass Jan 3 '13 at 14:44
I want small $N$, and I added an edit to this effect. –  Joseph Victor Jan 3 '13 at 18:19

Let $B$ be the oriented vertex-edge incidence matrix of a graph, viewed as a matrix over $GF(p)$. Let the subspaces $V_i$ be the 1-dimensional subspaces spanned by the columns of $B$. There is a subspace of codimension 1 disjoint from these subspaces if and only if there is a non-zero vector $a$ such that no entry of $a^TB$ is zero.
But the columns of $B$ are each of the form $e_i-e_j$, for an edge $ij$ of $G$, and we can view $a$ as a function on the vertices of $G$. The condition that no entry of $a^TB$ is zero is then equivalent to the condition that the map from a vertex to the corresponding entry of $a$ is a proper vertex-coloring with $p$ colors. Hence your problem is NP-hard.
How sad. Can we do better if $N$ is small. –  Joseph Victor Jan 3 '13 at 18:19
If $N$ is bounded, inclusion-exclusion might well work. –  Chris Godsil Jan 3 '13 at 18:21