Given matrix $A in {0,1}^{n times m}$ with $n$ rows and $m = 2^n – 1$ columns. Where $j$-th column is binary decomposition of $j$ ($j = 1 dots 2^n – 1$). For example, if $n = 3$:

$ A = begin{pmatrix}

0 & 0 & 0 & 1 & 1 & 1 & 1 \

0 & 1 & 1 &0 & 0& 1 & 1 \

1 & 0 & 1 & 0 & 1 & 0 & 1

end{pmatrix}$

This matrix calculates $Ax$ over $({0,1}, oplus)$, where $x in {0,1}^m$.

For example, if $n = 3$ it calculates $(x_4 oplus x_5 oplus x_6 oplus x_7,; x_2 oplus x_3 oplus x_6 oplus x_7, ; x_1 oplus x_3 oplus x_5 oplus x_7)^T$

This is a Boolean function with $m = 2^n – 1$ inputs and $n$ outputs. It can be represented by boolean circuit $S$ with $m = 2^n – 1$ inputs and $n$ outputs, *where only XOR gates are allowed*. **Each XOR gate in circuit $S$ is binary — it takes exactly two inputs**.

Let us denote by $size(S)$ number of gates in $S$ (we don’t count inputs as gates, but we count outputs as gates).

It is not hard to prove upper bound: $size(S) le 2(2^n – 1 – n)$.

Problem:Provelowerbound: $size(S) ge 2(2^n – 1 – n)$.