On Structural Rank and Resilience of Sparsity Patterns

DOI10.1109/TAC.2022.3212013MaRDI QIDQ6093201zbMATH OpenOpenAlexFDO

Authors Mohamed-Ali Belabbas, Xudong Chen, Daniel Zelazo

Publication date 6 October 2023

Published in IEEE Transactions on Automatic Control (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2107.11894

zbMATH Keywords

graph theorymatchingsmax-flowspassivitysparsity patterns

Mathematics Subject Classification ID

Systems theory; control (93-XX)

Abstract: A sparsity pattern in $mathbb{R}^{nimesm}$, for $mgeqn$, is a vector subspace of matrices admitting a basis consisting of canonical basis vectors in $mathbb{R}^{nimesm}$. 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 paper, 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.

Cited in

(1)

• Rank resilience of pattern matrices against structured perturbations with applications

This page was built for publication: On Structural Rank and Resilience of Sparsity Patterns

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6093201)