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.     

On the representability of totally unimodular matrices on bidirected graphs

We present a polynomial time algorithm to construct a bidirected graph for any totally unimodular matrix B by finding node-edge incidence matrices Q and S such that QB=S. Seymour’s famous decomposition theorem for regular matroids states that any totally unimodular (TU) matrix can be constructed through a series of composition operations called k-sums starting from network matrices and their transposes and two compact representation matrices B₁,B₂ of a certain ten element matroid. Given that B₁,B₂ are binet matrices we examine the k-sums of network and binet matrices. It is shown that thek-sum of a network and a binet matrix is a binet matrix, but binet matrices are not closed under this operation for k=2,3. A new class of matrices is introduced, the so-called tour matrices, which generalise network, binet and totally unimodular matrices. For any such matrix there exists a bidirected graph such that the columns represent a collection of closed tours in the graph. It is shown that tour matrices are closed under k-sums, as well as under pivoting and other elementary operations on their rows and columns. Given the constructive proofs of the above results regarding the k-sum operation and existing recognition algorithms for network and binet matrices, an algorithm is presented which constructs a bidirected graph for any TU matrix.     

Complement total unimodularity

A {0, 1} matrix U is defined to be complement totally unimodular (c.t.u.) if U as well as all matrices derived from U by certain complement operations are totally unimodular. Two decompositions of minimal violation matrices of total unimodularity are utilized to characterize the letter matrices by c.t.u. matrices. In addition properties of c.t.u. matrices are presented.     

On some characterisations of totally unimodular matrices

A characterisation of totally unimodular matrices is derived from a result of Hoffman and Kruskal. It is similar in spirit to a result of Baum and Trotter. Its relation with some other known characterisations is discussed and in the particular case where the matrices have (0, 1) entries, we derive some properties of the associated unimodular hypergraphs. Similar results for balanced and perfect matrices are also reviewed.     

Principally Unimodular Skew-Symmetric Matrices

principally unimodular (PU) if every principal submatrix has determinant 0 or ±1. Let A be a symmetric (0, 1)-matrix, with a zero diagonal. A PU-orientation of A is a skew-symmetric signing of A that is PU. If A′ is a PU-orientation of A, then, by a certain decomposition of A, we can construct every PU-orientation of A from A′. This construction is based on the fact that the PU-orientations of indecomposable matrices are unique up to negation and multiplication of certain rows and corresponding columns by −1. This generalizes the well-known result of Camion, that if a (0, 1)-matrix can be signed to be totally unimodular then the signing is unique up to multiplying certain rows and columns by −1. Camion's result is an easy but crucial step in proving Tutte's famous excluded minor characterization of totally unimodular matrices. Received: May 17, 1996     

Characterizations of totally balanced matrices

A (0,1)-matrix is totally balanced if it does not contain as a submatrix the incidence matrix of any cycle of length at least 3. Several alternative characterizations of these matrices are presented. These characterizations follow from properties of strongly chordal graphs, studied by Farber, and maximal totally balanced matrices, studied by Anstee. Using these characterizations, efficient recognition algorithms for totally balanced matrices are presented. In addition, a new completion algorithm for building a maximal totally balanced matrix from an arbitrary totally balanced matrix follows from these results.     

INERTIA SETS OF SYMMETRIC SIGN PATTERN MATRICES

1　IntroductionIn qualitative and combinatorial matrix theory,we study properties ofa matrix basedon combinatorial information,such as the signs of entries in the matrix.A matrix whoseentries are from the set{ + ,-,0 } is called a sign pattern matrix ( or sign pattern,or pat-tern) .We denote the setof all n× n sign pattern matrices by Qn.For a real matrix B,sgn( B) is the sign pattern matrix obtained by replacing each positive( respectively,negative,zero) entry of B by+ ( respectively,-,0 )…     

Recognizing Balanceable Matrices

A 0/±1 matrix is balanced if it does not contain a square submatrix with exactly two nonzero entries per row and per column in which the sum of all entries is 2 modulo 4. A 0/1 matrix is balanceable if its nonzero entries can be signed ±1 so that the resulting matrix is balanced. A signing algorithm due to Camion shows that the problems of recognizing balanced 0/±1 matrices and balanceable 0/1 matrices are equivalent. Conforti, Cornuéjols, Kapoor and Vušković gave an algorithm to test if a 0/±1 matrix is balanced. Truemper has characterized balanceable 0/1 matrices in terms of forbidden submatrices. In this paper we give an algorithm that explicitly finds one of these forbidden submatrices or shows that none exists. Received: October 2004     

Computing singular values of diagonally dominant matrices to high relative accuracy

For a (row) diagonally dominant matrix, if all of its off-diagonal entries and its diagonally dominant parts (which are defined for each row as the absolute value of the diagonal entry subtracted by the sum of the absolute values of off-diagonal entries in that row) are accurately known, we develop an algorithm that computes all the singular values, including zero ones if any, with relative errors in the order of the machine precision. When the matrix is also symmetric with positive diagonals (i.e. a symmetric positive semi-definite diagonally dominant matrix), our algorithm computes all eigenvalues to high relative accuracy. Rounding error analysis will be given and numerical examples will be presented to demonstrate the high relative accuracy of the algorithm.

     

On the normality of Rees algebras associated to totally unimodular matrices

Let A be an integral matrix with non negative entries and let K be a field. We give a sufficient condition for the normality of the monomial subring determined by the columns of A over the field K. One of the main results proves that if A is totally unimodular, then the Rees algebra of the monomial ideal over K defined by the columns of A is a normal domain.     

Almost strictly totally positive matrices

A determinantal identity, frequently used in the study of totally positive matrices, is extended, and then used to re-prove the well-known univariate knot insertion formula for B-splines. Also we introduce a class of matrices, intermediate between totally positive and strictly totally positive matrices. The determinantal identity is used to show any minor of such matrices is positive if and only if its diagonal entries are positive. Among others, this class of matrices includes B-splines collocation matrices and Hurwitz matrices.This author acknowledges a sabbatical stay at IBM T.J. Watson Research Center in 1990, which was supported by a DGICYT grant from Spain.     

On the completion of a partial integral matrix to a unimodular matrix

We prove that if a partial integral matrix has a free diagonal then this matrix can be completed to a unimodular matrix. Such a condition is necessary in a general sense. Consequently if an n × n (n ? 2) partial integral matrix has 2n − 3 prescribed entries and any n entries of these do not constitute a row or a column then it can be completed to a unimodular matrix. This improves a recent result of Zhan.     

An extension of a theorem of Kaplansky

A theorem of Kaplansky asserts that a semigroup of matrices with entries from a field whose members all have singleton spectra is triangularizable. Indeed, Kaplansky’s Theorem unifies well-known theorems of Kolchin and Levitzki on simultaneous triangularizability of semigroups of unipotent and nilpotent matrices, respectively. First, for a division ring D of characteristic zero whose center intersects its multiplicative commutator group in a finite group, we prove that the counterpart of Kolchin’s Theorem over D implies that of Kaplansky’s Theorem over D. Next, we note that this proof, when adjusted in the setting of fields, provides a new and simple proof of Kaplansky’s Theorem over fields of characteristic zero. We show that if Kaplansky’s Theorem holds over a division ring D, which is for instance the case over general fields, then a generalization of Kaplansky’s Theorem holds over D, and in particular over general fields.     

Permanents of special classes of doubly stochastic matrices

We identify the doubly stochastic matrices with at least one zero entry which are closest in the Euclidean norm to J_n, the matrix with each entry equal to 1/n, and we show that at these matrices the permanent function has a relative minimum when restricted to doubly stochastic matrices having zero entries.     

Vector and matrix apportionment problems and separable convex integer optimization

The problems of (bi-)proportional rounding of a nonnegative vector or matrix, resp., are written as particular separable convex integer minimization problems. Allowing any convex (separable) objective function we use the notions of vector and matrix apportionment problems. As a broader class of problems we consider separable convex integer minimization under linear equality restrictions Ax = b with any totally unimodular coefficient matrix A. By the total unimodularity Fenchel duality applies, despite the integer restrictions of the variables. The biproportional algorithm of Balinski and Demange (Math Program 45:193–210, 1989) is generalized and derives from the dual optimization problem. Also, a primal augmentation algorithm is stated. Finally, for the smaller class of matrix apportionment problems we discuss the alternating scaling algorithm, which is a discrete variant of the well-known Iterative Proportional Fitting procedure.     

An alternating projected gradient algorithm for nonnegative matrix factorization

Due to the extensive applications of nonnegative matrix factorizations (NMFs) of nonnegative matrices, such as in image processing, text mining, spectral data analysis, speech processing, etc., algorithms for NMF have been studied for years. In this paper, we propose a new algorithm for NMF, which is based on an alternating projected gradient (APG) approach. In particular, no zero entries appear in denominators in our algorithm which implies no breakdown occurs, and even if some zero entries appear in numerators new updates can always be improved in our algorithm. It is shown that the effect of our algorithm is better than that of Lee and Seung’s algorithm when we do numerical experiments on two known facial databases and one iris database.     

A Lanczos‐type algorithm for the QR factorization of regular Cauchy matrices

We present a fast algorithm for computing the QR factorization of Cauchy matrices with real nodes. The algorithm works for almost any input matrix, does not require squaring the matrix, and fully exploits the displacement structure of Cauchy matrices. We prove that, if the determinant of a certain semiseparable matrix is non‐zero, a three term recurrence relation among the rows or columns of the factors exists. Copyright © 2002 John Wiley & Sons, Ltd.     

On parametrization of totally nonpositive matrices and applications

The problem of accurate computations for totally non‐negative matrices has been studied; however, it remains open for other sign regular matrices. One major obstacle is that there is no known parametrization of these matrices. The main contribution of the present work is that we provide such parametrization of nonsingular totally nonpositive matrices. A useful application of our results is that these parameters can determine accurately the entries of the inverse of a nonsingular totally nonpositive matrix. Copyright © 2011 John Wiley & Sons, Ltd.     

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