On Structural Rank and Resilience of Sparsity Patterns
Mohamed-Ali Belabbas, Xudong Chen, Daniel Zelazo · IEEE Transactions on Automatic Control · 2022
A sparsity pattern in$\mathbb {R}^{n \times m}$, for$m\geq n$, is a vector subspace of matrices admitting a basis consisting of canonical basis vectors in$\mathbb {R}^{n \times m}$. We represent a sparsity pattern by a matrix with$0/\star$-entries, where$\star$-entries are arbitrary real numbers and 0-entries are equal to 0. We say that a sparsity pattern has full structural rank if the maximal rank of matrices contained in it is$n$. In this article, we investigate the degree of resilience of patterns with full structural rank: We address questions, such as how many$\star$-entries can be removed without decreasing the structural rank and, reciprocally, how many$\star$-entries one needs to add so as to increase the said degree of resilience to reach a target. Our approach goes by translating these questions into max-flow problems on appropriately defined bipartite graphs. Based on these translations, we provide algorithms that solve the problems in polynomial time.