Representing (0, 1)-matrices by boolean circuits

A boolean circuit represents an n by n ( 0 , 1 ) -matrix A if it correctly computes the linear transformation y → = A x → over GF(2) on all n unit vectors. If we only allow linear boolean functions as gates, then some matrices cannot be represented using fewer than Ω ( n 2 / ln n ) wires. We first show that using non-linear gates one can save a lot of wires: any matrix can be represented by a depth- 2 circuit with O ( n ln n ) wires using multilinear polynomials over GF(2) of relatively small degree as gates. We then show that this cannot be substantially improved: If any two columns of an n by n ( 0 , 1 ) -matrix differ in at least d rows, then the matrix requires Ω ( d ln n / ln ln n ) wires in any depth- 2 circuit, even if arbitrary boolean functions are allowed as gates.