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.