Page 1 of 2 12 LastLast
Results 1 to 15 of 17

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

  1. #1
    Member
    Joined
    Feb 2011
    Posts
    147
    Thanks
    3

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21

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

    Quote Originally Posted by ymar View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Feb 2011
    Posts
    147
    Thanks
    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Feb 2011
    Posts
    147
    Thanks
    3

    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\}
    Last edited by ymar; October 22nd 2011 at 12:55 PM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Feb 2011
    Posts
    147
    Thanks
    3

    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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Oct 2011
    Posts
    9

    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.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Oct 2011
    Posts
    9

    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)
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member
    Joined
    Feb 2011
    Posts
    147
    Thanks
    3

    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?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Newbie
    Joined
    Oct 2011
    Posts
    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???
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Member
    Joined
    Feb 2011
    Posts
    147
    Thanks
    3

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

    Quote Originally Posted by salim View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,327
    Thanks
    701

    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.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Member
    Joined
    Feb 2011
    Posts
    147
    Thanks
    3

    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.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Member
    Joined
    Feb 2011
    Posts
    147
    Thanks
    3

    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.
    Follow Math Help Forum on Facebook and Google+

  14. #14
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,327
    Thanks
    701

    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.
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Member
    Joined
    Feb 2011
    Posts
    147
    Thanks
    3

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

    Quote Originally Posted by Deveno View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. Replies: 3
    Last Post: October 17th 2011, 02:50 PM
  2. Replies: 1
    Last Post: September 16th 2011, 01:08 AM
  3. Replies: 2
    Last Post: April 24th 2011, 07:01 AM
  4. Replies: 1
    Last Post: October 25th 2010, 04:45 AM
  5. Replies: 1
    Last Post: June 4th 2010, 10:26 PM

Search Tags


/mathhelpforum @mathhelpforum