ON THE COMPLEXITY OF LINEAR BOOLEAN OPERATORS WITH THIN MATRIXES
It is considered the problem of construction of a «rectangle-free» Boolean (n × n)-matrix <i>A </i>(i.e. a matrix without (2 × 2)-submatrixes of all unities) such that the corresponding linear mapping modulo 2 has complexity o(v(A) - n) in the basis {⊕}, where v(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 <i>thin matrixes.) </i>Two constructions for solving the problem are introduced. In the first example n = <i>ρ</i><sup><i></i>2</sup>, where <i>ρ</i> is an odd prime number. The weight of the corresponding matrix <i>H</i><sub><i>ρ</i></sub><i> </i>is <i>ρ</i><sup><i></i>3</sup> and the complexity of the corresponding linear operator is O(<i>ρ</i><sup><i></i>2</sup> log <i>ρ</i> log log <i>ρ</i>). The matrix in the second example has weight nk, where k is the cardinality of the Sidon set in Z<sub>n</sub>. One can put k = Θ(√n); for some n, Sidon sets of cardinality k ~ √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. 6.