8
$\begingroup$

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.

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
10
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Assuming I didn't make an embarrassing gaffe, always possible at 3am!, can we now leverage this into a result about equitable partitions? $\endgroup$
    – Brendan McKay
    May 16, 2012 at 16:59
  • $\begingroup$ Quite possibly. Do you want to refine the complexity landscape (determine which subproblems are easy and which are hard) or do you want some alternate characterizations of graphs that admit nontrivial eqquitable partitions? Gerhard "Ask Me About Problem Choices" Paseman, 2012.05.16 $\endgroup$
    – Gerhard Paseman
    May 16, 2012 at 17:11
  • 1
    $\begingroup$ 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. $\endgroup$
    – Aaron Meyerowitz
    May 16, 2012 at 19:20

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.