A Survey of Matrix Theory and Matrix Inequalities

By Marvin Marcus and Henryk Minc

Written for advanced undergraduate students, this highly regarded book presents an enormous amount of information in a concise and accessible format. Beginning with the assumption that the reader has never seen a matrix before, the authors go on to provide a survey of a substantial part of the field, including many areas of modern research interest.
Part One of the book covers not only the standard ideas of matrix theory, but ones, as the authors state, "that reflect our own prejudices," among them Kronecker products, compound and induced matrices, quadratic relations, permanents, incidence matrices and generalizations of commutativity.
Part Two begins with a survey of elementary properties of convex sets and polyhedra and presents a proof of the Birkhoff theorem on doubly stochastic matrices. This is followed by a discussion of the properties of convex functions and a list of classical inequalities. This material is then combined to yield many of the interesting matrix inequalities of Weyl, Fan, Kantorovich and others. The treatment is along the lines developed by these authors and their successors and many of their proofs are included. This chapter contains an account of the classical Perron Frobenius-Wielandt theory of indecomposable nonnegative matrices and ends with some important results on stochastic matrices.
Part Three is concerned with a variety of results on the localization of the characteristic roots of a matrix in terms of simple functions of its entries or of entries of a related matrix. The presentation is essentially in historical order, and out of the vast number of results in this field the authors have culled those that seemed most interesting or useful. Readers will find many of the proofs of classical theorems and a substantial number of proofs of results in contemporary research literature.

• Language: English
• Publisher: Dover Publications
• Release date: May 5, 2014
• ISBN: 9780486153063

Book preview

A SURVEY OF MATRIX THEORY AND MATRIX INEQUALITIES

MARVIN MARCUS

Professor of Computer Science University of California, Santa Barbara

HENRYK MINC

Professor of Mathematics University of California, Santa Barbara

DOVER PUBLICATIONS, Inc., New York

To Arlen and Catherine

Copyright © 1964 by Marvin Marcus and Henryk Mine.

Ail rights reserved under Pan American and International Copyright Conventions.

This Dover edition, first published in 1992, is an unabridged, unaltered republication of the corrected (1969) printing of the work first published by Prindle, Weber & Schmidt, Boston, 1964, as Volume Fourteen of The Prindle, Weber & Schmidt Complementary Series in Mathematics.

Library of Congress Cataloging-in-Publication Data

Marcus, Marvin, 1927–

A survey of matrix theory and matrix inequalities / Marvin Marcus, Henryk Mine,

p. cm.

Originally published: Boston : Prindle, Weber & Schmidt, 1969.

Includes bibliographical references.

eISBN 13: 978-0-486-15306-3

1. Matrices. I. Mine, Henryk. II. Title.

QA188.M36 1992

512.9′434—dc20

91-39704

CIP

Manufactured in the United States by Courier Corporation

67102X05

www.doverpublications.com

Preface

MODERN MATRIX THEORY is a subject that has lately gained considerable popularity both as a suitable topic for undergraduate students and as an interesting area for mathematical research. Apart from aesthetic reasons this is a result of the widespread use of matrices in both pure mathematics and the physical and social sciences.

In this book we have tried within relatively few pages to provide a survey of a substantial part of the field. The first chapter starts with the assumption that the reader has never seen a matrix before, and then leads within a short space to many ideas which are of current research interest. In order to accomplish this within limited space, certain proofs that can be found in any of a very considerable list of books have been left out. However, we have included many of the proofs of classical theorems as well as a substantial number of proofs of results that are in the current research literature. We have found that a subset of the material covered in Chapter I is ample for a one-year course at the third- or fourth-year undergraduate level. Of course, the instructor must provide some proofs but this is in accordance with our own personal preference not to regurgitate definition-theorem-proof from the printed page. There are many ideas covered in Chapter I that are not standard but reflect our own prejudices: e.g., Kronecker products, compound and induced matrices, quadratic relations, permanents, incidence matrices, (v, k, λ) configurations, generalizations of commutativity, property L.

The second chapter begins with a survey of elementary properties of convex sets and polyhedrons and goes through a proof of the Birkhoff theorem on doubly stochastic matrices. From this we go on to the properties of convex functions and a list of classical inequalities. This material is then put together to yield many of the interesting matrix inequalities of Weyl, Fan, Kantorovich, and others. The treatment is along the lines developed by these authors and their successors and many of the proofs are included. This chapter contains an account of the classical Perron- Frobenius-Wielandt theory of indecomposable nonnegative matrices and ends with some very recent results on stochastic matrices.

The third chapter is concerned with a variety of results on the localization of the characteristic roots of a matrix in terms of simple functions of its entries or of entries of a related matrix. The presentation is essentially in historical order, and out of the vast number of results in this field we have tried to cull those that seemed to be interesting or to have some hope of being useful.

In general it is hoped that this book will prove valuable in some respect to anyone who has a question about matrices or matrix inequalities.

MARVIN MARCUS

HENRYK MINC

The present edition is unaltered except for minor typographical corrections.

M. M.

H. M.

August, 1969

Contents

I. SURVEY OF MATRIX THEORY

1. INTRODUCTORY CONCEPTS

Matrices and vectors. Matrix operations. Inverse, Matrix and vector operations. Examples. Transpose. Direct sum and block multiplication. Examples. Kronecker product. Example.

2. NUMBERS ASSOCIATED WITH MATRICES

Notation. Submatrices. Permutations. Determinants. The quadratic relations among svbdeterminants. Examples. Compound matrices. Symmetric functions; trace. Permanents. Example. Properties of permanents. Induced matrices. Characteristic polynomial. Examples. Characteristic roots. Examples, Rank. Linear combinations. Example. Linear dependence; dimension. Example.

3. LINEAR EQUATIONS AND CANONICAL FORMS

Introduction and notation. Elementary operations. Example. Elementary matrices. Example. H ermite normal form. Example. Use of the Hermite normal form in solving Ax = b. Example. Elementary column operations and matrices. Examples. Characteristic vectors. Examples. Conventions for polynomial and integral matrices. Determinants divisors. Examples. Equivar lerue. Example. Invariant factors. Elementary divisors. Examples. Smith normal form. Example. Similarity. Examples. Elementary divisors and similarity. Example. Minimal polynomial. Companion matrix. Examples. Irredudbility. Sim ilarity to a diagonal matrix. Examples.

4. SPECIAL CLASSES OF MATRICES, COMMUTATIVITY

Bilinear functional. Examples. Inner product. Example. Orthogonality. Example. Normal matrices. Examples. Circur lard. Unitary similarity. Example. Positive definite matrices. Example. Functions of normal matrices. Examples. Exponentied of a matrix. Functions of an arbitrary matrix. Example. Representation of a matrix as a function of other matrices. Examples. Simultaneous reduction of commuting matrices. Commutativity. Example. Quasi-commutativity. Example. Property L. Examples. Miscellaneous results on commutativity.

5. CONGRUENCE

Definitions. Triple diagonal form. Congruence and elementary operations. Example. Relationship to quadratic forms. Example. Congruence properties. Hermitian congruence. Example. Triangular product representation. Example. Conjunctive reduction of skew-hermitian matrices. Conjunctive reduction of two hermitian matrices.

II. CONVEXITY AND MATRICES

1. CONVEX SETS

Definitions. Examples. Intersection property. Examples. Convex polyhedrons. Example. Birkhoff theorem. Simplex. Examples. Dimension. Example. Linear functionals. Example.

2. CONVEX FUNCTIONS

Definitions. Examples. Properties of convex functions. Examples.

3. CLASSICAL INEQUALITIES

Power means. Symmetric functions. Holder inequality. Min* kowski inequality. Other inequalities. Example.

4. CONVEX FUNCTIONS AND MATRIX INEQUALITIES

Convex functions of matrices. Inequalities of H. Weyl. Kantorovich inequality. More inequalities. Hadamard product.

5. NONNEGATIVE MATRICES

Introduction. Indecomposable matrices. Examples. Fully indecomposable matrices. Perron-Frobentus theorem. Example. Nonnegative matrices. Examples. Primitive matrices. Example. Doubly stochastic matrices. Examples. Stochastic matrices.

III. LOCALIZATION OF CHARACTERISTIC ROOTS

1. BOUNDS FOR CHARACTERISTIC ROOTS

Introduction. Bendixson’s theorems. Hirsch’s theorems. Schur’s inequality (1909). Browne’s theorem. Perron’s theorem. Schneider’s theorem.

2. REGIONS CONTAINING CHARACTERISTIC ROOTS OF A GENERAL MATRIX

Lévy-Desplanques theorem. Gerŝgorin discs. Example. Ovals of Cassini. Ostrowski’s theorem. Fan’s theorem.

3. CHARACTERISTIC ROOTS OF SPECIAL TYPES OF MATRICES

Nonnegative matrices. Example. Stability matrices. Row stochastic matrices. Normal matrices. Hermitian matrices. Jacobi, or triple diagonal matrices.

4. THE SPREAD OF A MATRIX

Definition. Spread of a general matrix. Spread of a normal matrix.

5. THE FIELD OF VALUES OF A MATRIX

Definitions. Properties of the field of values.

INDEX

Special Notation

CHAPTER I

R—real numbers.

C—complex numbers.

I—integers.

P—nonnegative real numbers.

F[λ]—polynomial in λ with coefficients in F.

Mm,n(F)—m × n matrices with entries in F.

Mn(F)—n-square matrices with entries in F.

A(i)—ith row of A.

A(j)—jth column of A.

Fk—set of k-tuples of numbers from F.

0m,n—m × n zero matrix.

In—n-square identity matrix.

0n—n-tuple of zeros.

AT—transpose of A.

A*—conjugate transpose of A.

A—conjugate of A.

A B —direct sum.

A ⊗ B—Kronecker product.

Qk,n—totality of strictly increasing sequences of k integers chosen from 1, ···, n.

Gk,n—totality of nondecreasing sequences of k integers chosen from 1, ···, n.

Dk,n—totality of sequences of k distinct integers chosen from 1, ···, n.

Sk,n—totality of sequences of k integers chosen from 1, ···, n.

Ek(a)—kth elementary symmetric function of the numbers a = (a1, ···, an).

A[α|β], A[α|β), A(α|β], A(α|β)—submatrices of A using rows numbered α and columns numbered β, rows α and columns complementary to β, etc. Here α and β are sequences of integers.

Sn—symmetric group of degree n.

d(A)—determinant of A.

Cr(A)—rth compound matrix of A.

u1 ∧ ··· ∧ ur—skew-symmetric product of the vectors u1, ···, ur.

Ek(A)—sum of all k-square principal subdeterminants of A.

tr (A)—trace of A.

p(A)—permanent of A.

Pr(A)—rth induced matrix of A.

u1 ··· ur—symmetric product of the vectors u1, ···, ur.

λi(A)—a characteristic root of A.

ρ(A)—rank of A.

ei—the n-tuple with 1 as ith coordinate, 0 otherwise.

〈x1, ···, xk〉—space spanned by x1, ···, xk.

η(A)—nullity of A.

I(i)(j)— interchange rows i and j.

II(i)+e(j)—add c times row j to row i.

IIIe(i) multiply row i by c.

I(i),(j)—interchange columns i and j.

II(i)+e(j)—add c times column j to column i.

IIIe(i)—multiply column i by c.

a | b—a divides b.

C(p(λ))—companion matrix of p(λ).

H(p(λ))—hypercompanion matrix of p(λ).

diag (a1, ···, an)—the diagonal matrix with a1, ···, an down the main diagonal.

CHAPTER II

U—(in Chapter II) either of the sets Rn or Mm,n(R).

〈x1, ··· , xk)⊥—the orthogonal complement of the vector space spanned by x1 ···, xk.

Dn—set of all real n-square matrices with row and column sums equal to 1.

Ωn—set of all n-square doubly stochastic matrices.

H(X)—convex hull of X.

A * B—Hadamard product (the i,j entry is aijbij).

CHAPTER III

In Sections 1.2, 1.3, 1.4, and 1.6, the following special notation is used: for A ∈ Mn(C) let B = (A + A*)/2, C = (A – A*)/2i; let λ1 ···, λn

be the characteristic roots of A, B, and C .

In Sections 1.6, 2.1, 2.2, 2.4, and 2.5; if A ∈ Mn(C), then denotes the sum of the absolute values of the entries in row i; Ti is the sum of the absolute values of the entries in column i; R is the largest of the Ri; T is the largest of the Ti; Pi = Ri – |aii|; Qi = Ti – |aii|.

s(A)—the spread of A.

||A||—Euclidean norm of

.

The Numbering System

WITHIN THE TEXT of a chapter a reference to a section in that chapter will give only the number of the section. A reference to a section in some other chapter will be preceded by the number of that chapter. Thus, if in the text of Chapter II we wish to refer to Section 2.12 of Chapter I we write "(see I.2.12). Exhibited formulas are referred to by the section number followed by the formula number in parentheses. Thus, if in the text of Chapter III we wish to refer to formula (2) of Section 3.4 of Chapter I, we write [see I.3.4(2)]."

Survey of Matrix Theory

I

1 Introductory Concepts

1.1 Matrices and vectors

In this book we will be dealing with the following sets:

(i) The field of real numbers R.

(ii) The field of complex numbers C.

(iii) The ring of all integers (positive, negative, and zero) I.

(iv) The set of all nonnegative real numbers P.

(v) The ring of polynomials in some indeterminate (variable) λ with real (complex) coefficients R[λ] (C[λ]).

Let F be any one of these sets and suppose that a11, a12, a13, ···, amn is a collection of mn elements in F. The rectangular array of these elements

consisting of m rows and n columns is called an m × n matrix. We write A = (aij). A more formal but less suggestive definition is this: a matrix A is a function on the set of pairs of integers (i,j), 1 ≤ i ≤ m, 1 ≤ j ≤ n, with values in F in which aij designates the value of A at the pair (i,j). The array 1.1(1) is then just a convenient way of exhibiting the range of the function A. The element aij is called the (i,j) entry of A. The ith row of A is the sequence ai1, ai2, ···, ain, and the jth column is the sequence a1j, a2j, ···, amj. Since the aij are in F, we say that A is an m × n matrix over F. The totality of such matrices will be designated by Mm,n(F). In case n = m, we say that A is an n-square matrix. Denote by Mn(F) the set of all n-square matrices over F. A row (column) vector over F is just an element of M1,n(F) (Mm,1(F)). If A ∈ Mm,n(F), then A(i) = (ai1, ···, ain ∈ M1,n(F), (i = 1, ···, m), designates the ith row vector of A. Similarly, the column vector A(i) ∈ Mm,1(F) designates the m × 1 matrix whose (i,j) entry is aij, (i = 1, ···, m). The (i,j) entry of A is sometimes designated by Aij also. In general, a k-vector v over F is just an ordered k-tuple of elements of F, (a1, a2, ···, ak); ai is called the ith coordinate of v. The k-vector every one of whose coordinates is 0 will be denoted by 0 also. In case it is necessary to designate its size, we write 0k. The totality of k-vectors over F is denoted by Fk. In case F = C, v = (a1, a2, ···, ak) ∈ Ck, then v denotes the vector (a1, a2, ···, ak). Two special matrices are the n-square identity matrix In ∈ Mn(F) and the m × n zero matrix 0m,n ∈ Mm,n(F). The (i,j) entry of In is 0 unless i = j, in which case it is 1. That is, the (i,j) entry of In is the Kronecker delta, δij = 0 if i ≠ j, δij = 1 if i = j. The (i, j) entry of 0m,n is 0 for every i and j.

1.2 Matrix operations

Three standard operations for matrices over F are defined below.

1.2.1 Multiplication of A = (aij) ∈ Mm,n(F) by a scalar, i.e., an element c ∈ F. The product is defined as the matrix in Mm,n(F) whose (i,j) entry is caij and is designated by cA.

1.2.2 The sum of two matrices A = (aij) and B = (bij) in Mm,n(F) is the matrix C = (cij) ∈ Mm,n(F) whose (i,j) entry is cij = aij + bij. Observe that the matrices A and B must be the same size in order that the sum be defined.

1.2.3 The product of two matrices A = (aij) ∈ Mm,k(F) and B = (bij) ∈ Mk,n(F) is the matrix C = (cij) ∈ Mm,n(F) whose (i,j) entry is

We write C = AB, using simply proximity to indicate the product. Observe that in order for the product C = AB to be defined the number of columns of A must be the same as the number of rows of B. If A ∈ Mn(F), we use the notation A² to designate the product AA; A³ = AA², and in general Ar = AAr–1 for any positive integer r. The matrix Ar is called the rth power of A for obvious reasons.

1.2.4 The rules connecting these operations are:

(i) Commutativity: A + B = B + A. However, AB ≠ BA in general. If AB = BA, then A and B are said to commute.

(ii) Associativity: A + (B + C) = (A + B) + C; A(BC) = (AB)C. The common values of these sums (products) are written without parentheses: A + B + C (ABC).

(iii) Distributivity: A(B + C) = AB + AC, (B + C)A = BA + CA.

Of course all the matrices in (i), (ii), and (iii) must be of appropriate sizes for the indicated operations to be defined.

1.3 Inverse

If A ∈ Mn(F), it is sometimes the case that there exists a matrix B ∈ Mn(F) such that BA = AB = In. If this happens, A is said to be nonsingular. If no such B exists, then A is called singular. If A is nonsingular, then B is uniquely determined by the equation AB = In or by BA = In The matrix B is called the inverse of A, and the notation A–1 is used to designate B. If r is a positive integer, then A–r denotes the matrix (A–1)r; A⁰ = In. The usual laws of exponents Ap+q = ApAq and (Ap)q = Apq work for any A if p and q are