Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Suppose I have a basis $v_1, ..., v_n$ of boolean vectors and a boolean vector $v$ that was constructed by iterated $v = v_i$ $OR$ $v_j$ statements. I want a way to figure our how many unique combinations $v_I$, $I = \alpha_1,...,\alpha_k$, $\alpha_i \neq \alpha_j \forall i \neq j$ there are that, when union/or'd, yield $v$. The only thing I know about the basis vectors is that each basis vector has an entry that is true only for that basis vector, and false for all other basis vectors (note then that the vector $(TRUE,...,TRUE)$ has exactly one representation). The order of the basis vectors does not matter - I treat $v_i$ $OR...OR$ $v_j$ and $v_j$ $OR...OR$ $v_i$ equally. An analytic method is preferred but a polynomial-time algorithm would be great too. A polynomial-time algorithm for an upper bound for the number of basis representations (over the whole space) would be incredible, but if someone answered the main question I could probably do that on my own or with an optimization suite.

share|cite|improve this question
up vote 1 down vote accepted

For each i, let S(i) be the index of the bit that is set only in the i'th basis vector v_i

If V is the result of orring together some subset T of basis vectors, then for each i, the S(i)'th bit is set in V iff v_i is in T.

So for any vector V there is at most one such representation.

share|cite|improve this answer
Thanks. Do you have an answer for when the basis does not have that property? – Julien Clancy Aug 24 '12 at 6:26
My guess is that the answer will depend on the precise meaning of "basis" – dmuir Aug 24 '12 at 11:59
What do you mean? – Julien Clancy Aug 24 '12 at 12:08
Do you know anything about the v_i or are they an arbitrary collection of vectors? – dmuir Aug 24 '12 at 13:15
Essentially arbitrary. The vectors represent all the edge cuts of a graph, which in turn are formed through the disjoint union of basis vectors (the fundamental cuts) with the property I originally described. – Julien Clancy Aug 24 '12 at 15:25

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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