Principal submatrices of co-order one with the biggest Perron root

摘要

Let A be an irreducible nonnegative matrix, w be any of its indices, and A - w be the principal submatrix of co-order one obtained from A by deleting the wth column and row. Denote by V-ext(A) the set of indices to such that A - w has the biggest Perron root (among all the principal submatrices of co-order one of the original matrix A). We prove that exactly one Jordan block corresponds to the Perron root lambda(A - w) of A - w for every w is an element of V-ext (A). If its size is strictly greater than one for some w is an element of V-ext(A), then the original matrix A is permutationally similar to a lower Hessenberg matrix with positive entries on the superdiagonal and in the left lower corner (in other words, the digraph D(A) of A has a Hamiltonian circuit and its diameter is one less than its order). In the opposite case for any w is an element of V-ext(A), there is a unique path gamma = {wi}(i=0)(p) going through w in D (A) such that(1) A - w(i) has the biggest Perron root for i = 0, ..., p;(2) A - w(0) has a right positive Perron eigenvector;(3) A - w(p) has a left positive Perron eigenvector;(4) A - w(i) has neither a left nor a right positive Perron eigenvector for i = 1, ..., p - 1.Thus, by the spectral criterion for a nonnegative matrix to be irreducible, the submatrices A - w(0),..., A - w(p) combined inherit the property of irreducibility. We also show that A - w is irreducible for every w is an element of V-ext(A) if any of the following holds:(1) A is symmetric;(2) every column (row) of A has at least two positive nondiagonal entries;(3) A has at least two columns (rows) all of whose entries are positive.If A is an irreducible tournament matrix, then either A - w is also irreducible for any w is an element of V-ext(A) or there exist exactly two indices w(in) and w(out) in V-ext(A) such that A - W-in and A - w(out) are reducible. In the last case any other principal submatrix of co-order one is irreducible. This shows that in the general case, a one-vertex-deleted subdigraph with the biggest Perron root need not have the best connectivity properties among all one-vertex-deleted subdigraphs of a given strongly connected digraph D. (C) 2004 Elsevier Inc. All rights reserved.