Matrix Mathematics

Theory, Facts, and FormulasBy Dennis S. Bernstein

PRINCETON UNIVERSITY PRESS

Copyright © 2009 Princeton University Press
All right reserved.
ISBN: 9780-691-14039-1

Contents

Preface to the Second Edition..............................................xvPreface to the First Edition...............................................xviiSpecial Symbols............................................................xxiConventions, Notation, and Terminology.....................................xxxiii1. Preliminaries...........................................................12. Basic Matrix Properties.................................................853. Matrix Classes and Transformations......................................1794. Polynomial Matrices and Rational Transfer Functions.....................2535. Matrix Decompositions...................................................3096. Generalized Inverses....................................................3977. Kronecker and Schur Algebra.............................................4398. Positive-Semidefinite Matrices..........................................4599. Norms...................................................................59710. Functions of Matrices and Their Derivatives............................68111. The Matrix Exponential and Stability Theory............................707Bibliography...............................................................881Author Index...............................................................967Index......................................................................979

Chapter One

Preliminaries

In this chapter we review some basic terminology and results concerning logic, sets, functions, and related concepts. This material is used throughout the book.

1.1 Logic

Every statement is either true or false, but not both. Let A and B be statements. The negation of A is the statement (not A), the both of A and B is the statement (A and B), and the either of A and B is the statement (A or B). The statement (A or B) does not contradict (A and B), that is, the word "or" is inclusive. Exclusive "or" is indicated by the phrase "but not both."

The statements "A and B or ITLITL" and "A or B and ITLITL" are ambiguous. We therefore write "A and either B or ITLITL" and "either A or both B and ITLITL."

Let A and B be statements. The implication statement "if A is satisfied, then B is satisfied" or, equivalently, "A implies B" is written as A [??] B, while A [??] B is equivalent to [(A [??] B) and (A [??] B)]. Of course, A [??] B means B [??] A. A tautology is a statement that is true regardless of whether the component statements are true or false. For example, the statement "(A and B) implies A" is a tautology. A contradiction is a statement that is false regardless of whether the component statements are true or false. For example, the statement "A implies (not) A" is a contradiction.

Suppose that A [??] B. Then, A is satisfied if and only if B is satisfied. The implication A [??] B (the "only if" part) is necessity, while B [??] A (the "if" part) is sufficiency. The converse statement of A [??] B is B [??] A. The statement A [??] B is equivalent to its contrapositive statement (not B) [??] (not A).

A theorem is a significant statement, while a proposition is a theorem of less significance. The primary role of a lemma is to support the proof of a theorem or proposition. Furthermore, a corollary is a consequence of a theorem or proposition. Finally, a fact is either a theorem, proposition, lemma, or corollary. Theorems, propositions, lemmas, corollaries, and facts are provably true statements.

Suppose that A' [??] A [??] B [??] B'. Then, A' [??] B' is a corollary of A [??] B.

Let A, B, and ITLITL be statements, and assume that A [??] B. Then, A [??] B is a strengthening of the statement (A and ITLITL) [??] B. If, in addition, A [??] C, then the statement (A and ITLITL) [??] B has a redundant assumption.

1.2 Sets

A set {x, y, ...} is a collection of elements. A set may have a finite or infinite number of elements. A finite set has a finite number of elements.

Let X be a set. Then,

x [member of] X (1.2.1)

means that x is an element of X. If w is not an element of X, then we write

w [??] X. (1.2.2)

The statement "x [member of] X" is either true or false, but not both. The statement "X [??] X" is true by convention, and thus no set can be an element of itself. Therefore, there does not exist a set that contains every set. The set with no elements, denoted by Ø, is the empty set. If X ≠ Ø, then X is nonempty.

A set cannot have repeated elements. For example, {x, x} = {x}. However, a multiset is a collection of elements that allows for repetition. The multiset consisting of two copies of x is written as {x, x}_ms. However, we do not assume that the listed elements x, y of the conventional set {x, y} are distinct. The number of distinct elements of the set S or not-necessarily-distinct elements of the multiset S is the cardinality of S, which is denoted by card(S).

There are two basic types of mathematical statements for quantifiers. An existential statement is of the form

there exists x [member of] X such that statement Z is satisfied, (1.2.3)

while a universal statement has the structure

for all x [??] X, it follows that statement Z is satisfied, (1.2.4)

or, equivalently,

statement Z is satisfied for all x [member of] X. (1.2.5)

Let X and Y be sets. The intersection of X and Y is the set of common elements of X and Y given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1.2.6)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1.2.7)

while the set of elements in either X or Y (the union of X and Y) is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1.2.8)

The complement of X relative to Y is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1.2.9)

If Y is specified, then the complement of X is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1.2.10)

If x [member of] X implies that x [member of] Y, then X is contained in Y (X is a subset of Y), which is written as

X [??] Y. (1.2.11)

The statement X = Y is equivalent to the validity of both X [??] Y and Y [??] X. If X [??] Y and X ≠ Y, then X is a proper subset of Y and we write X [subset] Y. The sets X and Y are disjoint if X [intersection] Y = Ø. A partition of X is a set of pairwise-disjoint and nonempty subsets of X whose union is equal to X.

The operations "[intersection]," "[union]," and "\" and the relations "[subset]" and "[??]" extend directly to multisets. For example,

{x, x}_ms [union] {x}_ms = {x, x, x}_ms. (1.2.12)

By ignoring repetitions, a multiset can be converted to a set, while a set can be viewed as a multiset with distinct elements.

The Cartesian product X₁ x ··· x X_n of sets X₁, .. ., X_n is the set consisting of tuples of the form (x₁, ..., x_n), where x_i [member of] X_i for all i [member of] {1, ..., n}. A tuple with n components is an n-tuple. Note that the components of an n-tuple are ordered but need not be distinct.

By replacing the logical operations "[??]," "and," "or," and "not" by "[??]" "[union]," "[intersection]," and "~," respectively, statements about statements A and B can be transformed into statements about sets A and B, and vice versa. For example, the tautology

A and (B or ITLITL) [??} (A and B) or (A and ITLITL)

is equivalent to

A [intersection] (B [union] C) = (A [intersection] B) [inion] (A [intersection] C).

1.3 Integers, Real Numbers, and Complex Numbers

The symbols Z, N, and P denote the sets of integers, nonnegative integers, and positive integers, respectively. The symbols R and C denote the real and complex number fields, respectively, whose elements are scalars. Define

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Let x [member of] C. Then, x = y + jz, where y, z [member of] R. Define the complex conjugate [bar x] of x by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1.3.1)

and the real part Re x of x and the imaginary part Im x of x by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1.3.2)

and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1.3.3)

Furthermore, the absolute value |x| of x is defined by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1.3.4)

The closed left half plane (CLHP), open left half plane (OLHP), closed right half plane (CRHP), and open right half plane (ORHP) are the subsets of C defined by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1.3.5)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1.3.6)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1.3.7)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1.3.8)

The imaginary numbers are represented by jR. Note that 0 is both a real number and an imaginary number.

Next, we define the open unit disk (OUD) and the closed unit disk (CUD) by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1.3.9)

and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1.3.10)

The complements of the open unit disk and the closed unit disk are given, respectively, by the closed punctured plane (CPP) and the open punctured plane, which are defined by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1.3.11)

and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1.3.12)

Since R is a proper subset of C, we state many results for C. In other cases, we treat R and C separately. To do this efficiently, we use the symbol F to consistently denote either R or C.

1.4 Functions

Let X and Y be sets. Then, a function f that maps X into Y is a rule f: X [??] Y that assigns a unique element f(x) (the image of x) of Y to each element x of X. Equivalently, a function f: X [??] Y can be viewed as a subset F of X x Y such that, for all x X, it follows that there exists y [member of] Y such that (x, y) [member of] F and such that, if (x, y₁), (x, y₂) [member of] F, then y₁ = y₂. In this case, F = Graph(f) [??] {(x, f(x)): [Xi]}. The set X is the domain of f, while the set Y is the codomain of f. If f: X [member of] X, then f is a function on X. For X₁ [??] X, it is convenient to define f(X₁) [??] {f(x): x [member of] X₁}. The set f(X), which is denoted by R(f), is the range of f. If, in addition, Z is a set and g: f(X) [??] Z, then g • f: X [??] Z (the composition of g and f) is the function (g • f)(x) [??] g[f(x)]. If x₁, x₂ [member of] X and f(x₁) = f(x₂) implies that x₁ = x₂, then f is one-to-one; if R(f) = Y, then f is onto. The function IX: X [??] X defined by I_X(x) [??] x for all x [member of] X is the identity on X. Finally, x [member of] X is a fixed point of the function f: X [??] X if f(x) = x.

The following result shows that function composition is associative.

Proposition 1.4.1. Let X, Y, Z, and W be sets, and let f: X [??] Y, g: Y [??] Z, h: Z [??] W. Then,

h • (g • f) = (h • g) • f. (1.4.1)

Hence, we write h • g • f for h • (g • f) and (h • g) • f.

Let X be a set, and let [??] be a partition of X. Furthermore, let f: [??] [??] X, where, for all S [member of] [??], it follows that f(S) [member of] S. Then, f is a canonical mapping, and f(S) is a canonical form. That is, for all components S of the partition [??] of X, it follows that the function f assigns an element of S to the set S.

Let f: X [??] Y. Then, f is left invertible if there exists a function g: Y [??] X (a left inverse of f) such that g • f = IX, whereas f is right invertible if there exists a function h: Y [??] X (a right inverse of f) such that f • h = I_Y. In addition, the function f: X [??] Y is invertible if there exists a function f^-1: Y [??] X (the inverse of f) such that f^-1 • f = I_X and f • f^-1 = I_Y. The inverse image f^-1(S) of S [??] Y is defined by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1.4.2)

Note that the set f^-1(S) can be defined whether or not f is invertible. In fact, f^-1[f(X)] = X.

Theorem 1.4.2. Let X and Y be sets, and let f: X [??] Y. Then, the following statements hold:

i) f is left invertible if and only if f is one-to-one.

ii) f is right invertible if and only if f is onto.

Furthermore, the following statements are equivalent:

iii) f is invertible.

iv) f has a unique inverse.

v) f is one-to-one and onto.

vi) f is left invertible and right invertible.

vii) f has a unique left inverse.

viii) f has a unique right inverse.

Proof. To prove i), suppose that f is left invertible with left inverse g: Y [??] X. Furthermore, suppose that x₁, x₂ [member of] X satisfy f(x₁) = f(x₂). Then, x₁ = g[f(x₁)] = g[f(x₂)] = x₂, which shows that f is one-to-one. Conversely, suppose that f is one-to-one so that, for all y [member of] R(f), there exists a unique x [member of] X such that f(x) = y.

Hence, define the function g: Y [??] X by g(y) [??] x for all y = f(x) [member of] R(f) and by g(y) arbitrary for all y [member of] Y\R(f). Consequently, g[f(x)] = x for all x [member of] X, which shows that g is a left inverse of f.

(Continues...)

Excerpted from Matrix Mathematicsby Dennis S. Bernstein Copyright © 2009 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.