Geršgorin variations III: On a theme of Brualdi and Varga

Endre Boros, Richard A. Brualdi, Yves Crama, A. J. Hoffman

Research output: Contribution to journalArticle

2 Scopus citations

Abstract

Brualdi brought to Geršgorin Theory the concept that the digraph G(A) of a matrix A is important in studying whether A is singular. He proved, for example, that if, for every directed cycle of G(A), the product of the diagonal entries exceeds the product of the row sums of the moduli of the off-diagonal entries, then the matrix is nonsingular. We will show how, in polynomial time, that condition can be tested and (if satisfied) produce a diagonal matrix D, with positive diagonal entries, such that AD (where A is any nonnnegative matrix satisfying the conditions) is strictly diagonally dominant (and so, A is nonsingular). The same D works for all matrices satisfying the conditions. Varga raised the question of whether Brualdi's conditions are sharp. Improving Varga's results, we show, if G is scwaltcy (strongly connected with at least two cycles), and if the Brualdi conditions do not hold, how to construct (again in polynomial time) a complex matrix whose moduli satisfy the given specifications, but is singular.

Original languageEnglish (US)
Pages (from-to)14-19
Number of pages6
JournalLinear Algebra and Its Applications
Volume428
Issue number1
DOIs
StatePublished - Jan 1 2008

All Science Journal Classification (ASJC) codes

  • Algebra and Number Theory
  • Numerical Analysis
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics

Keywords

  • Assignment problem
  • Digraph
  • Duality
  • Matrix singularity
  • Scwaltcy
  • Transversal

Fingerprint Dive into the research topics of 'Geršgorin variations III: On a theme of Brualdi and Varga'. Together they form a unique fingerprint.

  • Cite this