How does XOR qualify as a linear function?

[B-Con]

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 F_2 = {0, 1} 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 F_2. So what is the definition for the addition of two elements in a field to be linear, and how does the (XOR) addition over F_2 qualify as linear?

I'm sure I've encountered these answers before, but I'm blanking at the moment. :-S

 

[g_edgar]

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.

 

[B-Con]

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.

 

[B-Con]

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.

 

[Fredrik]

The might want to look up the terms "bilinear" and "multilinear"...or I could just explain them here. Let T:U\times U\rightarrow V, where U and V are vector spaces. T is said to be bilinear if, for each u in U, the functions x\mapsto T(x,u) and x\mapsto T(u,x) 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 T:U_1\times\cdots\times U_n\rightarrow V.

Multiplication of complex numbers, the inner product on \mathbb R^n, and the cross product on \mathbb R^3, are good examples of bilinear maps.

 

[B-Con]

The might want to look up the terms "bilinear" and "multilinear"...or I could just explain them here. Let T:U\times U\rightarrow V, where U and V are vector spaces. T is said to be bilinear if, for each u in U, the functions x\mapsto T(x,u) and x\mapsto T(u,x) 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 T:U_1\times\cdots\times U_n\rightarrow V.

Multiplication of complex numbers, the inner product on \mathbb R^n, and the cross product on \mathbb R^3, are good examples of bilinear maps.

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.