On Structural Rank and Resilience of Sparsity Patterns

• 成果类型: Article
• 署名作者: Belabbas, Mohamed-Ali; Chen, Xudong; Zelazo, Daniel
• 署名单位: University of Illinois System; University of Illinois Urbana-Champaign; University of Illinois System; University of Illinois Urbana-Champaign; University of Colorado System; University of Colorado Boulder; Technion Israel Institute of Technology
• 刊物名称: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
• ISSN/ISSBN: 0018-9286
• DOI: 10.1109/TAC.2022.3212013
• 发表日期: 2023
• 页码: 4783-4795
• 关键词: Graph theory; matchings; max-flows; Passivity; sparsity patterns

摘要

A sparsity pattern in R-nxm, for m >= n, is a vector subspace of matrices admitting a basis consisting of canonical basis vectors in R-nxm. 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.