How sparse can a matrix with orthogonal rows be?
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.
This page was built for publication: How sparse can a matrix with orthogonal rows be?
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1279655)
