Acerca del 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.

De la contraportada

"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

De la solapa interior

"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

Fragmento. © Reproducción autorizada. Todos los derechos reservados.

Totally Nonnegative Matrices

PRINCETON UNIVERSITY PRESS

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

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] α^c. Then Sylvester's identity states that for each δ, γ [subset] α^c, with |δ| = |γ| = l,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1.4)

Observe that a special case of (1.4) is that detB = (detA[a])n-k-1detA. A very useful consequence of (1.4) is that if A [element of] M_n [intersection] TP (or is TN and detA]α] > 0), then B is also a TP (TN) matrix. This fact is actually quite useful for inductive purposes, for example, when considering distributions of ranks and shadows (see [dBP82] and Chapter 7).

Another very useful special case is the following. Let A [element of] M_n(IF) be the partitioned matrix

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where A₂₂ [element of] M_n-2 (IF) and a₁₁, a₃₃ are scalars. Define the matrices

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

If we let b = detB, c = detC, d = detD, and e = detE, then by (1.4) it follows that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Hence, provided detA₂₂ [not equal to] 0, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1.5)

Karlin's identities: The next identity that we record for minors has appeared in a number of places regarding TP matrices; see, for example, [Kar68, Cry76, FZ99]. In [And87] this identity also appears and is used (as it was in [Kar68]) to prove that membership in the TP can be checked by verifying that all minors based on contiguous rows and columns are positive. We confess that referring to these identities as "Karlin's identities" may give the impression that they are due to Karlin. This is most certainly not the case. This reference is more to indicate that, within the umbrella of total positivity, Karlin was one of the first to utilize this identity and apply it to one of the most fundamental facts about this class of matrices (see [Kar68, pp. 8–10, 58–60]).

This useful identity can be stated in the following manner. Suppose A is an n-by-n matrix, and let α, ω be two index sets of {1, 2, ..., n} with |ω| = n -2, |α| = n - 1 and ω [subset] α. Then the complement of ω, ω^c, is given by ω^c = {a, b}, and the complement of a may be assumed to be α]^c = {a}.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1.6) where q satisfies 1 < q < n.

We will demonstrate the validity of this identity in the case that A is invertible. If A is singular, then one may apply a continuity argument making use of Schur complements and Sylvester's identity (both of which are mentioned above).

Given that A is invertible, we may invoke Jacobi's identity (1.2) to each of the six minors above and realize the equivalent equation

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where B = A^-1. However, the relation is a simple identity to verify on an arbitrary 3-by-2 matrix (namely, the submatrix of B given by B[{1, q, n}, {a, b}]).

Viewing this 3-term identity as a special case of a determinantal identity on a 3-by-2matrix gives insight regarding the potential origin of this equation as a short-term Plücker identity, which is a special case of the more general Plücker relations or quadratic identities for minors.

To motivate the connection with certain types of Plücker coordinates, we consider the following situation. Suppose a and β are given index sets of N with |α| = |β|. Define a third index set γ

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where β^c is the complement of β relative to N. Observe that γ is a subset of {1, 2, ..., 2n}. For example, suppose that n = 8, α = {1, 2, 4, 6}, and β = {2, 3, 6, 7}. Then γ = α [union] {16, 13, 12, 9}. As we will see, the set γ above has a very natural association to a totally positive element in the Grassmannian Gr(n, 2n).

Recall that the Grassmannian Gr(n, 2n) can be interpreted as the collection of all 2n-by-n matrices of rank n, modulo multiplication on the right by an invertible n-by-n matrix. Thus if we are given any n-by-n matrix A, we can embed A in an 2n-by-n matrix, B(A), as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where S is the alternating sign signature matrix and T is the backward identity matrix, both of which are of order n.

It is clear that B(A) is a matrix representation of an element of Gr(n, 2n), as clearly the rank of B(A) is n. Recall that the Plücker coordinate

[p₁, p₂, ..., p_n](B(A)),

where 1 ≤ p₁ < p₂ < ... < p_n = 2n, is defined to be the minor of B(A) lying in rows {p₁, p₂, ..., p_n} and columns {1, 2, ..., n}. That is,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

An element of Gr(n, 2n) is called a totally positive element if it has a matrix representation in which all its Plücker coordinates are positive. We note that these coordinates are determined up to a multiple (often called homogeneous projective coordinates) and hence depend only on A, given the representation B(A) above.

A key fact is the following determinantal identity, which can be verified by Laplace expansion of the determinant. Suppose α, β are two index sets of N of the same size and γ is defined as above. Then for any n-by-n matrix A, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Hence it follows that if A is TP, then B(A) is a matrix representation of a totally positive element in Gr(n, 2n).

One of the fundamental properties or relations that hold for Plücker coordinates are the so-called Plücker relations or quadratic relations. If {i₁, i₂, ... , i_n} and {j₁, j₂, ..., j_n} are two index sets of {1, 2, ..., 2n}, then the following identities hold,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

for each s = 1, 2, ..., n.

By the nature of their definition, if a Plücker coordinate contains a repeated index, it is zero; and if two indices are switched, the coordinate is negated. Taking into account the above, the short Plücker relation often refers to

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where [Delta] [subset] {1, 2, ..., 2n} with |[Delta]| = n - 2, and where 1 ≤ i < i' < j < j' ≤ 2n with i, i', j, j' [??] [Delta].

Consider some illustrative examples. Suppose n = 6, and let [Delta] = {2, 4, 5, 9} and i = 1, i' = 3, j = 6, and j' = 11. Then the corresponding (short) Plücker relation is given by

[1, 6, 2, 4, 5, 9][3, 11, 2, 4, 5, 9] = [1, 3, 2, 4, 5, 9][6, 11, 2, 4, 5, 9]+ [1, 11, 2, 4, 5, 9][3, 6, 2, 4, 5, 9].

Making use of the representation B(A) and the connection between these coordinates and the minors of A, it follows that the short relation above is equivalent to

det A]{1, 2, 4, 5, 6}, {1, 2, 3, 5, 6}] det A]{2, 3, 4, 5}, {1, 3, 5, 6}] = det A]{1, 2, 3, 4, 5}, {1, 2, 3, 5, 6}] det A]{2, 4, 5, 6}, {1, 3, 5, 6}] +det A]{2, 3, 4, 5, 6}, {1, 2, 3, 5, 6}] det A]{1, 2, 4, 5}, {1, 3, 5, 6}],

which is exactly a three-term identity that we referred to as Karlin's identity above.

On the other hand, if n = 6, [Delta] = {2, 5, 7, 10}, i = 1, i' = 4, j = 8, and j' = 12, then the corresponding (short) Plücker relation is given by

[1, 8, 2, 5, 7, 10][4, 12, 2, 5, 7, 10] = [1, 4, 2, 5, 7, 10][8, 12, 2, 5, 7, 10]+ [1, 12, 2, 5, 7, 10][4, 8, 2, 5, 7, 10],

which is equivalent to

det A]{1, 2, 5}, {1, 2, 4}] det A]{2, 4, 5}, {2, 4, 5}] = det A]{1, 2, 4, 5}, {1, 2, 4, 5} det A]{2, 5}, {2, 4}] +det A]{1, 2, 5}, {2, 4, 5} det A]{2, 4, 5}, {1, 2, 4}].

Evidently, this is not of the form of Karlin's identity above.

Recall specifically that Karlin's identity was written for an n-by-n matrix A as

det A({a, b}, {1, n}) det A({a}, {q}) = det A({a, b}, {1, q}) det A({a}, {n}) det A({a, b}, {q, n}) det A({a}, {1}).

Given the above equation, define [Lambda] = N \{1, q, n} and, assuming that a < b, define x = 2n + 1 - b and y = 2n + 1 - a, so that x < y. Then define [Delta] = [Lambda] [union] {x}, i = 1, i' = q, j = n, and j' = y, so that i < i' < j < j' and none of them lie in [Delta]. It then follows that the identity above is equivalent to the short Plücker relation given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

1.3 SOME BASIC FACTS

A TP₁ (TN₁) matrix is simply an entrywise positive (nonnegative) matrix. The theory of these matrices, which is a precursor to the theory of TP (TN) matrices, goes under the heading Perron-Frobenius theory and is a valuable ingredient in the theory of TP/TN matrices. See [HJ85, Ch. 8] for details. Recall that the spectral radius of an n-by-n matrix A is defined to be ρ(A) = max{|λ?|: λ [element of] ω(A)}. As usual, we use ω(A) to denote the collection of all eigenvalues of A, counting multiplicity. We state here the version of Perron's theorem on positive matrices that is most useful for us.

Theorem 1.3.1 If A [element of] M_n [intersection] TP₁, then

(a) the spectral radius ρ(A) [element of] ρ(A);

(b) the algebraic multiplicity of ?(A) as an eigenvalue of A is one;

(c) if λ [element of] ω(A), λ [not equal to] ρ(A), then |λ| < ρ(A); and

(d) associated with ?(A) is an entrywise positive eigenvector x of A.

If A is primitive (nonnegative and some power is positive), the same conclusions remain valid. If A is only entrywise nonnegative, the spectral radius may be zero, but (a) remains valid, while (b), (c), and (d) are weakened in a manner dictated by continuity: the multiplicity can be higher; there can be ties for spectral radius; and a nonnegative eigenvector may have zero components.

A general fact about left (y*A = λy*) and right (Ax = λx) eigenvectors of a square matrix is the principle of biorthogonality.

Proposition 1.3.2 If A is an n-by-n complex matrix with λ, µ [element of] s(A), λ [not equal to]= µ, then any left eigenvector of A corresponding to µ is orthogonal to any right eigenvector of A corresponding to λ.

(Continues...)

Excerpted from Totally Nonnegative Matricesby Shaun M. Fallat Charles R. Johnson Copyright © 2011 by Princeton University Press. Excerpted by permission of PRINCETON UNIVERSITY PRESS. All rights reserved. No part of this excerpt may be reproduced or reprinted without permission in writing from the publisher.
Excerpts are provided by Dial-A-Book Inc. solely for the personal use of visitors to this web site.