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

**ymar** · October 22nd 2011, 08:47 AM

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.

**Drexel28** · October 22nd 2011, 09:55 AM

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.

**ymar** · October 22nd 2011, 10:01 AM

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.

**ymar** · October 22nd 2011, 10:50 AM

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

**ymar** · October 23rd 2011, 02:50 AM

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.

**salim** · October 23rd 2011, 04:58 AM

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.

**salim** · October 23rd 2011, 05:06 AM

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)

**ymar** · October 23rd 2011, 05:21 AM

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

**salim** · October 23rd 2011, 06:06 AM

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

**ymar** · October 23rd 2011, 06:29 AM

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.

**Deveno** · October 23rd 2011, 07:43 AM

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.

**ymar** · October 23rd 2011, 08:01 AM

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.

**ymar** · October 23rd 2011, 08:18 AM

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

Proposition Every Boolean semimodule U has a unique basis.

It's here.

**Deveno** · October 23rd 2011, 08:38 AM

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.

**ymar** · October 23rd 2011, 08:53 AM

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.

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

LinkBack

Thread Tools

Display

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Similar Math Help Forum Discussions

"Mixture" and "Distance, Speed, and Time" Word Problems

a "well-known" result in shannon's paper "A mathematical theory of communication"

Ellipse: extract "minor axis" (b) when given "arc length" and "major axis" (a)

Definition clarification: "state-space", "support" and "sample space"

[SOLVED] Matlab symbolic "solve" gives unknown parameter "z"

Search Tags