# Thread: a "basis" in {0,1}^n with operations induced from the boolean algebra {0,1}

1. ## a "basis" in {0,1}^n with operations induced from the boolean algebra {0,1}

Let $\displaystyle u_1,...,u_n\in\{0,1\}^n$. Can we impose a condition on these vectors so that every vector $\displaystyle s\in\{0,1\}^n$ has a unique decomposition

$\displaystyle s=\alpha_1\cdot u_1\vee ... \vee\alpha_n\cdot u_n,$
where $\displaystyle \alpha_i\in\{0,1\},$ and by definition $\displaystyle \alpha\cdot \begin{pmatrix}x_1\\\vdots\\x_n\end{pmatrix}=$$\displaystyle \begin{pmatrix}\alpha\wedge x_1\\\vdots\\\alpha\wedge x_n\end{pmatrix} and \displaystyle \vee denotes element-wise conjunction? The one from linear algebra (a linear combination can be zero only trivially) doesn't work -- it's easy to give an example. 2. ## Re: a "basis" in {0,1}^n with operations induced from the boolean algebra {0,1} Originally Posted by ymar Let \displaystyle u_1,...,u_n\in\{0,1\}^n. Can we impose a condition on these vectors so that every vector \displaystyle s\in\{0,1\}^n has a unique decomposition \displaystyle s=\alpha_1\cdot u_1\vee ... \vee\alpha_n\cdot u_n, where \displaystyle \alpha_i\in\{0,1\}, and by definition \displaystyle \alpha\cdot \begin{pmatrix}x_1\\\vdots\\x_n\end{pmatrix}=$$\displaystyle \begin{pmatrix}\alpha\wedge x_1\\\vdots\\\alpha\wedge x_n\end{pmatrix}$ and $\displaystyle \vee$ denotes element-wise conjunction?

The one from linear algebra (a linear combination can be zero only trivially) doesn't work -- it's easy to give an example.
Could you explain more what you mean by "conjunction"? Evidently you don't mean addition modulo two otherwise $\displaystyle \{0,1\}^n$ is just a vector space over $\displaystyle \mathbb{Z}_2$ and trivially has a basis.

3. ## Re: a "basis" in {0,1}^n with operations induced from the boolean algebra {0,1}

Sorry! I meant logical disjunction. It's my English. Disjunction is called something different in Polish (unless someone really wants to sound smart) and I get confused all the time.

4. ## Re: a "basis" in {0,1}^n with operations induced from the boolean algebra {0,1}

I thought I'd add something. Let $\displaystyle e_i$ for i=1,...,n be defined in the usual way. Every vector $\displaystyle s\in\{0,1\}^n$ has a unique decomposition
$\displaystyle s=s_1\cdot e_1\vee ... \vee s_n\cdot e_n,$
which is easily proven. So it's not that there are no such bases. This one does actually satisfy the linear-algebraic independence condition, but $\displaystyle e_1,(e_1\vee e_2),(e_1\vee e_2\vee e_3)$ does too, in $\displaystyle \{0,1\}^3,$ and yet it doesn't yield unique decompositions.

edit: $\displaystyle s\in\{0,1\}^n$, and not $\displaystyle s\in\{0,1\}$

5. ## Re: a "basis" in {0,1}^n with operations induced from the boolean algebra {0,1}

If no one is replying because I wasn't clear enough, please tell me. I will try to make myself clearer.

Anyway, perhaps you could help me with my web search. I'm not sure if I'm using the correct terms. Is the structure $\displaystyle \left ( \{0,1\},\{0,1\}^n,\vee,\cdot\right )$ defined above a semimodule over the semiring $\displaystyle \left ( \{0,1\},\vee,\wedge \right )?$

Is there an unambiguous name for this semiring? I think it's called a boolean algebra, but I understand this term is ambiguous.

6. ## Re: a "basis" in {0,1}^n with operations induced from the boolean algebra {0,1}

hi,
first we must show that the space has dimension equal to n.
and then :
we know that every (n independent vectors) represent a base for the space. (the base have a property that every vector from a space can be writen uniquely withe the basis)
thus, the condition is : the vectors u(1) ... u(n) must be independent.

7. ## Re: a "basis" in {0,1}^n with operations induced from the boolean algebra {0,1}

let be,
$\displaystyle \left ( 1,0,...,0 \right )...\left ( 0,...,0,1 \right )$
n vectors from $\displaystyle \left \{ 1,0 \right \}^{n}$
we can easily proove that span the space $\displaystyle \left \{ 1,0 \right \}^{n}$
and are independent => the dimension equal (n)

8. ## Re: a "basis" in {0,1}^n with operations induced from the boolean algebra {0,1}

Salim, the problem is that this space is not a linear space. How do you define independence and dimension in this space?

9. ## Re: a "basis" in {0,1}^n with operations induced from the boolean algebra {0,1}

in the problem is set that s={1,0}^n is vector space?
can you tell me what are the (+,*) operations for this vector space???

10. ## Re: a "basis" in {0,1}^n with operations induced from the boolean algebra {0,1}

Originally Posted by salim
in the problem is set that s={1,0}^n is vector space?
can you tell me what are the (+,*) operations for this vector space???
It's not a vector space. (This is what I meant when I said that is is not a linear space.) A vector space is defined over a field. For example, {0,1} is a field when you define the addition as XOR (we denote it by $\displaystyle \oplus$ and the multiplication as AND (we denote it by $\displaystyle \wedge$), you get the two-element field. But in this case we do not have a field. While the multiplication is still defined to be AND, the addition is defined to be OR (we denote it by $\displaystyle \vee$), not XOR. In this case we do not get a field.

But we can define a space of "vectors" over this structure anyway. We can define addition of the "vectors". Let $\displaystyle (a_1,a_2,...,a_n)$ and $\displaystyle (b_1,b_2,...,b_n)$ be in $\displaystyle \{0,1\}^n$. We define

$\displaystyle (a_1,a_2,...,a_n)\vee (b_1,b_2,...,b_n)=(a_1 \vee b1 ,a_2 \vee b2,...,a_n\vee b_n)$

We can also define the multiplication $\displaystyle \cdot$ by scalars the following way. Let $\displaystyle (a_1,a_2,...,a_n)$ be in $\displaystyle \{0,1\}^n$. Let $\displaystyle \alpha$ be in $\displaystyle \{0,1\}$. We define

$\displaystyle \alpha \cdot (a_1,a_2,...,a_n)=(\alpha\wedge a_1,\alpha\wedge a_2,...,\alpha\wedge a_n)$.

So we just defined a "vector space" over our structure. It is not an actual vector space though, because our underlying structure isn't a field.

11. ## Re: a "basis" in {0,1}^n with operations induced from the boolean algebra {0,1}

as i think you have recognized ymar, the problem lies in the fact that you only have a boolean algebra, and not a vector space. in particular, {0,1} is not a group under $\displaystyle \vee$, because there is no inverse for 1. because of this peculiar behavior, linear independence is not a strong enough condition to guarantee the unique decompostion you seek.

i believe the structure you are after is "an idempotent semimodule", although "boolean semimodule" may also turn up some results for you.

a definition i saw of independence was: X is independent if $\displaystyle x \not\in M_{X\setminus\{x\}$ where $\displaystyle M_X$ is the set of linear combinations of X.

the trouble with your set $\displaystyle X = \{e_1,e_1 \vee e_2, e_1 \vee e_2 \vee e_3\}$ is that $\displaystyle M_X \neq \{0,1\}^3$, for example $\displaystyle e_2$ is not realizable as any linear combination:

$\displaystyle (0,1,0) = a(1,0,0) \vee b(1,1,0) \vee c(1,1,1) \implies$

$\displaystyle (0,1,0) = (a,0,0) \vee (b,b,0) \vee (c,c,c) \implies$

$\displaystyle (0,1,0) = (a \vee b \vee c, b \vee c, c) \implies c = 0$

$\displaystyle (0,1,0) = (a \vee b, b, 0) \implies b = 1$, but then $\displaystyle a \vee 1 = 1$.

this is in stark contrast to linear algebra where a 3-element linearly independent set necessarily spans a 3-dimensional space.

12. ## Re: a "basis" in {0,1}^n with operations induced from the boolean algebra {0,1}

Thank you, Deveno. This was very helpful. Especially the names of the structure! Now I see that there are lots of papers about it. I was about to believe that no one has tried to do research on them! I'll be looking at them and doing some thinking, and if I have any problems, I'll post here again.

13. ## Re: a "basis" in {0,1}^n with operations induced from the boolean algebra {0,1}

In case anyone's interested, I have found the following theorem:

Proposition Every Boolean semimodule U has a unique basis.

It's here.

14. ## Re: a "basis" in {0,1}^n with operations induced from the boolean algebra {0,1}

i think idempotent semimodule bases are unique up to scalability, so if the underlying semiring has only two elements, $\displaystyle \{e_1,e_2,...,e_n\}$ should be the only possible basis for $\displaystyle \{0,1\}^n$.

i did not see a proof in the link you posted, just the statement of it.

15. ## Re: a "basis" in {0,1}^n with operations induced from the boolean algebra {0,1}

Originally Posted by Deveno
i think idempotent semimodule bases are unique up to scalability, so if the underlying semiring has only two elements, $\displaystyle \{e_1,e_2,...,e_n\}$ should be the only possible basis for $\displaystyle \{0,1\}^n$.

i did not see a proof in the link you posted, just the statement of it.
I don't see it either. I'm going to try to prove it when I have some free time. Do you think I can manage? I'm after a first course in algebra.

Page 1 of 2 12 Last