Filling the gap between the Gerschgorin and Brualdi theorems

L. Yu. Kolotilina

Zapiski Nauchnykh Seminarov POMI, Computational methods and algorithms. Part XIX, Tome 334 (2006), pp. 128-148

Résumé

The paper presents new diagonal dominance type nonsingularity conditions for $n\times n$ matrices formulated in terms of circuits of length not exceeding a fixed number $r\ge 0$ and simple paths of length $r$ in the digraph of the matrix. These conditions are intermediate between the diagonal dominance conditions in terms of all paths of length $r$ and Brualdi's diagonal dominance conditions, involving all the circuits. For $r=0$, the new conditions reduce to the standard row diagonal dominance conditions $|a_{ii}|\ge\sum\limits_{j\ne i}|a_{ij}|$, $i=1,\dots,n$, whereas for $r=n$ they coincide with the Brualdi circuit conditions. Thus, they connect the classical Lévy–Desplanques theorem and the Brualdi theorem, yielding a family of sufficient nonsingularity conditions. Further, for irreducible matrices satisfying the new diagonal dominance conditions with nonstrict inequalities, the singularity/nonsingularity problem is solved. Also the new sufficient diagonal dominance conditions are extended to the so-called mixed conditions, simultaneously involving the deleted row and column sums of an arbitrary finite set of matrices diagonally conjugated to a given one, which, in the simplest nontrivial case, reduce to the old-known Ostrowski conditions $|a_{ii}|>(\sum\limits_{j\ne i}|a_{ij}|)^\alpha\;(\sum\limits_{j\ne i} |a_{ji}|)^{1-\alpha}$, $i=1,\dots,n$, $0\le\alpha\le 1$. The nonsingularity conditions obtained are used to provide new eigenvalue inclusion sets, depending on $r$, which, as $r$ varies from 0 to $n$, serve as a bridge connecting the union of Gerschgorin's disks with the Brualdi inclusion set.