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

2012-05-16T08:37:05Z

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.

Answer by Brendan McKay for Complexity of finding a 0-1 vector in a subspace or showing that there is none

2012-05-16T16:58:11Z

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.

The famous SUBSET SUM problem is known to be NP-complete. It asks whether a set of integers has a subset summing to 0 and is well known to be NP-complete. Requiring the integers to be even doesn't make it any easier (multiply a general instance by 2). That cooks the goose.

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

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

Answer by Brendan McKay for Complexity of finding a 0-1 vector in a subspace or showing that there is none