On \(n\)-column 0,1-matrices with all \(k\)-projections surjective (Q1323388)

This paper presents a new approach to construct a small \(n\)-column 0,1- matrix for two given integers \(n\) and \(k\) \((k<n)\), such that every \(k\)- column projection contains all \(2^ k\) possible row vectors, namely surjective on \(\{0,1\}^ k\). The number of the matrix's rows does not exceed \(2^ k\lceil\log(k^ 2+ 4)\rceil^{k-1}\left({2\log n\over \log(0.25k^ 2+ 1)}\right)^{\lceil\log(0.25k^ 2+ 1)\rceil}\). This approach has considerable advantage for small \(k\) and practical sizes of \(n\). It can be applied to the test generation of VLSI circuits, the design of fault tolerant systems and other fields.