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

Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last
• Oct 22nd 2011, 08:47 AM
ymar
a "basis" in {0,1}^n with operations induced from the boolean algebra {0,1}
Let $u_1,...,u_n\in\{0,1\}^n$. Can we impose a condition on these vectors so that every vector $s\in\{0,1\}^n$ has a unique decomposition

$s=\alpha_1\cdot u_1\vee ... \vee\alpha_n\cdot u_n,$
where $\alpha_i\in\{0,1\},$ and by definition $\alpha\cdot \begin{pmatrix}x_1\\\vdots\\x_n\end{pmatrix}=$ $\begin{pmatrix}\alpha\wedge x_1\\\vdots\\\alpha\wedge x_n\end{pmatrix}$ and $\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.
• Oct 22nd 2011, 09:55 AM
Drexel28
Re: a "basis" in {0,1}^n with operations induced from the boolean algebra {0,1}
Quote:

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

$s=\alpha_1\cdot u_1\vee ... \vee\alpha_n\cdot u_n,$
where $\alpha_i\in\{0,1\},$ and by definition $\alpha\cdot \begin{pmatrix}x_1\\\vdots\\x_n\end{pmatrix}=$ $\begin{pmatrix}\alpha\wedge x_1\\\vdots\\\alpha\wedge x_n\end{pmatrix}$ and $\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 $\{0,1\}^n$ is just a vector space over $\mathbb{Z}_2$ and trivially has a basis.
• Oct 22nd 2011, 10:01 AM
ymar
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.
• Oct 22nd 2011, 10:50 AM
ymar
Re: a "basis" in {0,1}^n with operations induced from the boolean algebra {0,1}
I thought I'd add something. Let $e_i$ for i=1,...,n be defined in the usual way. Every vector $s\in\{0,1\}^n$ has a unique decomposition
$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 $e_1,(e_1\vee e_2),(e_1\vee e_2\vee e_3)$ does too, in $\{0,1\}^3,$ and yet it doesn't yield unique decompositions.

edit: $s\in\{0,1\}^n$, and not $s\in\{0,1\}$
• Oct 23rd 2011, 02:50 AM
ymar
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 $\left ( \{0,1\},\{0,1\}^n,\vee,\cdot\right )$ defined above a semimodule over the semiring $\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.
• Oct 23rd 2011, 04:58 AM
salim
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.
• Oct 23rd 2011, 05:06 AM
salim
Re: a "basis" in {0,1}^n with operations induced from the boolean algebra {0,1}
let be,
$\left ( 1,0,...,0 \right )...\left ( 0,...,0,1 \right )$
n vectors from $\left \{ 1,0 \right \}^{n}$
we can easily proove that span the space $\left \{ 1,0 \right \}^{n}$
and are independent => the dimension equal (n)
• Oct 23rd 2011, 05:21 AM
ymar
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?
• Oct 23rd 2011, 06:06 AM
salim
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???
• Oct 23rd 2011, 06:29 AM
ymar
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 $\oplus$ and the multiplication as AND (we denote it by $\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 $\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 $(a_1,a_2,...,a_n)$ and $(b_1,b_2,...,b_n)$ be in $\{0,1\}^n$. We define

$(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 $\cdot$ by scalars the following way. Let $(a_1,a_2,...,a_n)$ be in $\{0,1\}^n$. Let $\alpha$ be in $\{0,1\}$. We define

$\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.
• Oct 23rd 2011, 07:43 AM
Deveno
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 $\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 $x \not\in M_{X\setminus\{x\}$ where $M_X$ is the set of linear combinations of X.

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

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

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

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

$(0,1,0) = (a \vee b, b, 0) \implies b = 1$, but then $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.
• Oct 23rd 2011, 08:01 AM
ymar
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.
• Oct 23rd 2011, 08:18 AM
ymar
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.
• Oct 23rd 2011, 08:38 AM
Deveno
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, $\{e_1,e_2,...,e_n\}$ should be the only possible basis for $\{0,1\}^n$.

i did not see a proof in the link you posted, just the statement of it.
• Oct 23rd 2011, 08:53 AM
ymar
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, $\{e_1,e_2,...,e_n\}$ should be the only possible basis for $\{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.
Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last