Abstract
We consider depth-2 circuits with arbitrary boolean functions as gates. Such a circuit represents a given boolean n by n matrix $A$ if it correctly computes the linear operator $Ax$ over GF(2) on all $n$ unit vectors $e_1\dots,e_n$; on other input vectors $x$ the circuit can output arbitrary values. In the class of linear circuits, where each gate computes the sum mod-2 of its inputs, some matrices require $\Omega(n^2/\ln n)$ wires.
We show that using non-linear gates one can save a lot of wires: every matrix can then be represented by a depth-2 circuit with $O(n\ln n)$ wires. We also show that this bound cannot be essentially improved: some matrices, like Hadamard ones, require $\Omega(n\ln n/\ln\ln n)$ wires.