# Why do XOR and other operators on binary variables qualify as linear?

I never fully understood why is the operation $\oplus: \{0,1\}^n \times \{0,1\}^n \mapsto \{0,1\}^n$ considered linear ? I am well aware of the definition of linearity on real numbers, and I understand the intuition behind this fact, but could one give me a sketch of proof why this is the case ?

Is it also the case for other operations on binary data such as:

• bitwise-OR $\vee: \{0,1\}^n \times \{0,1\}^n \mapsto \{0,1\}^n$
• truncated addition: $+: \{0,1\}^n \times \{0,1\}^n \mapsto \{0,1\}^n$ (i.e., $a+b \mod 2^n$)
• Hamming-weight: $H: \{0,1\}^n \mapsto \{0,\dots, n\}$
-
Linear over $\Bbb{F}_2$ = additive (= takes sums to sums). And bitwise XOR is the same as addition modulo two. – Jyrki Lahtonen Dec 3 '13 at 13:57
@JyrkiLahtonen: Thanks for the comment. I know that XOR is addition mod 2, and this is why I understand it intuitively, but can you give me a mathematical reasonning ? And what do you mean by "takes sums to sums" ? do you refer to the fact that $f(x+y)=f(x)+f(y)$? In this case I don't know how that would translate for binary operators? – doc Dec 3 '13 at 14:06

For any field $K$, vector addition in $K^n$ can be viewed as a map $p:K^{2n}\cong K^n\times K^n\to K^n$, and as such it is a linear map, whose $n\times2n$ matrix has block form $(I_n~~I_n)$. Indeed one easily checks that $p((u,v)+(x,y))=p(u+x,v+y)=u+x+v+y=p(u,v)+p(x,y)$, and compatibility with scalar multiplication is verified similarly (but it is trivial for $K=\Bbb F_2$).

This applies in particular for $K=\Bbb F_2$, in which $p$ is bitwise-XOR. But neither bitwise-OR nor addition modulo $2^n$ satisfy this compatibility with addition in $K^{2n}$. (Indeed every symmetric linear function $f:K^n\times K^n\to K^n$ satisfies $f(v,v)=f(v,0)+f(0,v)=2f(v,0)=0$ for all $v\in K^{2n}$, since $2=0$ in $\Bbb F_2$, but this holds neither for bitwise-XOR nor for addition modulo $2^n$, while both are symmetric.) As for Hamming weight, it takes values in $\Bbb Z$, which is not even a $\Bbb F_2$-vector space; the notion of linearity makes no sense in this context.

-
Ok I think I got the idea. But so, why are permutations over $\mathbb{F}_2^n$ considered linear ? For instance, consider the data-dependent rotation $Rot(x,y):\mathbb{F}_2^n \times \mathbb{Z}_n \mapsto \mathbb{F}_2^n$ which consists in a circular left shift of $x$ by $y$ positions. Is it linear in $x$ ? – doc Dec 3 '13 at 15:50
Yes bit permutations are linear in a fairly trivial way. Their matrices are permutation matrices. Note that these are linear maps $\Bbb F_2^n\to\Bbb F_2^n$. – Marc van Leeuwen Dec 3 '13 at 17:01