Geršgorin variations. III: On a theme of Brualdi and Varga (Q2463607): Difference between revisions

[For part II see \textit{A. J. Hoffman}, Adv. Comput. Math. 25, No. 1--3, 1--6 (2006; Zbl 1107.15013).] A transversal of a nonnegative matrix of order \(n\) is the set of \(n\) positive entries of the matrix with no two of the entries in the same row or column. The product of these entries is called the value of the transversal. Let \(a\) and \(r\) denote two positive vectors of order \(n\), and let \(G\) denote a loop-free digraph with each vertex having positive outdegree. Define the matrix \(B(a,r,G)=[b_{ij}]\), with main diagonal \(a\), and, for the all off-diagonal entries, \(b_{ij}=r_i\), if \((i,j)\) is an edge of \(G\), and \(b_{ij}=0\), otherwise. In this note, the authors consider the problem of finding a transversal of \(B(a,r,G)\) of maximum value. The main results are proved based on the duality theorem applied to assignment problem, and on the Camion-Hoffman theorem, due mainly to \textit{R. B. Bapat} and \textit{T. E. S. Raghavan} [Nonnegative matrices and applications. Cambridge: Cambridge University Press (1997; Zbl 0879.15015)] and to \textit{P. Camion} and \textit{A. J. Hoffman} [Pac. J. Math. 17, 211--214 (1966; Zbl 0145.03902)], respectively. PS: For a strongly connected digraph with at least two cycles, the authors create a new abbreviation: scwaltcy!