Totally Nonnegative Matrices (Princeton Series in Applied Mathematics) - Hardcover

Fallat, Shaun M.; Johnson, Charles R.

Hardcover

ISBN 10: 0691121575 ISBN 13: 9780691121574

Verlag: Princeton University Press, 2011

Inhaltsangabe

Totally nonnegative matrices arise in a remarkable variety of mathematical applications. This book is a comprehensive and self-contained study of the essential theory of totally nonnegative matrices, defined by the nonnegativity of all subdeterminants. It explores methodological background, historical highlights of key ideas, and specialized topics.

The book uses classical and ad hoc tools, but a unifying theme is the elementary bidiagonal factorization, which has emerged as the single most important tool for this particular class of matrices. Recent work has shown that bidiagonal factorizations may be viewed in a succinct combinatorial way, leading to many deep insights. Despite slow development, bidiagonal factorizations, along with determinants, now provide the dominant methodology for understanding total nonnegativity. The remainder of the book treats important topics, such as recognition of totally nonnegative or totally positive matrices, variation diminution, spectral properties, determinantal inequalities, Hadamard products, and completion problems associated with totally nonnegative or totally positive matrices. The book also contains sample applications, an up-to-date bibliography, a glossary of all symbols used, an index, and related references.

Über diesen Titel

Über die Autorin bzw. den Autor

Shaun M. Fallat is professor of mathematics and statistics at the University of Regina. Charles R. Johnson is the Class of 1961 Professor of Mathematics at the College of William & Mary.

Von der hinteren Coverseite

"This book is a valuable new reference on the subject of totally nonnegative matrices and its insights will be much appreciated by a broad community of readers interested in matrix theory and its applications."--Charles Micchelli, City University of Hong Kong and State University of New York, Albany

Aus dem Klappentext

"This book is a valuable new reference on the subject of totally nonnegative matrices and its insights will be much appreciated by a broad community of readers interested in matrix theory and its applications."--Charles Micchelli, City University of Hong Kong and State University of New York, Albany

Auszug. © Genehmigter Nachdruck. Alle Rechte vorbehalten.

Totally Nonnegative Matrices

By Shaun M. Fallat Charles R. Johnson

PRINCETON UNIVERSITY PRESS

Copyright © 2011 Princeton University Press
All right reserved.
ISBN: 978-0-691-12157-4

Contents

List of Figures........................................................................xiPreface................................................................................xiiiChapter 0. Introduction................................................................1Chapter 1. Preliminary Results and Discussion..........................................27Chapter 2. Bidiagonal Factorization....................................................43Chapter 3. Recognition.................................................................73Chapter 4. Sign Variation of Vectors and TN Linear Transformations.....................87Chapter 5. The Spectral Structure of TN Matrices.......................................97Chapter 6. Determinantal Inequalities for TN Matrices..................................129Chapter 7. Row and Column Inclusion and the Distribution of Rank.......................153Chapter 8. Hadamard Products and Powers of TN Matrices.................................167Chapter 9. Extensions and Completions..................................................185Chapter 10. Other Related Topics on TN Matrices........................................205Bibliography...........................................................................219List of Symbols........................................................................239Index..................................................................................245

Chapter One

Preliminary Results and Discussion

1.0 INTRODUCTION

Along with the elementary bidiagonal factorization, to be developed in the next chapter, rules for manipulating determinants and special determinantal identities constitute the most useful tools for understanding TN matrices. Some of this technology is simply from elementary linear algebra, but the less well-known identities are given here for reference. In addition, other useful background facts are entered into the record, and a few elementary and frequently used facts about TN matrices are presented. Most are stated without proof, but are accompanied by numerous references where proofs and so on, may be found. The second component features more modern results, some of which are novel to this book. Accompanying proofs and references are supplied for the results in this portion. Since many of the results in later chapters rely on the results contained within this important ground-laying chapter, we trust that all readers will benefit from this preparatory discussion.

1.1 THE CAUCHY-BINET DETERMINANTAL FORMULA

According to the standard row/column formula, an entry of the product of two matrices is a sum of pairwise products of entries, one from each of the factors. The Cauchy-Binet formula (or identity) simply says that much the same is true for minors of a product. A minor of AB is a sum of pair-wise products of minors, one from each factor.

Theorem 1.1.1 (Cauchy-Binet) Let A [element of] M_m,n (IF) and B [element of] M_n,p (IF). Then for each pair of index sets α [subset or equal to] {1, 2, ..., m} and β [subset or equal to] {1, 2, ..., p} of cardinality k, where 1 ≤ k ≤ min(m, n, p), we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1.1)

Proof. The claim is clear for k = 1. In general, it suffices to prove (1.1) for m = p = k by replacing A by A[α,N] and B by B[N, β], in which N = {1, 2, ..., n}; then it suffices to show

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

in which K = {1, 2, ..., k}. If n = k, this is just the multiplicativity of the determinant, and if n < k, there is nothing to show. If k < n, we need only note that the equality follows since the sum of the k-by-k principal minors of BA (the expression on the right above) equals the sum of the k-by-k principal minors of AB (the expression on the left), as AB and BA have the same nonzero eigenvalues ([HJ85]).

This useful identity bears a resemblance to the formula for matrix multiplication (and in fact can be thought of as a generalization of matrix multiplication), and a special case of the above identity is the classical fact that the determinant is multiplicative, that is, if A, B [element of] M_n(IF), then detAB = detAdetB.

Another very useful consequence of the Cauchy-Binet formula is the multiplicativity of compound matrices. If A [element of] M_n(IF) and k ≤ m, n, the (^mk) by- (^nk) matrix of k-by-k minors (with index sets ordered lexicographically) of A is called the kth compound of A and is denoted by C_k(A). The Cauchy-Binet formula is simply equivalent to the statement that each kth compound is multiplicative,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

This means that TP (TN) matrices are closed under the usual product. In fact,

Theorem 1.1.2 For [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

We note, though, that neither TN nor TP matrices in M_m,n are closed under addition.

Example 1.1.3 Observe that both [4/1 15/4] and [4/15 1/4] are TP but their sum [8/16 16/8] has a negative determinant.

It has been shown, however, that any positive matrix is the sum of (possibly several) TP matrices [JO04].

1.2 OTHER IMPORTANT DETERMINANTAL IDENTITIES

In this section we list and briefly describe various classical determinantal identities that will be used throughout this text. We begin with the well-known identity attributed to Jacobi (see, for example, [HJ85]).

Jacobi's identity: If A [element of] M_n(IF) is nonsingular, then the minors of A^-1 are related to those of A by Jacobi's identity. Jacobi's identity states that for α, β [subset or equal to] N, both nonempty, in which |α| = |β|,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1.2)

where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Observe that if α and β are both singletons, that is, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], then (1.2) becomes

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

in which a^-1_ij denotes the (i, j) entry of A^-1. This expression is the classical adjoint formula for the inverse of a matrix, so that Jacobi's identity may be viewed as a generalization of the adjoint formula. When α = β, (1.2) takes the form

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1.3)

We now present some identities discovered by Sylvester (see [HJ85]).

Sylvester's identities: Let A [element of] M_n (IF), α [subset or equal to] N, and suppose |α| = k. Define the (n - k)-by-(n - k) matrix B = [b_ij], with i, j [element of] α^c, by setting b_ij = detA]α [union] {i}, α [union] {j}], for every i, j [element of]...

Details zur Ausgabe

• Verlag: Princeton University Press
• Erscheinungsdatum: 2011
• Sprache: Englisch
• ISBN 10: 0691121575
• ISBN 13: 9780691121574
• Einband: Gebundene Ausgabe
• Anzahl der Seiten: 248
• Kontakt zum Hersteller: Nicht verfügbar
• Verantwortliche Person: Nicht verfügbar