Reference : Geršgorin variations III: On a theme of Brualdi and Varga
Scientific journals : Article
Physical, chemical, mathematical & earth Sciences : Mathematics
Geršgorin variations III: On a theme of Brualdi and Varga
Boros, Endre [ > > ]
Brualdi, Richard [ > > ]
Crama, Yves mailto [Université de Liège - ULiège > HEC - École de gestion de l'ULiège > Recherche opérationnelle et gestion de la production - HEC-Ecole de gestion - HEC - Ecole de gestion de l'ULG : Direction générale >]
Hoffman, Alan [ > > ]
Journal of Linear Algebra and its Applications
[en] matrix singularity ; digraph ; scwaltcy
[en] 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.
Available online at

File(s) associated to this reference

Fulltext file(s):

Open access
scwaltcy.pdfAuthor preprint114.85 kBView/Open

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.