Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.


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

share|improve this question
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

1 Answer 1

up vote 2 down vote accepted

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.

Over GF(2) is can be shown that finding a subspace of codimension two disjoint from the columns is equivalent to 4-coloring.

share|improve this answer
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
I'm afraid I don't know as many combinatorial algorithms as I probably should. How would you use inclusion-exclusion to calculate the subspace? –  Joseph Victor Jan 3 '13 at 18:32
I am not sure about getting an actual subspace. What I know about this is mostly what I learned from the material on the "critical exponent" in Aigner's book 'Combinatorial Theory". –  Chris Godsil Jan 3 '13 at 19:52

Your Answer


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

Not the answer you're looking for? Browse other questions tagged or ask your own question.