Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

How does XOR qualify as a linear function?

  1. Oct 16, 2009 #1
    In computer science the XOR operation is a very important one, and I've heard XOR referred to as a "linear" function. My experience with linear functions (in the sense of vector spaces) has only been with functions in one variable, but XOR is a function of two.

    I know that we start by using the field [tex]F_2 = {0, 1}[/tex] in which addition is actually the XOR operation. So addition of two vectors from a vector space over that field (say, two 32-bit integers) is merely addition of the vectors using the field addition operation.

    So then the XOR operation on 32-bit integers isn't a special function so much as it is really just addition of 32-dimension vectors over [tex]F_2[/tex]. So what is the definition for the addition of two elements in a field to be linear, and how does the (XOR) addition over [tex]F_2[/tex] qualify as linear?

    I'm sure I've encountered these answers before, but I'm blanking at the moment. :-S
    Last edited: Oct 16, 2009
  2. jcsd
  3. Oct 16, 2009 #2
    We are talking about addition of vectors, not addition in a field. The set of 32-bit integers is viewed as a 32-dimensional vector space over the field with 2 elements. Then apply the definition of "linear transformation" from linear algebra to see what it means.
  4. Oct 16, 2009 #3
    But addition of vectors, by the definition of a vector space, is the dimension-by-dimension addition of the field elements, which uses the field addition.

    My problem is that, as far as I can find, a linear transformation is from one vector to another vector. XOR is from two vectors to one vector.
  5. Oct 20, 2009 #4
    I think the basic question here is: What is the definition of a linear function in two variables? Ie, if you have +: S×S → S, what must + satisfy to qualify as linear?

    I can only find examples of linear functions with one variable.
  6. Oct 20, 2009 #5


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    The might want to look up the terms "bilinear" and "multilinear"...or I could just explain them here. Let [itex]T:U\times U\rightarrow V[/itex], where U and V are vector spaces. T is said to be bilinear if, for each u in U, the functions [itex]x\mapsto T(x,u)[/itex] and [itex]x\mapsto T(u,x)[/itex] are both linear. (Note that they are functions from U into V) . Multilinear is the same thing, except that you're dealing with a function of more than two varibles. The most general situation would be when you're dealing with a function like [itex]T:U_1\times\cdots\times U_n\rightarrow V[/itex].

    Multiplication of complex numbers, the inner product on [itex]\mathbb R^n[/itex], and the cross product on [itex]\mathbb R^3[/itex], are good examples of bilinear maps.
    Last edited: Oct 20, 2009
  7. Oct 20, 2009 #6
    Ah, yes, that's what I was looking for. It slipped my mind. Thanks.

    So XOR is just addition of vectors over F_2 and satisfies the conditions of a bilinear map.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook