Lecture Notes on Matrices with Positive Principal Minors ...

Lecture Notes on Matrices with Positive Principal Minors: Theory

and Applications

Michael Tsatsomeros

Mathematics and Statistics

Washington State University

Pullman, WA 99164

(tsat@wsu.edu)

December 16, 2017

Indian Institute of Technology - Madras

December 2017

1

1

Introduction

An n ¡Á n complex matrix A ¡Ê Mn (C) is called a P-matrix if all its principal minors are positive.

Recall that a principal minor is simply the determinant of a submatrix obtained from A when the

same set of rows and columns are stricken out. The diagonal entries and the determinant of A are

thus among its principal minors. We shall denote the class of complex P-matrices by P .

The P-matrices encompass such notable classes as the positive definite matrices, the M-matrices

and the totally positive matrices. Indeed, the study of P-matrices originated in the context of these

classes in the work of Ostrowski, Fan, Koteljanskij, Gantmacher & Krein, Taussky, Fiedler & Ptak,

Tucker, and Gale & Nikaido. Some classical references to this early work include [24, 25, 28, 29, 75].

The first systematic study of P-matrices appears in the work of Fiedler & Ptak [25]. Since

then, the class P and its subclasses have proven a fruitful research subject, judged by the attention

received in the matrix theory community and the continuing interest generated by the applications

of P-matrices in the mathematical sciences.

Indeed, P-matrices play an important role in a wide range of applications, including the linear

complementarity problem, global univalence of maps, linear differential inclusion problems, interval

matrices and computational complexity. Some of these applications are discussed in this chapter;

see also [5, 7, 10, 64].

Of particular concern is the ability to decide as efficiently as possible whether an n-by-n matrix

is in P or not, referred to as the P-problem. It has received attention partly due to its inherent

computational complexity. Motivated by the P-problem and questions about the spectra of Pmatrices, in this chapter we address the need to construct (generic and special) P-matrices for

purposes of experimentation, as well as theoretical and algorithmic development. To this end, in

this chapter we provide a review of

(i) basic properties of P-matrices and operations that preserve them;

(ii) techniques to generate P-matrices;

(iii) numerical methods to detect P-matrices;

(iv) manifestations of P-matrices in various mathematical contexts.

This approach affords us the opportunity to review well-known results, some of them presented

under new light, as well as to bring forth some less known and some new results on P-matrices.

Other comprehensive treatments of P-matrix theory can be found in [10, 23, 42].

This chapter unfolds as follows: Section 2 contains notation and definitions. Section 3 reviews

basic properties and characterizations of P-matrices, including mappings of P into itself. Section

4 contains facts and questions about the eigenvalues of P-matrices. Section 5 describes methods to

generate P-matrices, some of which yield P-matrices with additional properties. Section 6 contains

a closer examination of a special subclass of the P-matrices (mimes) that encompasses the M-

2

matrices and their inverses. Section 7 provides an algorithmic resolution of the general P-problem,

as well as approaches suitable for special subclasses of the P-matrices. Section 8 concerns the

topological closure of P , specifically, the adaptation of results for P to the class of matrices with

nonnegative principal minors. Section 9 reviews manifestations and applications of P-matrices in

various mathematical contexts. The chapter concludes with Section 10 in which further P-matrix

considerations, generalizations and related facts are collected.

2

Notation, definitions and preliminaries

2.1

General notation

The transpose of a complex array X is denoted by X T and its conjugate transpose by X ? . Entrywise

ordering of real arrays of the same size is indicated by ¡Ý . We write X > Y if X, Y are real and

every entry of X ? Y is positive. The indication of a matrix interval [X, Y ] presumes that Y ¡Ý X

and denotes the set of all real matrices each of whose entry lies in the interval whose endpoints are

the corresponding entries of X and Y .

A vector x ¡Ê Cn is called a unit vector if kxk2 = 1. Let n be a positive integer and A ¡Ê Mn (C).

The following notation is also used:

? hni = {1, 2, . . . , n}.

? The i-th entry of a vector x is denoted by xi .

? ¦Ò(A) denotes the spectrum of A.

? ¦Ñ(A) = max{|¦Ë| : ¦Ë ¡Ê ¦Ò(A)} is the spectral radius of A.

? diag(d1 , d2 , . . . , dn ) is the diagonal matrix with diagonal entries d1 , d2 . . . , dn .

? For ¦Á ? hni, |¦Á| denotes the cardinality of ¦Á and ¦Á = hni \ ¦Á.

? A[¦Á, ¦Â] is the submatrix of A whose rows and columns are indexed by ¦Á, ¦Â ? hni, respectively;

the elements of ¦Á, ¦Â are assumed to be in ascending order. When a row or column index set is empty,

the corresponding submatrix is considered vacuous and by convention has determinant equal to 1.

We abbreviate A[¦Á, ¦Á] by A[¦Á] and refer to it as a principal submatrix of A.

2.2

Matrix transforms

Definition 2.1 Given A ¡Ê Mn (C) and ¦Á ? hni such that A[¦Á] is invertible, A/A[¦Á] denotes the

Schur complement of A[¦Á] in A, that is,

A/A[¦Á] = A[¦Á] ? A[¦Á, ¦Á]A[¦Á]?1 A[¦Á, ¦Á].

3

Definition 2.2 Given a nonempty ¦Á ? hni and provided that A[¦Á] is invertible, we define the

principal pivot transform of A ¡Ê Mn (C) relative to ¦Á as the matrix ppt (A, ¦Á) obtained from A by

replacing

A[¦Á]

by A[¦Á]?1 ,

A[¦Á, ¦Á] by ?A[¦Á]?1 A[¦Á, ¦Á],

A[¦Á, ¦Á] by A[¦Á, ¦Á]A[¦Á]?1

A[¦Á]

by

A/A[¦Á].

By convention, ppt (A, ?) = A. To illustrate this definition, when ¦Á = {1, 2, . . . , k} (0 < k < n), we

have that

"

#

A[¦Á]?1

?A[¦Á]?1 A[¦Á, ¦Á]

ppt (A, ¦Á) =

.

A[¦Á, ¦Á]A[¦Á]?1

A/A[¦Á]

Definition 2.3 For A ¡Ê Mn (C) with ?1 6¡Ê ¦Ò(A), the fractional linear map FA ¡Ô (I +A)?1 (I ?A) is

called the Cayley transform of A. The map A ¡ú FA is an involution, namely, A = (I +FA )?1 (I ?FA ).

2.3

Conditions on the entries and stability

Definition 2.4 We call A = [aij ] ¡Ê Mn (C) row diagonally dominant if for all i ¡Ê hni,

X

|aii | >

|aij |.

j6=i

Note that in our terminology the diagonal dominance is strict. Due to Gers?gorin¡¯s Theorem [41,

Theorem 6.1.1], row diagonally dominant matrices with positive diagonal entries are positive stable,

namely, their eigenvalues lie in the open right half of the complex plane.

Definition 2.5 We call A = [aij ] ¡Ê Mn (R) a B-matrix if for each i ¡Ê hni and all j ¡Ê hni \ {i},

n

X

aik > 0

n

1 X

aik > aij ;

n

and

k=1

k=1

namely, the row sums of a B-matrix are positive and the row averages dominate the off-diagonal

entries. The properties and applications of B-matrices are studied in [65].

2.4

Matrix positivity classes

Recall that P denotes the complex P-matrices (of a given order determined by the context), that is,

matrices all of whose principal minors are positive. We also let PM denote the class of matrices all

of whose positive integer powers are in P.

We refer to an array X as nonnegative (resp., positive) if its entries are nonnegative (resp.,

positive) and we write X ¡Ý 0 (resp., X > 0).

4

We call a matrix A ¡Ê Mn (C) semipositive if there exists vector x ¡Ý 0 such that Ax > 0. Notice

that by continuity of the map x ¡ú Ax , semipositivity of A is equivalent to the existence of x > 0

such that Ax > 0.

A positive stable matrix A ¡Ê Mn (C) is a matrix all of whose eigenvalues lie in the open right-half

plane.

A positive definite matrix A ¡Ê Mn (C) is a hermitian (i.e., A = A? ) P-matrix.

A totally positive matrix is a square matrix all of whose (principal and non-principal) minors are

positive.

A Z-matrix is a square matrix all of whose off-diagonal entries are non-positive. An (invertible)

M-matrix is a positive stable Z-matrix or, equivalently, a semipositive Z-matrix. An inverse M-matrix

is the inverse of an M-matrix (see [10, 42] for general background on M-matrices and Z-matrices).

An MMA-matrix is a matrix all of whose positive integer powers are irreducible M-matrices (see

Section 2.5 for the definition of irreducibility).

It is known that an M-matrix A can be written as A = sI ? B, where B ¡Ý 0 and s > ¦Ñ(B). The

Perron-Frobenius Theorem applied to B and B T implies that A possesses right and left nonnegative

eigenvectors x, y, respectively, corresponding to the eigenvalue s ? ¦Ñ(B). We refer to x and y as

right and left Perron eigenvectors of A, respectively. When B is also irreducible, it is known that

s ? ¦Ñ(B) is a simple eigenvalue of A and that x > 0 and y > 0.

The companion matrix of A = [aij ] ¡Ê Mn (C), denoted by M(A) = [bij ], is defined by

(

?|aij | if i 6= j

bij =

|aii | otherwise.

We call A ¡Ê Mn (C) an H-matrix if M(A) is an M-matrix.

The following class of matrices was defined by Pang in [62, 63], extending notions introduced in

the work of Mangasarian and Dantzig. Such matrices were called ¡®hidden Minkowski matrices¡¯ in

[63]; we adopt a different name for them, indicative of their matricial nature and origin.

Definition 2.6 Consider a matrix A ¡Ê Mn (R) of the form

A = (s1 I ? P1 ) (s2 I ? P2 )?1 ,

where s1 , s2 ¡Ê R , P1 , P2 ¡Ý 0, such that for some vector u ¡Ý 0,

P1 u < s1 u and P2 u < s2 u.

We call A a mime, an acronym for M-matrix and Inverse M-matrix Extension, because the class of

mimes contains the M-matrices (by taking P2 = 0, s2 = 1) and their inverses (by taking P1 = 0, s1 =

1). We refer to the positive vector u above as a common semipositivity vector of A.

5

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download