# Number of basis representations of Boolean vectors

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.

-

## 1 Answer

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.

-
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