What is the definition of a $\mathbb{F}_2$-linear function?

73 Views Asked by At

To clarify, the function is $f:\mathbb{F}_2^m\rightarrow \mathbb{F}_2$. So, does it mean linear in each variable, or perhaps that each monomial is of degree $\leq1$?

I know that sometimes terms have multiple definitions (and are context dependent), but I suspect that here we have a consensus. In any case I'd like to hear the definition you are familiar with.

3

There are 3 best solutions below

0
On

$A$ is a linear map if for any vectors $v,w$ and any scalars $a,b$ we have $$A(av+bw)=aA(v)+bA(w)$$ The type of function you describe (linear in each variable) is called multilinear. A function $A:V_1\times V_2\times\cdots\times V_n\to W$ is called multilinear if for any index $i$, any vectors $v_1,v_2,\ldots,v_{i-1},v_{i,1},v_{i,2},v_{i+1},\ldots,v_n$, and any scalars $a,b$ we have $$A(v_1,v_2,\ldots,v_{i-1},av_{i,1}+bv_{i,2},v_{i+1},\ldots,v_n)=aA(v_1,v_2,\ldots,v_{i-1},v_{i,1},v_{i+1},\ldots,v_n)+bA(v_1,\ldots,v_{i-1},v_{i,2},v_{i+1},\ldots,v_n)$$

0
On

A map $$T: \Bbb V \to \Bbb W$$ between vector spaces $\Bbb V, \Bbb W$ over a field $\Bbb F$ is linear iff

  1. $T(v_1 + v_2) = T(v_1) + T(v_2)$ for all $v_1, v_2 \in \Bbb V$, and
  2. $T(\alpha v) = \alpha T(v)$ for all $\alpha \in \Bbb F$ and $v \in \Bbb V$.

In the special case that $\Bbb F = \Bbb F_2$, there are only two possible values for $\alpha$: The case $\alpha = 0$ gives $T(0) = 0$, but this follows from (1), as $T(0 + 0) = T(0) + T(0) = 0$ (the same holds over any field of characteristic $2$). On the other hand, the case $\alpha = 1$ gives the tautology $T(v) = T(v)$ (for all $v$).

Thus, in the case $\Bbb F = \Bbb F_2$, property (1) alone already characterizes linearity.


The particular given domain and codomain let us specialize further in an interesting way. A linear map $T: \Bbb V \to \Bbb W$ is characterized entirely by its values on a basis of $\Bbb V$, and any assignment of elements of such a basis to elements of $\Bbb W$ determines a linear map. In our case, $\Bbb V := \Bbb F_2^m$ has a canonical basis $(E_a)$, where $E_a$ is the element with $a$th entry $1$ and all other entries zero, and any linear map assigns each of these to element in $\Bbb W := \Bbb F_2$, that is, either $0$ or $1$. So, the linear maps $\Bbb F_2^m \to \Bbb F_2$ are precisely the maps $$T_I : (a_1, \ldots, a_m) \mapsto \sum_{i \in I} a_i,$$ where $I$ is a subset of $\{1, \ldots, m\}$, which defines a bijection $\text{Hom}(\Bbb F_2^m, \Bbb F_2) \leftrightarrow \mathcal{P}(\{1, \ldots, m\})$.

Remark Under this identification, the addition of linear maps corresponds to symmetric difference of subsets of $\{1, \ldots, m\}$; more precisely, $$T_{I_1} + T_{I_2} = T_{I_1 \triangle I_2},$$ where $\triangle$ is the symmetric difference operator, $X \triangle Y := X \cup Y - X \cap Y$. Incidentally, this shows---much more cleanly than a direct proof---that the symmetric difference operator is associative.

0
On

It means it is a linear homogeneous polynomial in the coordinates. As we're in $\mathbf F_2$, this means a sum of coordinates, e.g. $\; x_2+x_5+x_m$.