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 Citations (Scopus)

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

Fingerprint

Modulus
Polynomial time
Cycle
Polynomials
Diagonal matrix
Digraph
Exceed
Strictly
Specification
Specifications
Concepts

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

Cite this

Boros, Endre ; Brualdi, Richard A. ; Crama, Yves ; Hoffman, A. J. / Geršgorin variations III : On a theme of Brualdi and Varga. In: Linear Algebra and Its Applications. 2008 ; Vol. 428, No. 1. pp. 14-19.
@article{50ba061ffc1c4200ac8af38f09d3a0f1,
title = "Geršgorin variations III: On a theme of Brualdi and Varga",
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.",
keywords = "Assignment problem, Digraph, Duality, Matrix singularity, Scwaltcy, Transversal",
author = "Endre Boros and Brualdi, {Richard A.} and Yves Crama and Hoffman, {A. J.}",
year = "2008",
month = "1",
day = "1",
doi = "10.1016/j.laa.2007.10.003",
language = "English (US)",
volume = "428",
pages = "14--19",
journal = "Linear Algebra and Its Applications",
issn = "0024-3795",
publisher = "Elsevier Inc.",
number = "1",

}

Geršgorin variations III : On a theme of Brualdi and Varga. / Boros, Endre; Brualdi, Richard A.; Crama, Yves; Hoffman, A. J.

In: Linear Algebra and Its Applications, Vol. 428, No. 1, 01.01.2008, p. 14-19.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Geršgorin variations III

T2 - On a theme of Brualdi and Varga

AU - Boros, Endre

AU - Brualdi, Richard A.

AU - Crama, Yves

AU - Hoffman, A. J.

PY - 2008/1/1

Y1 - 2008/1/1

N2 - 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.

AB - 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.

KW - Assignment problem

KW - Digraph

KW - Duality

KW - Matrix singularity

KW - Scwaltcy

KW - Transversal

UR - http://www.scopus.com/inward/record.url?scp=36048986362&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=36048986362&partnerID=8YFLogxK

U2 - 10.1016/j.laa.2007.10.003

DO - 10.1016/j.laa.2007.10.003

M3 - Article

AN - SCOPUS:36048986362

VL - 428

SP - 14

EP - 19

JO - Linear Algebra and Its Applications

JF - Linear Algebra and Its Applications

SN - 0024-3795

IS - 1

ER -