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,...,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 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 n\ln n wires. We also show that this bound cannot be essentially improved: some matrices, like Hadamard ones, require n\ln n/\ln\ln n wires.