Sparsity of orthogonal matrices with restrictions (Q1971034)

The authors study the sparsity of orthogonal matrices that have a fixed number, \(k>0\), of full columns. In particular, Corollary 4.2 asserts that minimum number of nonzero entries in an \(m\times m\) orthogonal matrix with \(k\) full columns is \[ \left(\left[ \lg{m\over k}\right] +k+2\right) m-k 2^{\bigl [\lg(m/k) \bigr ]+1}. \] In order to prove Corollary 4.2, they prove something stronger. A matrix is row-orthogonal provided each of its rows is nonzero and its rows are pairwise orthogonal. Corollary 4.1 asserts that the minimum number of nonzero entries in an \(m\times n\) row-orthogonal matrix with \(k\) full columns and no column of zeros is \[ \left(\left[ \lg\left({m\over k}\right) \right]+ k+2 \right) m-k 2^{\bigl[\lg(m/k) \bigr]+1}+(n-m). \] A consequence of this result is that if \(A\) is an \(m\times n\) row-orthogonal matrix with \(n>m\), with no column of zeros and \[ \#(A)<\left( \left[\lg\left( {n\over n-m}\right) \right]+ 2\right) n-(n-m) 2^{\bigl[ \lg(n/n-m) \bigr]+1}, \] then each vector orthogonal to the rows of \(A\) has an entry equal to 0. Also, for integers \(k\) and \(n\) with \(k\leq n\), the minimum number of nonzero entries is \(n\times n\). A connected, orthogonal matrix having a column with at least \(k\) nonzero entries is determined.