Interlacing properties of the eigenvalues of some matrix classes

We establish the eigenvalue interlacing property (i.e. the smallest real eigenvalue of a matrix is less than the smallest real eigenvalue of any of its principal submatrices) for the class of matrices introduced by Kotelyansky (all principal and almost principal minors of these matrices are positive). We show that certain generalizations of Kotelyansky and totally positive matrices possess this property. We also prove some interlacing inequalities for the other eigenvalues of Kotelyansky matrices.     

Necessary conditions and a sufficient condition for the Fischer-Hadamard inequalities

It is well known that a matrix, all of whose principal minors are positive, satisfies the Fischer-Hadamard inequalities if and only if it is weakly sign symmetric. In this paper we consider the general case of matrices whose principal minors may be nonpositive. Necessary conditions and a sufficient condition for the Fischer-Hadamard inequalities to hold are given in the general case.     

Spanning-tree extensions of the Hadamard-Fischer inequalities

All possible graph-theoretic generalizations of a certain sort for the Hadamard-Fischer determinantal inequalities are determined. These involve ratios of products of principal minors which dominate the determinant. Furthermore, the cases of equality in these inequalities are characterized, and equality is possible for every set of values which can occur for the relevant minors. This relates recent work of the authors on positive definite completions and determinantal identities. When applied to the same collections of principal minors, earlier generalizations give poorer, more difficult to compute bounds than the present inequalities. Thus, this work extends, and in a certain sense completes, a series of generalizations of Hadamard-Fischer begun in the 1960s.     

AlmostP 0-matrices and the classQ

This paper demonstrates that within the class of thosen × n real matrices, each of which has a negative determinant, nonnegative proper principal minors and inverse with at least one positive entry, the class ofQ-matrices coincides with the class of regular matrices. Each of these classes of matrices plays an important role in the theory of the linear complementarity problem. Lastly, analogous results are obtained for nonsingular matrices which possess only nonpositive principal minors.     

On weakly sign-symmetric matrices

Weakly sign-symmetric matrices have non-negative principal minors and non-negative products of symmetrically placed pairs of almost-principal minors. A necessary condition is proved for such a matrix to have as rank a given positive integer. Several characterizations are given of those weakly sign-symmetric matrices for which the generalized Hadamard inequality holds.     

M-matrix products having positive principal minors

Sufficient conditions are given for powers and products of M-matrices to have all principal minors positive. Several of these conditions involve directed graphs of the matrices. In particular we show that if A and B are irreducible M-matrices which have longest simple circuit of length two with A+B having no simple circuit longer than three, then the product AB has all principal minors positive.     

On a conjecture on the eigenvalues of p-matrices

The spectra of matrices with positive principal minors are strudied. A conjecture and a question concerning the width of the wedge around the negative real axis which is free from eigenvalues of such matrices are answered negatively.     

Intervals of P-matrices and related matrices

We consider intervals of matrices with respect to the usual entrywise partial ordering. Necessary and sufficient conditions are given for an interval of matrices to contain only P-matrices (i.e. matrices having only positive principal minors) or related matrices.     

Diagonal dominance, Schur complements and some classes of H-matrices and P-matrices

We analyze a class of matrices generalizing strictly diagonally dominant matrices and included in the important class of H-matrices. Adequate pivoting strategies and the corresponding Schur complements are studied. A new class of matrices with all their principal minors positive is presented.     

On the characterization of almost strictly totally positive matrices

A nonsingular matrix is called almost strictly totally positive when all its minors are nonnegative and, furthermore, these minors are strictly positive if and only if their diagonal entries are strictly positive. Almost strictly totally positive matrices are useful in Approximation Theory and Computer Aided Geometric Design to generate bases of functions with good shape preserving properties. In this paper we give an algorithmic characterization of these matrices. Moreover, we provide a determinantal characterization of them in terms of the positivity of a very reduced number of their minors and also in terms of their factorizations.     

Matrices with positive principal minors

A new necessary and sufficient condition is given for all principal minors of a square matrix to be positive. A special subclass of such matrices, called quasidominant matrices, is also examined.     

On the leading principal minors of direct products

A result is given, relating the leading principal minors of a direct product of matrices to the leading principal minors of the matrices     

On the leading principal minors of direct products

A result is given, relating the leading principal minors of a direct product of matrices to the leading principal minors of the matrices     

The width and integer optimization on simplices with bounded minors of the constraint matrices

In this paper, we will show that the width of simplices defined by systems of linear inequalities can be computed in polynomial time if some minors of their constraint matrices are bounded. Additionally, we present some quasi-polynomial-time and polynomial-time algorithms to solve the integer linear optimization problem defined on simplices minus all their integer vertices assuming that some minors of the constraint matrices of the simplices are bounded.     

On the characterization of almost strictly totally positive matrices

A nonsingular matrix is called almost strictly totally positive when all its minors are nonnegative and, furthermore, these minors are strictly positive if and only if their diagonal entries are strictly positive. Almost strictly totally positive matrices are useful in Approximation Theory and Computer Aided Geometric Design to generate bases of functions with good shape preserving properties. In this paper we give an algorithmic characterization of these matrices. Moreover, we provide a determinantal characterization of them in terms of the positivity of a very reduced number of their minors and also in terms of their factorizations. Both authors were partially supported by the DGICYT Spain Research Grant PB93-0310     

Controllability,inertia, and stability for tridiagonal matrices

Criteria are given for the controllability of certain pairs of tridiagonal matrices. These criteria may be used, with the Chen-Wimmer theorem, to obtain inertia results. Also, a characterization is given of those nonsingular tridiagonal matrices with certain principal minors nonnegative which are positive stable. This extends a previous characterization of the real D-stable tridiagonal matrices.     

M-matrix products having positive principal minors

Sufficient conditions are given for powers and products of M-matrices to have all principal minors positive. Several of these conditions involve directed graphs of the matrices. In particular we show that if A and B are irreducible M-matrices which have longest simple circuit of length two with A+B having no simple circuit longer than three, then the product AB has all principal minors positive.     

Positive definite completions of partial Hermitian matrices

The question of which partial Hermitian matrices (some entries specified, some free) may be completed to positive definite matrices is addressed. It is shown that if the diagonal entries are specified and principal minors, composed of specified entries, are positive, then, if the undirected graph of the specified entries is chordal, a positive definite completion necessarily exists. Furthermore, if this graph is not chordal, then examples exist without positive definite completions. In case a positive definite completion exists, there is a unique matrix, in the class of all positive definite completions, whose determinant is maximal, and this matrix is the unique one whose inverse has zeros in those positions corresponding to unspecified entries in the original partial Hermitian matrix. Additional observations regarding positive definite completions are made.     

Conditions for the positivity of determinants

Consider a matrix with positive diagonal entries, which is similar via a positive diagonal matrix to a symmetric matrix, and whose signed directed graph has the property that if a cycle and its symmetrically placed complement have the same sign, then they are both positive. We provide sufficient conditions so that A be a P-matrix, that is , a matrix whose principal minors are all positive. We further provide sufficiet conditions for an arbitrary matrix A whose (undirected) graph is subordinate to a tree, to be a P-matrix. If, in additionA is sign symmetric and its undirected graph is a tree, we obtain necessary and sufficient conditions that it be a P-matrix. We go on to consider the positive semi-definiteness of symmetric matrices whose graphs are subordinate to a given tree and discuss the convexity of the set of all such matrices.     

bc–opt: a branch-and-cut code for mixed integer programs

A branch-and-cut mixed integer programming system, called bc–opt, is described, incorporating most of the valid inequalities that have been used or suggested for such systems, namely lifted 0-1 knapsack inequalities, 0-1 gub knapsack and integer knapsack inequalities, flowcover and continuous knapsack inequalities, path inequalities for fixed charge network flow structure and Gomory mixed integer cuts. The principal development is a set of interface routines allowing these cut routines to generate cuts for new subsets or aggregations of constraints. The system is built using the XPRESS Optimisation Subroutine Library (XOSL) which includes a cut manager that handles the tree and cut management, so that the user only essentially needs to develop the cut separation routines. Results for the MIPLIB3.0 library are presented - 37 of the instances are solved very easily, optimal or near optimal solution are produced for 18 other instances, and of the 4 remaining instances, 3 have 0, +1, -1 matrices for which bc–opt contains no special features. Received May 11, 1997 / Revised version received March 8, 1999?Published online June 11, 1999