On the complexity of linear Boolean operators with thin matrixes

It is considered the problem of construction of a “rectangle-free” Boolean $(n\times n)$-matrix $A$ (i.e. a matrix without ($2\times2$)-submatrixes of all unities) such that the corresponding linear mapping modulo 2 has complexity $o(\nu(A)-n)$ in the basis $\{\oplus\}$, where $\nu(A)$ is the weight of $A$, i.e. the number of unities. (In the paper by Mityagin and Sadovskiy (1965), where the problem was originally studied, “rectangle-free” matrixes were called thin matrixes.) Two constructions for solving the problem are introduced. In the first example $n=p^2$, where $p$ is an odd prime number. The weight of the corresponding matrix $H_p$ is $p^3$ and the complexity of the corresponding linear operator is $O(p^2\log p\log\log p)$. The matrix in the second example has weight $nk$, where $k$ is the cardinality of the Sidon set in $\mathbb Z_n$. One can put $k=\Theta(\sqrt n)$; for some $n$, Sidon sets of cardinality $k\sim\sqrt n$ are known. The complexity of the corresponding linear mapping is $O(n\log n\log\log n)$. Some generalizations of the problem are also considered. Bibl. 29.