Preface
A matrix is called totally nonnegative (resp. totally positive) if the determinant of every square submatrix is a nonnegative (resp. positive) number. This seemingly unlikely occurrence arises in a remarkable variety of ways (see Section 0.2 for a sample) and carries with it an array of very attractive mathematical structure. Indeed, it is the most useful and aesthetic matricial topic not covered in the broad references [HJ85] and [HJ91]. It is our purpose here to give a largely self-contained development of the most fundamental parts of that structure from a modern theoretical perspective. Applications of totally nonnegative matrices and related numerical issues are not the main focus of this work, but are recognized as being integral to this subject. We also mention a number of more specialized facts with references and give a substantial collection of references covering the subject and some related ideas.
Historically, the books [GK60, GK02, Kar68] and [GM96] and the survey paper [And87] have been the most common references in this area. However, each has a somewhat special perspective and, by now, each is missing some modern material. The most recent of these, [GM96], is more than fifteen years old and is a collection of useful, but noncomprehensive papers broadly in the area. In [Kar68] and [And87] the perspective taken leads to a notation and organization that can present difficulty to the reader needing particular facts. Perhaps the most useful and fundamental reference over a long period of time [GK60], especially now that it is readily available in English, is from the perspective of one motivating and important application and is now about sixty years old.
The present book takes a core, matrix theoretic perspective common to all sources of interest in the subject and emphasizes the utility of the elementary bidiagonal factorizations (see Chapter 2), which, though its roots are rather old, has only recently emerged as the primary tool (among very few available at present) to understand the beautiful and elaborate structure of totally nonnegative matrices. This tool is largely unused in the prior references. Along with the elementary bidiagonal factorization, planar diagrams, a recently appearing concept, are introduced as a conceptual combinatorial tool for analyzing totally nonnegative matrices. In addition to the seemingly unlimited use of these combinatorial objects, they lend themselves to obtaining prior results in an elegant manner, whereas in the past many results in this area were hard fought. As we completed this volume, the book [Pin10] appeared. It takes a different and more classical view of the subject, with many fewer references. Of course, its appearance is testimony to interest in and importance of this subject.
Our primary intent is that the present volume be a useful reference for all those who encounter totally nonnegative matrices. It could also be readily used to guide a seminar on the subject for either those needing to learn the ideas fundamental to the subject or those interested in an attractive segment of matrix analysis. For brevity, we have decided not to include textbook-type problems to solidify the ideas for students, but for purposes for which these might be useful, a knowledgeable instructor could add appropriate ones.
Our organization is as follows. After an initial introduction that sets major notation, gives examples, and describes several motivating areas, Chapter 1 provides much of the needed special background and preliminary results used throughout. (Any other needed background can be found in [HJ85] or a standard elementary linear algebra text.) Chapter 2 develops the ubiquitously important elementary bidiagonal factorization and related issues, such as LU factorization and planar diagrams that allow a combinatorial analysis of much about totally nonnegative matrices. Though an m-by-n matrix has many minors, total nonnegativity/positivity may be checked remarkably efficiently. This and related ideas, such as sufficient collections of minors, are the subject of Chapter 3.
Viewed as a linear transformation, it has long been known that a totally positive matrix cannot increase the sequential variation in the signs of a vector (an important property in several applications). The ideas surrounding this fact are developed in Chapter 4 and several converses are given. The eigenvalues of a totally positive matrix are positive and distinct and the eigenvectors are highly structural as well. A broad development of spectral structure and principal submatrices etc. are given in Chapter 5. Like positive semidefinite and M-matrices, totally nonnegative matrices enjoy a number of determinantal inequalities involving submatrices. These are explored in Chapter 6.
The remaining four chapters contain introductions to a variety of more specialized and emerging topics, including the distribution of rank in a TN matrix (Chapter 7); Hadamard (or entry-wise) products of totally nonnegative matrices (Chapter 8); various aspects of matrix completion problems associated with totally nonnegative matrices (Chapter 9); and a smorgesboard of further interesting topics are surveyed in the final chapter (Chapter 10).
An index and directory of terminology and notation is given at the end, as well as a lengthy list of relevant references, both ones referred to in the text and others of potential interest to readers. It is inevitable, unfortunately, that we may have missed some relevant work in the literature.
The reader should be alerted to an unfortunate schism in the terminology used among authors on this subject. We consistently use “totally nonnegative” and “totally positive” (among a hierarchy of refinements). Some authors use, instead, terms such as “totally positive” (for totally nonnegative) and “strictly totally positive” (for totally positive). This is at odds with conventional terminology for real numbers. We hope that there can be a convergence to the more natural and unambiguous terms over time.
We would like to thank B. Turner for a useful reading of a late draft of our manuscript, and several colleagues and friends for helpful suggestions. Finally, we note that the so-called sign-regular matrices (all minors of a given size share a common sign that may vary from size to size) share many properties with totally nonnegative and totally positive matrices. It could be argued that they present the proper level of generality in which to study certain parts of the structure. We have chosen not to focus upon them (they are mentioned occasionally) in order not to deflect attention from the most important sign-regular classes: namely the totally nonnegative and totally positive matrices.
SMF
CRJ