Número de funciones binarias lineales en un espacio vectorial

Question

Para $x,y\in\{0,1\}^n$ ,

deje $x\oplus y$ sea el elemento de $\{0,1\}^n$ obtenida por el componente exclusivo-o de $x$ y $y$ . Una función booleana $F : \{0,1\}^n\to\{0,1\}$ se dice lineal si $F(x\oplus y) = F(x)\oplus F(y),\forall x\ and\ y$ . Entonces, ¿cuál es el número de funciones lineales de $\{0,1\}^n$ a $\{0,1\}$ ?

P.D : Es fácil averiguar que el número total de la función binaria es $2^{2^n}$

Answer 1

SUGERENCIA: Supongamos que $F$ es lineal, y para $k=1,\ldots,n$ deje $e^k=\langle e_1^k,\ldots,e_n^k\rangle$ donde $$e_j^k=\begin{cases}1,&\text{if }j=k\\0,&\text{otherwise}\;.\end{cases}$$

Demuestra que $F$ está completamente determinada por sus valores en $E=\{e^1,\ldots,e^n\}$ lo que significa que si sabes $F(e^k)$ para cada $k\in\{1,\ldots,n\}$ entonces ya sabes $F(x)$ para todos $x\in\{0,1\}^n$ . ¿Cuántas maneras hay de determinar los valores de $F$ en $E$ ?

Answer 2

Sugerencia : Demostrar que el mapa $f \mapsto \bigl(f(e_1), \ldots, f(e_n)\bigr)$ asignación de funciones lineales $\{0,1\}^n \to \{0,1\}$ a sus valores en $e_1 = (1, 0,\ldots, 0)$ , $\ldots$ , $e_n = (0,\ldots, 0, 1)$ es una biyección.