# Complexity of finding a 0-1 vector in a subspace or showing that there is none

This question, is a slightly different disguise (see below), came up in discussions of this question about equitable partitions

A $0,1$ vector in $\mathbb{Z}^n$ is any vector with all entries $0$ and $1$ (at least one of each.) This excludes (for temporary convenience) the all ones vector $\mathbf{1}.$

Q: Given a set of $k+1$ vectors in $\mathbb{Z}^n$, one being $\mathbf{1}$, How difficult is it to determine if there is a (rational) linear combination which is a $0,1$ vector?

It would be equivalent to say that we have a set of $k$ integer vectors such the $n$ entries of each vector sum to $0.$ We wonder if there is a linear combination having only two distinct entries.

In the context of the earlier question the $k$ vectors might be a basis for a certain eigenspace of (the adjacency matrix of) a given regular graph. A linear combination with only two distinct entries would indicate an intersetig two cell partition of the vertices of the graph. If the graph is connected then the largest eigenvalue is the common degree. Then the $k+1$ vector form of the question deals with a basis for the span of two eigenspaces.

-

It is NP-complete. Consider the case of $n$ vectors of length $n+1$, where the vectors are the rows of a matrix $[I | x]$ where $I$ is an $n\times n$ identity matrix and $x$ is a column vector of even integers. Any linear combination of the rows that is 0-1 must have multipliers 0 or 1 (due to the identity matrix part). So what we are asking is if there is a subset of the rows that sums to 0-1, i.e. is there a subset of the entries of $x$ that sums to 0 or 1. However the entries of $x$ are even, so the only possible sum is 0.
Nice! This might handle equitable partitions of multigraphs. These vectors don't look like eigenvectors of 0-1 matrices. Of course we could use $[I|B|x]$. For SUBSET the measure is likely to be $n^2+nk$ where the even entries are of size $2^k$. A graph that accommodated these as eigenvectors might have to have $O(2^k)$ vertices . That could shift the cost. – Aaron Meyerowitz May 16 '12 at 19:20