= Linear Boolean function
{title2=$f_a(x)=a\cdot x$}
= Homogeneous linear Boolean function
{synonym}
A <linear Boolean function> is a <linear map> from $\mathbb F_2^n$ to $\mathbb F_2$. Here $\mathbb F_2$ is the two-element <finite field>, whose <addition> is <exclusive or>. Every such function has a unique coefficient <binary string> $a$ and takes the form
$$
f_a(x)=a\cdot x=\bigoplus_{j=1}^{n}a_jx_j.
$$
The dot is the <binary inner product>. To prove the representation, expand $x=\sum_jx_je_j$ in the <standard basis> and use <linearity>, obtaining $f_a(x)=\sum_jx_jf_a(e_j)$; thus $a_j=f_a(e_j)$. For example, $a=101$ gives $f_a(x)=x_1\oplus x_3$. Adding a nonzero constant produces an <affine map>, not a <linear map>.
Back to article page
