Sparse orthogonal matrices and the Haar wavelet (Q1975364)

The authors discuss the sparsity of orthogonal matrices which have a column of nonzero entries. It is shown that the minimun number of nonzero entries in such a matrix of size \(m\times m\) is \[ (\lfloor m\rfloor +3)m-2^{\lfloor m\rfloor+1}. \] This is optimal, as the paper characterizes the matrices which achieve this number. It turns out that this is related to the orthogonal Haar wavelet matrix. The analogous sparsity of \(m\times n\) row-orthogonal matrices is studied.