Complexity of finding a 0-1 vector in a subspace or showing that there is none - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T05:58:51Z http://mathoverflow.net/feeds/question/97098 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/97098/complexity-of-finding-a-0-1-vector-in-a-subspace-or-showing-that-there-is-none Complexity of finding a 0-1 vector in a subspace or showing that there is none Aaron Meyerowitz 2012-05-16T08:37:05Z 2012-05-16T16:58:11Z <p>This question, is a slightly different disguise (see below), came up in discussions of <a href="http://mathoverflow.net/questions/96858" rel="nofollow">this question about equitable partitions</a></p> <p>A <em>$0,1$ vector</em> 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}.$ </p> <p>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?</p> <p>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. </p> <p>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.</p> http://mathoverflow.net/questions/97098/complexity-of-finding-a-0-1-vector-in-a-subspace-or-showing-that-there-is-none/97140#97140 Answer by Brendan McKay for Complexity of finding a 0-1 vector in a subspace or showing that there is none Brendan McKay 2012-05-16T16:58:11Z 2012-05-16T16:58:11Z <p>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.</p> <p>The famous <a href="http://en.wikipedia.org/wiki/Subset_sum_problem" rel="nofollow">SUBSET SUM</a> 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.</p>