On Structural Rank and Resilience of Sparsity Patterns

Mohamed Ali Belabbas, Xudong Chen, Daniel Zelazo

Research output: Contribution to journalArticlepeer-review


A sparsity pattern in R n × m, for m≥ n, is a vector subspace of matrices admitting a basis consisting of canonical basis vectors in Rn × m. We represent a sparsity pattern by a matrix with 0/∗-entries, where ∗-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 ∗-entries can be removed without decreasing the structural rank and, reciprocally, how many ∗-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.

Original languageEnglish (US)
Pages (from-to)4783-4795
Number of pages13
JournalIEEE Transactions on Automatic Control
Issue number8
StatePublished - Aug 1 2023


  • Graph theory
  • matchings
  • max-flows
  • passivity
  • sparsity patterns

ASJC Scopus subject areas

  • Electrical and Electronic Engineering
  • Control and Systems Engineering
  • Computer Science Applications


Dive into the research topics of 'On Structural Rank and Resilience of Sparsity Patterns'. Together they form a unique fingerprint.

Cite this