Solving $n$-binary-variable system of equations using only combinations of $n \over 2$ variables when $n \over 2$ is even

Question

It seems that it's impossible to find the unique solution to an $n$-binary-variable system of XOR equations if you only use all $(n \text{ choose } {n \over 2})$ equations combining half the variables, when $n \over 2$ is even i.e. $n \mod 4 \equiv 0$. Why is that?

I'm not that great with notation (suggestions for improvement appreciated!), but for $n$ binary variables: $$x_1, \dots, x_n \in \{0, 1\}$$ ...we can define an "equation" as the XOR of half of those variables: $$(x_1 \wedge y_1) \oplus (x_2 \wedge y_2) \oplus \cdots \oplus (x_n \wedge y_n)$$ $$y = \text{permutation of }(1, \dots, 1, 0, \dots, 0)$$ ...where the number of $1$'s in $y$ is the same as the number of $0$'s which is an even number (i.e. $n \mod 4 \equiv 0$).

For example, you cannot find the unique solution to a system of four-variable equations when all you know are all the combinations of exactly two variables. Here's an example sequence of four variables whose values we know: $$x_{\text{example}} = (1, 1, 0, 0)$$

...and here's all $(n \text{ choose } {n \over 2}) = (4 \text{ choose } 2) = 6$ possible values of $y$:

$$y_1 = (0, 0, 1, 1)$$ $$y_2 = (0, 1, 1, 0)$$ $$y_3 = (1, 1, 0, 0)$$ $$y_4 = (0, 1, 0, 1)$$ $$y_5 = (1, 0, 1, 0)$$ $$y_6 = (1, 0, 0, 1)$$

...we can represent these equations and their solutions with a table/matrix:

     |     |     |     |     | xor(...)
=====+=====+=====+=====+=====+==========
 y_1 |  0  |  0  |  1  |  1  | = 0 = (x_1 & 0) ^ (x_2 & 0) ^ (x_3 & 1) ^ (x_4 & 1) = x_3 ^ x_4
-----+-----+-----+-----+-----+----------
 y_2 |  0  |  1  |  1  |  0  | = 1
-----+-----+-----+-----+-----+----------
 y_3 |  1  |  1  |  0  |  0  | = 0
-----+-----+-----+-----+-----+----------
 y_4 |  0  |  1  |  0  |  1  | = 1
-----+-----+-----+-----+-----+----------
 y_5 |  1  |  0  |  1  |  0  | = 1
-----+-----+-----+-----+-----+----------
 y_6 |  1  |  0  |  0  |  1  | = 1

...and do something like Gaussian Elimination (row operations using swap and XOR) to give us this:

     |     |     |     | xor(...)
=====+=====+=====+=====+==========
  1  |  0  |  0  |  1  | = 1
-----+-----+-----+-----+----------
  0  |  1  |  0  |  1  | = 1
-----+-----+-----+-----+----------
  0  |  0  |  1  |  1  | = 0
-----+-----+-----+-----+----------
  0  |  0  |  1  |  1  | = 0
-----+-----+-----+-----+----------
  0  |  0  |  1  |  1  | = 0
-----+-----+-----+-----+----------
  0  |  0  |  1  |  1  | = 0

But notice that although we started with all possible combinations of two variables we cannot recover the values of $x_1 \dots x_4$. Instead, all we've found out for our $x_{\text{example}}$ is that $x_1 \neq x_4$, $x_2 \neq x_4$, and that $x_3 = x_4$.

Interestingly e.g. 10-variable systems can be solved while 12-variable systems cannot.

Can anyone show a proof of this for all values of $n$?

Edit: In the case of four variables like above I feel like it has something to do with the fact that the equations can only represent whether any two variables are equal or not equal. But I don't know how to extend that to the case of eight variables.

Answer 1

Here is a somewhat more general result. I will use $\oplus$ to denote logical exclusive or.

Suppose we have a Boolean system of equations (equivalently, a system of linear equations in several variables $x_1,x_2,\ldots,x_n$ over $\mathbb{Z}/2\mathbb{Z}$).

If the equations can be rewritten in a form where all the variables appear only as in XOR'ing pairs of variables, then any solution $x_1,x_2,\ldots,x_n$ gives rise to a different solution by complementation, $\overline{x_1},\overline{x_2},\ldots, \overline{x_n}$.

Note that $x_i \oplus x_j \equiv \overline{x_i} \oplus \overline{x_j}$, regardless of whether $i,j$ are distinct or not.

So a system of the kind considered here cannot have a unique solution.