
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 elementwise conjunction?
The one from linear algebra (a linear combination can be zero only trivially) doesn't work  it's easy to give an example.

Re: a "basis" in {0,1}^n with operations induced from the boolean algebra {0,1}
Quote:
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 elementwise 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.

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.

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 linearalgebraic 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\}$

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.

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.

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)

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?

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???

Re: a "basis" in {0,1}^n with operations induced from the boolean algebra {0,1}
Quote:
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 twoelement 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.

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 3element linearly independent set necessarily spans a 3dimensional space.

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.

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.

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.

Re: a "basis" in {0,1}^n with operations induced from the boolean algebra {0,1}
Quote:
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.