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