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.

  • 2
    $\begingroup$ 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. $\endgroup$ Jan 3 '13 at 6:53
  • $\begingroup$ 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. $\endgroup$ Jan 3 '13 at 9:33
  • $\begingroup$ My thought was that 3SAT would say NP complete, or do you want an efficient algorithm for small $N$? $\endgroup$ Jan 3 '13 at 10:20
  • 2
    $\begingroup$ 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. $\endgroup$ Jan 3 '13 at 14:44
  • $\begingroup$ I want small $N$, and I added an edit to this effect. $\endgroup$ 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.

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

  • $\begingroup$ How sad. Can we do better if $N$ is small. $\endgroup$ Jan 3 '13 at 18:19
  • $\begingroup$ If $N$ is bounded, inclusion-exclusion might well work. $\endgroup$ Jan 3 '13 at 18:21
  • $\begingroup$ 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? $\endgroup$ Jan 3 '13 at 18:32
  • 1
    $\begingroup$ 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". $\endgroup$ Jan 3 '13 at 19:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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