# complexity theory – Prove lower bound on boolean circuit

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: Prove lower bound: $$size(S) ge 2(2^n – 1 – n)$$.