Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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\}$
share|improve this question
1  
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
1  
@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

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.