TIFR CSE 2018 | Part B | Question: 10

Question

For two $n$ bit strings $x,y \in\{0,1\}^{n},$ define $z=x\oplus y$ to be the bitwise XOR of the two strings (that is, if $x_{i},y_{i},z_{i}$ denote the $i^{th}$ bits of $x,y,z$ respectively, then $z_{i}=x_{i}+y_{i} \bmod 2$). A function $h:\{0,1\}^{n} \to \{0,1\}^{n}$ is called linear if $h(x \oplus y  )=h(x)\oplus h(y),$ for every $x,y \in \{0,1\}^{n}.$ The number of such linear functions for $n \geq 2$ is:

• A. $2^{n}$
• B. $2^{n^{2}}$
• C. $\large2^{\frac{n}{2}}$
• D. $2^{4n}$
• E. $2^{n^{2}+n}$

Comments

is answer e

---

Correct option is B

Similar question is discussed here

https://gateoverflow.in/25046/tifr2012-b-1

---

This question can be solved easily by using concept that we used in below referenced question:-

https://gateoverflow.in/27351/tifr2014-b-18

This referenced question is difficult to understand but if you did then above question will be cake wake for you.

Answer 1

Here, $x,y$ are $n$ length binary strings.

If $n=2$, we have $x,y \in \{00, 01, 10, 11\}$

For a generic function mapping to $\{0,1\}^2$ we have $2^{2}=4$ options for each of the four $2$ bit strings thus giving $2^4 =16$ functions (in general $2^{2^2}).$ But here, our function must be linear.

Lemma: Once we assign values to $h(x)$ for all $x$ having exactly one $1,$ the other values are fixed.

For example, for $n=2$ we can only fix $h(01)$ and $h(10)$ and the remaining two values $h(00)$ and $h(11)$ are fixed as $h(00)$ must be $h(01) \oplus h(01) = 00$ and $h(11) = h(01) \oplus h (10).$

In this way for any $n$ we have only $n$ combinations possible from the domain set for a linear function instead of $2^n$ for a normal function. Here, each of these $n$ possible combinations can be mapped to any of the $2^n$ bit strings thus giving rise to $\left({2^n}\right)^n$ possible LINEAR functions which equals $2^{n^2}.$

Correct Option: B.

Comments

@Arjun sir

For $n=3$,

How to generate $h(111)?$

Do we need to use the $XOR$ operation three times like $h(100) \oplus h(010) \oplus h(001) = h(111)?$

---

when we have 4 options for each of the four 2 bit strings, won't total functions be $4^{4}$?

---

@akshay7797,  yes you are correct, it'll be 256