Patterns that preserve sparsity in orthogonal factorization (Q1375102)

An \(m\times n\) zero-nonzero pattern \({\mathcal A}\) with the Hall property allows a full rank matrix \(A\in{\mathcal A}\) with a QR factorization. The union of patterns occurring \(Q\) over all such \(A\) is denoted by \({\mathcal Q}\). By further restricting \({\mathcal A}\) to have the strong Hall property, a Hasse diagram, that is a forest, is used to characterize patterns \({\mathcal A}\) that yield \({\mathcal Q}= {\mathcal A}\), thus preserving the sparsity of \({\mathcal A}\). For fixed \(n\), the sparsest \(n\times n\) such patterns are characterized by a binary rooted tree.