A note on the total unimodularity of matrices

A necessary and sufficient characterization of totally unimodular matrices is given which is derived from a necessary condition for total unimodularity due to Camion. This characterization is then used in connection with a theorem of Hoffman and Kruskal to provide an elementary proof of the characterization of totally unimodular matrices in terms of forbidden submatrices due to Camion.     

Perfect zero–one matrices

A zero–one matrix is called perfect if the polytope of the associated set packing problem has integral vertices only. By this definition, all totally unimodular zero–one matrices are perfect. In this paper we give a characterization of perfect zero–one matrices in terms offorbidden submatrices. Perfect zero–one matrices are closely related to perfect graphs and constitute a generalization of balanced matrices as introduced by C. Berge. Furthermore, the results obtained here bear on an unsolved problem in graph theory, the strong perfect graph conjecture, also due to C. Berge.     

Total unimodularity and the Euler-subgraph problem

We give a short treatment (including proofs) of all known characterizations by way of forbidden structures of totally unimodular matrices, i.e. matrices whose square minors have determinants of 0, +1, or −1 only. A generalization of a known topological characterization gives rise to a new combinatorial optimization problem which is introduced here and called the Euler-subgraph problem.     

The biobjective undirected two-commodity minimum cost flow problem

We address the two-commodity minimum cost flow problem considering two objectives. We show that the biobjective undirected two-commodity minimum cost flow problem can be split into two standard biobjective minimum cost flow problems using the change of variables approach. This technique allows us to develop a method that finds all the efficient extreme points in the objective space for the two-commodity problem solving two biobjective minimum cost flow problems. In other words, we generalize the Hu's theorem for the biobjective undirected two-commodity minimum cost flow problem. In addition, we develop a parametric network simplex method to solve the biobjective problem.     

Dominant matrices and max algebra

We study the class of so-called totally dominant matrices in the usual algebra and in the max algebra in which the sum is the maximum and the multiplication is usual. It turns out that this class coincides with the well known class of positive matrices having positive the determinants of all 2×2 submatrices. The closure of this class is closed not only with respect to the usual but also with respect to the max multiplication. Further properties analogous to those of totally positive matrices are proved and some connections to Monge matrices are mentioned.     

The Transportation Problem and its Variants

For 54 unimodular linear programming problems it is shown that either (i) the objective function is unbounded, or (ii) the problem is infeasible, or (iii) the problem can be solved by solving a related transportation problem. The related transportation problem is obtained by adding at the most two new constraints to the original problem.     

A good submatrix is hard to find

Given a matrix, it is NP-hard to find a ‘large’ column, row, or arbitraty submatrix that satisfies property π, where π is nontrivial, holds for permutation matrices, and is hereditary on submatrices. Such properties include totally unimodular, transformable to a network matrix, permutable to consecutive ones, and many others. Similar results hold for properties such as positive definite, of bandwidth w, and symmetric.     

Subtotally positive and Monge matrices

A real matrix is called k-subtotally positive if the determinants of all its submatrices of order at most k are positive. We show that for an m × n matrix, only mn inequalities determine such class for every k, 1 ? k ? min(m,n). Spectral properties of square k-subtotally positive matrices are studied. Finally, completion problems for 2-subtotally positive matrices and their additive counterpart, the anti-Monge matrices, are investigated. Since totally positive matrices are 2-subtotally positive as well, the presented necessary conditions for this completion problem are also necessary conditions for totally positive matrices.     

The use of jacobi's lemma in unimodularity theory

The paper applies Jacobi's fundamental result on minors of the adjoint matrix to obtain properties on determinants of unimodular matrices.     

Interlacing and degree conditios for invariat polynomials

It is well known that the invariant factors of a polynomial matrix interlace with ihose of one of its submatrices. If we restrict the degrees of the entries of our matrices in some prescribed way then the invariant factors of such matrices and submatrices satisfy other conditions that may be predicted and, in some cases, even completely described. That is the kind of problem we deal with Our main result is a sort of interlacing theorem for row proper matrices. Convexity and majorization also enter into play.     

由谱数据构造实双反对称矩阵

讨论实完全反对称矩阵的一个特秆值反问题．研究了实完全反对称矩阵的一些特征性质，构造一个实反对称矩阵使其各阶顺序主子矩阵具有指定的特征值．证明了：给定满足一定分隔条件的两组数，存在一个实完全反对称矩阵，使其各阶中心主子矩阵具有相应的特征值．     

Structural properties and recognition of restricted and strongly unimodular matrices

A (0, ±1) matrix A is restricted unimodular if every matrix obtained from A by setting to zero any subset of its entries is totally unimodular. Restricted unimodular matrices are also known as matrices without odd cycles. They have been studied by Commoner and recently Yannakakis has given a polynomial algorithm to recognize when a matrix belongs to this class. A matrix A is strongly unimodular if any matrix obtained from A by setting at most one of its entries to zero is totally unimodular. Crama et al. have shown that (0,1) matrix A is strongly unimodular if and only if any basis of (A, 1) is triangular, whereI is an identity matrix of suitable dimensions. In this paper we give a very simple algorithm to test whether a matrix is restricted unimodular and we show that all strongly unimodular matrices can be obtained by composing restricted unimodular matrices with a simple operation. Partially supported by a New York University Research Challenge Fund Grant.     

On unimodular graphs

We study graphs whose adjacency matrices have determinant equal to 1 or −1, and characterize certain subclasses of these graphs. Graphs whose adjacency matrices are totally unimodular are also characterized. For bipartite graphs having a unique perfect matching, we provide a formula for the inverse of the corresponding adjacency matrix, and address the problem of when that inverse is diagonally similar to a nonnegative matrix. Special attention is paid to the case that such a graph is unicyclic.     

A new strategy for the undirected two-commodity maximum flow problem

We address the two-commodity maximum flow problem on undirected networks. As a result of a change of variables, we introduce a new formulation that solves the problem through classical maximum flow techniques with only one-commodity. Therefore, a general strategy, based on this change of variables, is defined to deal with other undirected multi-commodity problems. Finally, we extend the single objective problem to a bicriteria environment. We show that the set of efficient solutions of the biobjective undirected two-commodity maximum flow problem is the set of alternative optimum solutions of the undirected two-commodity maximum flow problem. In addition, we prove that the set of efficient extreme points in the objective space has, at most, cardinality two.     

Rank-preserving extensions of band matrices

Existence and uniqueness problems are studied for extensions of a band matrix R such that the rank of the extension does not exceed the maximum of the ranks of the submatrices in the band of R. Applications are given to positive semidefinite extensions and extensions of lower-triangular matrices to contractions or to unitary matrices.     

Construction and Algebraic Characterizations of the Planar and Axial Transportation Problems

We describe the construction and several algebraic characterizations of the planar and axial transportation problems using the generalized inverse and the singular value decomposition of their coefficient matrices, and investigate relations between the planar and axial transportation problems. It is shown that results obtained on the planar transportation problem can be applied to the study of the solution of the axial transportation problem.     

Persymmetric determinants 5. Families of overlapping coaxial equivalent determinants

In an earlier paper the author constructed two infinite matrices and showed that they contain families of distinct submatrices whose determinants represent identical polynomials.

The object of this paper is to extend the earlier results in two directions. The first set of identities is closely related to the original set and may be regarded as a supplement to the original paper. The second set relates determinants whose elements are based partly on Stirling numbers of the Second Kind to polynomials whose terms are based on Stirling numbers of the First Kind.     

Rank-preserving extensions of band matrices

Existence and uniqueness problems are studied for extensions of a band matrix R such that the rank of the extension does not exceed the maximum of the ranks of the submatrices in the band of R. Applications are given to positive semidefinite extensions and extensions of lower-triangular matrices to contractions or to unitary matrices.     

Extremal inverse eigenvalue problem for symmetric doubly arrow matrices

In this paper, we consider the following inverse eigenvalue problem: to construct a real symmetric doubly arrow matrix A from the minimal and maximal eigenvalues of all its leading principal submatrices. The necessary and sufficient condition for the solvability of the problem is derived. We also give a necessary and sufficient condition in order that the constructed matrices can be nonnegative. Our results are constructive and they generate algorithmic procedures to construct such matrices.     

Properties of submatrices of Sylvester Hadamard matrices

We investigate the algebraic behaviour of leading principal submatrices of Hadamard matrices being powers of 2. We provide analytically the spectrum of general submatrices of these Hadamard matrices. Symmetry properties and relationships between the upper left and lower right corners of the matrices in this respect are demonstrated. Considering the specific construction scheme of this particular class of Hadamard matrices (called Sylvester Hadamard matrices), we utilize tensor operations to prove the respective results. An algorithmic procedure yielding the complete spectrum of leading principal submatrices of Sylvester Hadamard matrices is proposed.