How sparse can a matrix with orthogonal rows be? (Q1279655)

Let \(A=(a_{ij})\) be a real \(m\) by \(n\) matrix. It is called row-orthogonal if each of its rows is nonzero, and its rows are pairwise orthogonal. The matrix \(A\) is said to be connected if the bipartite graph on \(V=\{1, \dots, m\}\cup\{1',\dots,n'\}\) whose edge set is given by \(E=\{ij'\mid a_{ij}\neq 0\}\) is connected. Finally, \(A\) (with \(m\leq n)\) is called indecomposable provided \(A\) does not contain a zero submatrix whose dimensions sum to \(n\). The authors prove: Let \(A\) be row-orthogonal matrix. If \(A\) is connected then it has at least \(4m-4\) nonzero entries if \(n\leq 2m-2\), and at least \(n+2m-2\) nonzero entries if \(n>2m-2\). If \(A\) is indecomposable and \(m<n\) then it has at least \(8m-4n\) nonzero entries if \(n<4m/3\), at least \(4m-n\) nonzero entries if \(4m/3\leq n<2m\), and at least \(2m\) nonzero entries if \(2m\leq n\). All bounds are tight. The zero patterns of the matrices for which equality holds are characterized.