Dantzig G., Thapa M. Linear programming. Vol.1. Introduction

Подождите немного. Документ загружается.

322 LINEAR ALGEBRA

Deﬁnition (Vector Norm): The norm of a vector is a continuous function

with the following properties:

1. ||x|| ≥ 0; with equality holding if and only if x =0.

2. ||αx|| = |α|||x|| for any scalar α.

3. ||x + y||≤||x|| + ||y||.

The p-norm of an n-dimensional vector x is denoted by ||x||

and is deﬁned to be

||x||





i=1



1/p

. (A.15)

The most commonly used norms are deﬁned for p =1(1-norm), p =2(2-norm),

and p = ∞ (∞-norm). These are illustrated below:

(a) ||x||



i=1

|, (1-norm)

(b) ||x||

√

x =





i=1



1/2

, (2-norm or Euclidean norm)

∞

= max

i=1,...,n

|. (∞-norm)

Unless otherwise stated, the symbol “||·||” will always denote the 2-norm.

Example A.3 (Relative Error Using the ∞-Norm) The relative error in the ∞-

norm is given by

||x − ˆx||

∞

||x||

∞

where x is the true solution of some problem and ˆx is the computed solution of the

same problem. It turns out that by using the ∞-norm if e

=10

−t

then we can expect

approximately t correct signiﬁcant digits in the largest component of the computed solution

ˆx. Let x =(0.5432, 8.789)

and let the computed solution be ˆx =(0.5213, 8.790)

. Then

=0.002492 ≈ 10

−3

, implying that the largest component of ˆx has approximately three

correct signiﬁcant digits, which is clearly true for ˆx

in this example. Nothing is implied

about the number of correct digits in other components; in this example, ˆx

has only one

correct siginiﬁcant digit.

The cosine of angle θ between two vectors x and y in 

is given by

cos θ =

||x||

||y||

. (A.16)

Now, the cosine is bounded in absolute value by 1. Thus, this gives us a useful in-

equality for proving various theoretical results, i.e., the Cauchy-Schwartz inequality,

which is

y|≤||x||

||y||

. (A.17)

 Exercise A.3 Show that the Cauchy-Schwartz inequality (A.17) does not hold for the

∞-norm. Does it hold for the 1-norm?

A.5 NORMS 323

Deﬁnition (Matrix Norm): The norm of a matrix is a continuous function

with the following properties:

1. ||A|| ≥ 0; with equality holding if and only if A =0.

2. ||αA|| = |α|||A|| for any scalar α.

3. ||A + B||≤||A|| + ||B||.

4. ||AB||≤||A||||B||.

Note: Strictly speaking, a matrix norm need not satisfy the submultiplicative prop-

erty ||AB||≤||A||||B||; however, we have assumed it because all the matrix norms

that we work with in this book do satisfy this property.

 Exercise A.4 Deﬁne a matrix norm by

||A||

= max

i,j

Construct an example to show that it satisﬁes matrix norm properties 1, 2, and 3, but not

the sub-multiplicative property 4.

Deﬁnition (Vector Induced Matrix Norm): A matrix norm is said to be in-

duced by a vector norm if it is deﬁned as follows:

||A|| = max

||x||=0

||Ax||

||x||

where the norms on the right-hand side are vector norms. Equivalently, the

deﬁnition is sometimes stated as

||A|| = max

||x||=1

||Ax||.

Some speciﬁc examples of matrix norms are:

(a) ||A||

= max

j=1,...,n



i=1

|, (1-norm)

(b) ||A||

max

A), (2-norm)

∞

= max

i=1,...,m



j=1

|,(∞-norm)

(d) ||A||

(

)



i=1



j=1

, (Frobenius norm)

324 LINEAR ALGEBRA

where λ

max

A) is the largest eigenvalue of A

A (see Section A.12 for a deﬁntion

of eigenvalues).

The 1-norm, 2-norm, and ∞-norm are norms that are induced by the corre-

sponding vector norms. The Frobenius norm on the other hand is not a vector

induced norm (V-norm) as can be easily seen by considering the identity matrix:

||I||

√

n; whereas ||I||

= max

||x||=0

||Ix||

||x||

=1.

 Exercise A.5 Show that the 1-norm, 2-norm, and ∞-norm are norms that are induced

by the corresponding vector norms.

From the deﬁnition of a vector-induced norm, it is straightforward to see that a

matrix norm that is vector induced satisﬁes

||Ax||≤||A||||x||. (A.18)

Deﬁnition (Compatible (or Consistent) Norms): In general, any vector norm

||·||and any matrix norm ||·||



are said to be compatible,orconsistent, if they

satisfy the following inequality:

||Ax||≤||A||



||x||.

From (A.18) it follows that every vector norm and its vector-induced matrix norm

are compatible.

 Exercise A.6 Show that the Frobenius matrix norm and the Euclidean vector norm

are compatible, that is, ||Ax||

≤||A||

||x||

 Exercise A.7 Show that given any vector x, for any two vector norms ||·||and ||·||



there exist two scalars α and β that depend only on the dimension of x such that

α||x||≤||x||



≤ β||x||.

A.6 VECTOR SPACES

Vector spaces play an important role in the development of the theory of active set

methods for linear programming.

Deﬁnition (Vector Space): A set of vectors is said to form a vector space if

they satisfy the following two properties:

1. The sum of any two vectors in the space also lies in the space.

A.6 VECTOR SPACES 325

2. If we multiply any vector by a scalar, then the multiple also lies in the

space.

In other words a vector space is a set of vectors that is closed under vector addition

and closed under scalar multiplication.

A set of any n linearly independent n-dimensional vectors can be used to deﬁne

an n-dimensional vector space. This n-dimensional space is denoted by 

(for an

n-dimensional real space) or by E



for an n-dimensional Euclidean space when the

distance between two vectors x, y ∈

is given by



i=1

− y

)



Deﬁnition (Subspace): A subset of a vector space that is a vector space in

its own right is called a subspace. Thus, a subset of k linearly independent

vectors in 

could be used to deﬁne a k-dimensional subspace of the vector

space 

Deﬁnition (Span): If a vector space V consists of all linear combinations of a

particular set of vectors {w

,... ,w

}, then these vectors are said to span

the vector space V .

Deﬁnition (Basis): A spanning set of vectors that are linearly independent

are said to form a basis for the vector space.

Deﬁnition (Dimension of a Vector Space): The dimension of a vector space

(subspace) is the number of linearly independent vectors that span the vector

space (subspace).

Deﬁnition (Complementary Subspace, Null Space): For every proper sub-

space S ⊂

, there is a complementary subspace S ⊂

, whose members

are deﬁned as follows: if y ∈

S and x ∈ S, then x

y = 0. That is, y is

orthogonal to every vector in S. The subspace

S is termed the orthogonal

complement of S, and the two subspaces are completely disjoint except for

the origin. The vector subspace

S is also called the null space with respect to

S, and S is called the null space with respect to

S. If the dimension of S is

k, then the dimension of

S is n − k. The vector subspace S ⊂

is therefore

deﬁned by k basis vectors, and

S ⊂

is deﬁned by n − k basis vectors.

 Exercise A.8 Show that if the k basis vectors in S are orthogonal to each of the n −k

basis vectors in

S, then the subspaces deﬁned by each of these sets of basis vectors are

orthogonal complements of each other.

Deﬁnition (Null Space of a Matrix): Let A be an m × n matrix of rank r ≤ m

where m ≤ n. The rows of A belong to 

. The orthognal complement to the

326 LINEAR ALGEBRA

subspace generated by the rows of A is referred to as the null space of A and

has dimension n − r.

A.7 RANK OF A MATRIX

Analogous to the dimension of a vector space is the rank of a matrix.

Deﬁnition (Rank of a Matrix): The rank of a matrix is the number of linearly

independent rows (or columns). A matrix can only have one rank regardless

of the number of rows and columns.

Deﬁnition (Column Rank of a Matrix): The row rank of a matrix is the

dimension of the vector subspace spanned by the rows of A.

Deﬁnition (Row Rank of a Matrix): The column rank of a matrix is the

dimension of the vector subspace spanned by the columns of the matrix.

Deﬁnition (Full Rank):Anm × n matrix (with m ≤ n) is said to be of full

rank if it has rank m.

Note: The deﬁnition of rank implies that row rank is equal to column rank.

A.8 MATRICES WITH SPECIAL

STRUCTURE

Matrices with special structure play an important role in optimization and in the

solution of systems of equations.

Deﬁnition (Diagonal Matrix): A matrix is a diagonal matrix if all its oﬀ-

diagonal elements are zero.

A diagonal matrix is usually denoted by the letter D.

Example A.4 (Diagonal Matrix) An example of an n × n diagonal matrix is

D =







0 ... 0

0 d

... 0

00... d







Deﬁnition (Identity Matrix): A square diagonal matrix with all diagonal

elements equal to 1 is called an identity matrix.

A.8 MATRICES WITH SPECIAL STRUCTURE 327

An identity matrix is denoted by I or by I

, where n indicates the dimension of the

matrix. The ith column of an identity matrix is often denoted by e

or e

Example A.5 (Identity Matrix) The following illustrates an n-dimensional identity

matrix.

I =







100... 00

010... 00

001... 00

000... 10

000... 01







=(e

,... ,e

) .

Multiplication of a matrix by an identity matrix on the left or on the right does not

change the original matrix. This is analogous to the multiplication of a scalar by 1.

Deﬁnition (Permutation Matrix):Apermutation matrix is a matrix with

exactly one 1 in each row and in each column and zeros everywhere else.

Thus, a permutation matrix is a rearrangement of the columns of the identity ma-

trix. A permutation matrix is usually denoted by P .

Example A.6 (Permutation Matrix) An example of a 3 × 3 permutation matrix is

as follows.

P =



010

001

100



Multiplication by a permutation matrix on the left of a matrix A permutes the rows

of A whereas multiplication by a permutation matrix on the right of A permutes

the columns of A.

Example A.7 (Multiplying by a Permutation Matrix) For example, PA, using

the above 3-dimensional matrix P , results in a matrix that consists of the second row of A

followed by the third row of A followed by the ﬁrst row of A. Multiplying by a permutation

matrix on the right of A has the eﬀect of permuting the columns of A in a manner similar

to that described for the rows of A but in the order 3rd column, 1st column, 2nd column.

Deﬁnition (Upper (or Right) Triangular Matrix): A square matrix is upper,

or right, triangular if all its subdiagonal elements are zero, that is, A

=0if

i>j.

An upper triangular matrix is often denoted by R or U.

Example A.8 (Upper Triangular Matrix) An upper triangular matrix is illustrated

below.

R =







... r

0 r

... r

00r

... r

000... r







328 LINEAR ALGEBRA

A matrix is said to be upper trapezoidal if the deﬁnition of upper triangular matrix

is applied to a matrix with more columns than rows.

Deﬁnition (Lower (or Left) Triangular Matrix): A matrix is lower triangular

if all the elements above the diagonal are zero, i.e., A

=0ifi<j.

A lower triangular matrix is commonly denoted by L.

Example A.9 (Lower Triangular Matrix) An example of a lower triangular matrix

L =







00... 0

0 ... 0

... 0

... l







A lower triangular matrix with ones all along the diagonal (that is, l

= 1 for all i)

is called a unit lower triangular matrix. A matrix is said to be lower trapezoidal if

the deﬁnition of lower triangular matrix is applied to a matrix with more rows than

columns.

Deﬁnition (Triangular Matrix): We give the following two equivalent deﬁni-

tions of a triangular matrix.

1. A square matrix is said to be triangular if it satisﬁes the following prop-

erties.

(a) The matrix contains at least one row having exactly one nonzero

element.

(b) If the row with a single nonzero element and its column are deleted,

the resulting matrix will once again have this same property.

2. Equivalently we can deﬁne a square matrix to be triangular, if its rows

and columns can be permuted to be either an upper-triangular or lower-

triangular matrix.

 Exercise A.9 Prove that the transpose of a triangular matrix is also triangular.

Deﬁnition (Orthogonal (or Orthonormal) Matrix): A square matrix is said

to be an orthogonal (orthonormal) matrix if all its columns are orthogonal

(orthonormal).

Usually Q is used to denote an orthonormal matrix. An orthonormal matrix Q

satisﬁes

Q = I, QQ

= I, (A.19)

where I is the identity matrix.

A.9 INVERSE OF A MATRIX 329

Deﬁnition (Elementary Matrix):Anelementary matrix is a matrix of the

form I + αuv

, where the matrix uv

is called a rank one matrix.Arow

elementary matrix is a matrix of the form I + e

and a column elementary

matrix is a matrix of the form I + ue

, where e

is a vector witha1in

position k and zeros elsewhere.

Elementary matrices and rank one matrices play an important role in linear pro-

gramming.

Deﬁnition (Symmetric Matrix): A square matrix is said to be a symmetric

matrix if every element below the diagonal is equal to its mirror image above

the diagonal. That is, A

= A

Thus, a symmetric matrix is one whose transpose is equal to itself, that is, A = A

A.9 INVERSE OF A MATRIX

The inverse of a matrix is analogous to the reciprocal of a scalar.

Deﬁnition (Matrix Inverse): The inverse of a square matrix is another square

matrix that when multiplying the original matrix on the left or the right results

in an identity matrix. The inverse of a matrix A is denoted by A

−1

and satisﬁes

−1

= A

−1

A = I. (A.20)

In early implementations of linear equation solvers, the inverse played a crit-

ical role since the solution of Ax = b can be written as x = A

−1

b. However, it

can be shown that computing the inverse is ineﬃcient and can be highly unstable.

Thus, current implementations of linear equation solvers use matrix factorization

techniques (see Linear Programming 2).

THEOREM A.2 (Existence of the Inverse) The inverse as deﬁned by (A.20)

only exists for a square matrix of full rank and is unique.

Proof. It is easy to prove the uniqueness of the inverse. Let B and C be two

inverses of A. Then AB = I. Multiplying this identity on the left by C and re-

arranging the multiplication, we get (CA)B = C or B = C, thus proving that the

two inverses are the same.

Deﬁnition (Singular Matrix): A square matrix is said to be nonsingular if

its inverse exists; otherwise the matrix is said to be singular.

It is possible to deﬁne one-sided inverses for matrices as follows.

Deﬁnition (Left Inverse, Right Inverse): The matrix B is said to be a left

inverse of a matrix A if B satisﬁes BA = I. The matrix C is said to be a

right inverse of a matrix A if AC = I.

330 LINEAR ALGEBRA

LEMMA A.3 (Left Inverse Equals Right Inverse) For a square matrix

only, if both the left and right inverses exist then they are equal and are equal to the

inverse of A.

Proof. This can be proved by looking at the identity B(AC)=(BA)C, which

follows from the associativity property of matrix multiplication. Since B is a left

inverse and C is a right inverse we get B = C.

The inverse operation aﬀects the order of matrix multiplication in exactly the

same manner as the transpose operation. That is,

(AB)

−1

= B

−1

A.10 INVERSES OF SPECIAL MATRICES

The inverse of an orthonormal matrix Q is given by Q

−1

= Q

. This follows from

the fact that QQ

= Q

Q = I.

 Exercise A.10 Show that the inverse of a permutation matrix is the same as its trans-

pose.

 Exercise A.11 Show that the inverse of a lower (upper) triangular matrix is a lower

(upper) triangular matrix.

 Exercise A.12 The inverse of a nonsingular elementary matrix I + σuv

(where σ is

a scalar) is also an elementary matrix that involves the same two vectors u and v. Show

that if σu

v = −1, then

(I + σuv

)

−1

= I + γuv

, (A.21)

where γ = −σ/(1 + σu

v).

 Exercise A.13 Let A be an n × n matrix whose inverse exists. Use the result of

Exercise A.12 to determine the form of the inverse of



A = A + αuv

in terms of A

−1

, the scalar α, and the vectors u and v. Under what conditions does



−1

exist? The result obtained is a special case of the Sherman-Morrison-Woodbury formula

where u and v are replaced by U and V , which are n × k matrices; derive this formula.

A.11 DETERMINANTS 331

A.11 DETERMINANTS

We start our discussion by deﬁning a formula for computing the determinant of a

square matrix.

Deﬁnition (Determinant): The determinant ofa1× 1 matrix is the value of

its element. The determinant of a general square n × n matrix A, with n>1,

can be computed by expanding the matrix in the cofactors of its ith row, i.e.,

det A =



j=1

, (A.22)

where A

, the ijth cofactor, is the determinant of the minor M

with the

appropriate sign:

=(−1)

i+j

det M

. (A.23)

The minor M

is the matrix formed from A by deleting the ith row and jth

column of A.

Example A.10 (Determinant) The determinant of a two dimensional matrix

A =





can be easily computed as

det A = ad − bc.

 Exercise A.14 Show that det A = det A

. Use this to show that the determinant of A

can be obtained by an expansion of the cofactors along any column j of A.

The determinant possesses several interesting properties. It turns out that every

property is a consequence of the following three properties:

1. The determinant of an identity matrix is 1.

2. The determinant is a linear function of the ith row, i.e.,

(a) Let



A be the matrix obtained by replacing the ﬁrst row A

i•

by αA

i•

Then det



A = α det A.

(b) Let



A be the matrix obtained by replacing the ﬁrst row A

i•

by a vector

i•

+ v

. Then det



A = det A + det B, where B is the matrix formed

from A by replacing A

i•

by v

3. The determinant changes sign if any two rows are interchanged.

 Exercise A.15 Prove the above three properties of a determinant.