I was reading an article that discusses a property testing algorithm for testing Singletons:
A function $f:\{0,1\}^n \rightarrow\{0,1\}$ is a singleton function if there exists $i\in[n]$ such that $f(x)=x_i$ or $f(x)=\bar x_i $ for every $x\in\{0,1\}^n$.
It is claimed that every linear function $f:(\mathbb Z_2) ^n\rightarrow \mathbb Z_2$ is a parity function, which means that there exists $S\subset[n]$ such that $f(x)=\bigoplus_{i\in S} x_i$ for every $x\in (\mathbb Z_2)^n$.
I don't understand why this is true, I think that it's somehow related to the way addition and subtraction are defined in $\mathbb Z_2$ field and how XOR function is defined (it is $1$ $\iff$ odd number of inputs equals $1$).
I would appreciate it if you can show a proof for this. Thanks.
$x=\sum_{i=1}^n e_i x_i$, where $e_i$ is a vector whose $i$th coordinate is $1$ and all others are $0$ (and $\sum$ should be understood as addition in $(\mathbb{Z}_2)^n$). By linearity, $f(x) = \sum_{i=1}^n f(e_i) x_i$ (where $\sum$ should be understood as addition in $\mathbb{Z}_2$, i.e. $\bigoplus$), which is the indicator function for the set $S$ of indices $i$ such that $f(e_i)=1$ (note that there are only two options for these numbers, $0$ and $1$, and that these numbers only depend on $f$, not on $x$).