2
$\begingroup$

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.

$\endgroup$
5
  • 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, 2013 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, 2013 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, 2013 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, 2013 at 14:44
  • $\begingroup$ I want small $N$, and I added an edit to this effect. $\endgroup$ Jan 3, 2013 at 18:19

1 Answer 1

2
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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