John S. Lew
Mathematical Biosciences
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. © 2007 Elsevier Inc. All rights reserved.
John S. Lew
Mathematical Biosciences
D.S. Turaga, K. Ratakonda, et al.
SCC 2006
Hannaneh Hajishirzi, Julia Hockenmaier, et al.
UAI 2011
W.F. Cody, H.M. Gladney, et al.
SPIE Medical Imaging 1994