Davidson K.R., Donsig A.P. Real Analysis with Real Applications

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

1.4 Linear Algebra 13

1.4.4. PROPOSITION. A nonempty subset W of a vector space V is a subspace

if and only it is closed under addition and scalar multiplication.

1.4.5. EXAMPLES.

(1) A line is a the set of multiples of a single nonzero vector v, namely Rv. It is

easy to check that a line is a subspace. An afﬁne line is the translate of a line (i.e.

A = u + Rv). This is not a subspace unless u is a multiple of v, in which case

A = Rv, for otherwise A does not contain the origin 0.

(2) The set P

of all polynomials of degree no greater than n is a subspace of the

vector space P of all polynomials.

(3) The set S of all functions f(x) on [0, 1] satisfying the differential equation

(x) + e

(x) − xf(x) = 0 is a subspace of C[0, 1]. If f and g are solutions,

then

(f + g)

(x) + e

(f + g)

(x) − x(f + g)(x)

= (f

(x) + e

(x) − xf(x)) + (g

(x) + e

(x) − xg(x)) = 0

and

(rf)

(x) + e

(rf)

(x) − x(rf)(x) = r(f

(x) + e

(x) − xf(x)) = 0.

So f + g and rf are solutions, showing that S is closed under addition and scalar

multiplication.

(4) The subset R

consisting of all vectors (x, y) in R

such that x ≥ 0 and y ≥ 0

is not a subspace. It is closed under addition, but not scalar multiplication. Indeed,

(1, 0) ∈ R

but (−1)(1, 0) = (−1, 0) does not belong.

(5) {0} is the smallest subspace of V .

1.4.6. DEFINITION. If S is a subset of a vector space V , the span of S is the

smallest subspace containing S. It is denoted by spanS. A vector w is a linear

combination of S if there are vectors v

, . . . , v

∈ S and scalars r

, . . . , r

such

that w = r

+ ··· + r

Phrases like the smallest are dangerous, because they assume that there is a

unique smallest subspace. We must prove that this object exists; fortunately, it is

easy to do so. First, verify that the collection of all linear combinations of S is

a subspace. Second, verify that any subspace containing S will contain all linear

combinations of S, and hence will contain this unique minimal subspace. This

process of showing that the deﬁnition of an object makes sense is known as showing

that the object is well deﬁned. It comes up often.

Besides showing that our deﬁnition of span makes sense, this also proves the

following result.

1.4.7. PROPOSITION. The subspace spanned by a nonempty set S ⊂ V con-

sists of all linear combinations of S.

14 Background

We now consider one of the central notions of linear algebra.

1.4.8. DEFINITION. A subset S of a vector space V is linearly dependent if

there are vectors v

, . . . , v

∈ S and scalars r

, . . . , r

, which are not all 0, such

that r

+ ··· + r

= 0.

A subset S of a vector space V is linearly independent if whenever vectors

, . . . , v

∈ S and scalars r

, . . . , r

∈ R satisfy r

+ ··· + r

= 0, this

implies that r

= ··· = r

= 0.

A basis for a vector space V is a linearly independent set that spans V . We say

that V is ﬁnite dimensional if it has a ﬁnite basis.

A set S is linearly dependent if there is a nontrivial linear relationship between

certain vectors in S. If r

+ ··· + r

= 0 and r

6= 0, you can solve for v

+ ··· +

j−1

j+1

+ . . .

Thus v

belongs to span{S \ {v

}}. Therefore, it can be deleted from S without

changing the span.

On the other hand, there is no such relation among vectors in a linearly inde-

pendent set. Consequently, different linear combinations yield different vectors.

That is, if S = {v

, . . . , v

} is linearly independent and

+ ··· + r

= s

+ ··· + s

then

− s

+ ··· + (r

− s

= 0.

Linear independence forces r

= s

for 1 ≤ i ≤ k. So each vector v in span S can

be written in exactly one way (uniquely) as a linear combination of vectors in S.

So if S is linearly independent and spanS = V and thus S is a basis for V , then

every vector in V has a unique expression in terms of this basis. Thus the choice

of a basis provides a coordinate system for V . The expression of each vector as

a linear combination of the basis can be interpreted as coordinates with respect to

this basis.

1.4.9. EXAMPLES.

(1) Consider the space R

. The vectors e

= (1, 0, 0, . . . , 0), e

= (0, 1, 0, . . . , 0),

..., e

= (0, 0, . . . , 0, 1) are called the standard basis for R

. The vector

v = (v

, . . . , v

) =

i=1

is in span{e

, . . . , e

}. Conversely, suppose that

0 =

i=1

= (r

, . . . , r

). Then r

= ··· = r

= 0. So this set is linearly

independent. Thus it is a basis.

(2) The vectors (1, 2), (2, 3) and (3, 4) are linearly dependent because

(1, 2) − 2(2, 3) + (3, 4) = (0, 0)

is a nontrivial relation.

1.4 Linear Algebra 15

(3) The set {1, x, x

, . . . , x

} is a basis for P

. The inﬁnite set {1, x

: j ≥ 1} is a

basis for P. Note that in algebra (as opposed to analysis), linear combination means

a ﬁnite linear combination. Algebraists do not have to worry about convergence.

1.4.10. THEOREM. Let V be a ﬁnite-dimensional vector space. Then every

basis for V has the same ﬁnite number of elements. This number is the dimension

of V , written dimV .

It follows that R

is n-dimensional and P

is (n+1)-dimensional. Neither the

polynomials P nor the space of continuous functions C[0, 1] is ﬁnite dimensional.

Indeed, many inﬁnite-dimensional vector spaces arise in analysis.

Linear Transformations. In this book, we will be concerned with functions

on vector spaces. Linear algebra is focused on the special case of linear functions.

1.4.11. DEFINITION. A linear transformation A from a vector space V to a

vector space W is a function with domain V and codomain W satisfying

A(r

+ r

) = r

+ r

for all v

, v

∈ V and r

, r

∈ R.

We use L(V, W ) to denote the set of all linear transformations from V to W . When

W = V , we write L(V ) rather than L(V, V ).

A linear transformation is determined by what it does to a basis. Suppose that

, . . . , e

is a basis for V and f

, . . . , f

is a basis for W . If Ae

= w

for

1 ≤ j ≤ m, then we can compute

j=1

Moreover if each w

is expressed in the basis f

, . . . , f

, say Ae

= w

i=1

then we may compute

j=1

i=1

j=1

The n × m matrix

is called the matrix representation of A, with respect to

the bases e

, . . . , e

and f

, . . . , f

. Notice the meaning of a coefﬁcient a

in this

representation. It tells us how much of Ae

is in the direction of f

. By writing

vectors in terms of the two bases and representing the linear transformation by its

matrix, we can turn the application of the transformation into multiplication by its

matrix, using the preceding formula.

1.4.12. EXAMPLE. Consider the function taking P

into P

by differentiation,

Dp = p

. Since (r

+ r

)

= r

+ r

, it is evident that this is a linear

map. Let us use the standard basis 1, x, x

, x

for P

and use 1, x, x

, x

for P

16 Background

Observe that Dx

= kx

k−1

for 0 ≤ k ≤ 4. If p = a

+ a

x + a

+ a

then Dp = a

+ 2a

x + 3a

+ 4a

is given by the matrix computation







0 1 0 0 0

0 0 2 0 0

0 0 0 3 0

0 0 0 0 4































The space L(V, W ) is a vector space with the two operations A + B and rA

for A and B in L(V, W ) and scalars r, deﬁned by

(A + B)v = Av + Bv and (rA)v = r(Av) for v ∈ V.

However, there is another important operation that is deﬁned because linear maps

are functions, namely composition. If A is a linear map from V to W and B is

a linear map of W into a third vector space X, then BA is deﬁned as the map

(BA)v = B(Av). Convince yourself that this is indeed just composition. To see

that BA is linear, we compute

(BA)(r

+ r

) = B(A(r

+ r

)) = B(r

+ r

)

= r

B(Av

) + r

B(Av

) = r

(BA)v

+ r

(BA)v

The more interesting computation to do is the matrix representation of BA.

Suppose that bases have been chosen for V , W and X, say e

, . . . , e

for V ,

, . . . , f

for W and g

, . . . , g

for X. Then there will be matrices representing A

and B. As before, we see that A =

is an n × m matrix. Similarly, B =

is an p × n matrix. Compute

BAe

= B

i=1

k=1

i=1

So BA has a matrix representation for the bases e

, . . . , e

and g

, . . . , g

where c

i=1

. This formula is known as matrix multiplication.

1.4.13. DEFINITION. The kernel of a linear transformation A ∈ L(V, W ) is

the set kerA = {v ∈ V : Av = 0}. The nullity of A is dimkerA, the dimension

of the kernel. The rank of A is rankA = dimRanA, the dimension of the range.

Implicit in this deﬁnition is the observation that the kernel and range of A are

subspaces, so that dimension is deﬁned. This is easy to verify. The kernel of A

measures how far A is from being one-to-one. Indeed, Au = Av if and only if

A(u −v) = 0 (i.e., u −v ∈ kerA). So A is one-to-one if and only if kerA = {0}.

1.4 Linear Algebra 17

The range of A is the subspace A(V ). The main result relating the two dimensions

is the following.

1.4.14. THEOREM. Let V be a ﬁnite-dimensional vector space, and let A be a

linear transformation of V into W . Then

dimkerA + rankA = dimV.

An important corollary of this applies to maps from V into itself.

1.4.15. COROLLARY. Let A ∈ L(V ), where V is a ﬁnite-dimensional vector

space. Then the following are equivalent:

(1) A is invertible.

(2) A is one-to-one (i.e., ker A = {0}).

(3) A is onto (i.e., RanA = V ).

PROOF. The map A is invertible if and only it is one-to-one and onto. So (1)

implies (2) and (3). However, (2) means that dimkerA = 0 and (3) means that

dimRanA = dim V . Theorem 1.4.14 says that dim kerA = dimV − dimRanA,

so (2) and (3) are equivalent. Together they say that A is one-to-one and onto, and

thus is invertible. ¥

While it is not stated in the theorem, it is important to observe that the inverse

of an invertible linear transformation is also linear. Let A

−1

be the inverse map.

Consider v

, v

∈ V and r

, r

∈ R. Suppose that A

−1

= u

and A

−1

= u

Then

A(r

+ r

) = r

+ r

= r

+ r

Therefore, linearity follows from

−1

+ r

) = r

+ r

= r

−1

+ r

−1

Use I for the identity map on the vector space (i.e., I sends each vector to

itself). Thus in any basis, I is represented as the diagonal matrix with 1s down the

diagonal. The composition of A and A

−1

is the identity map. This is expressed

algebraically as A

−1

A = I = AA

−1

Systems of Linear Equations. The most basic application of the ideas of lin-

ear algebra is in the solution of a system of linear equations such as

+ a

+ . . . + a

= b

+ a

+ . . . + a

= b

+ a

+ . . . + a

= b

We deﬁne an n × m matrix A =

, a vector b = (b

, . . . , b

) in R

, and an

unknown vector x = (x

, . . . , x

) in R

. Then this system can be succinctly

written as Ax = b.

18 Background

You should be familiar with the Gaussian elimination algorithm for solving a

system of this kind. A solution exists precisely when b belongs to RanA. If x is a

solution, then every vector in x + kerA is also a solution, and all solutions are in

this set. This gives necessary and sufﬁcient conditions for solving the problem. In

particular, if m = n, Corollary 1.4.15 can be used to show that a solution exists for

every vector b if and only if A is invertible if and only if the solution is unique.

Exercises for Section 1.4

A. Show that the space S of all inﬁnite sequences of real numbers, x = (x

, x

, . . . ),

satisﬁes the axioms of a vector space.

B. (a) Verify that L(V, W ) satisﬁes the axioms of a vector space.

(b) If V and W are ﬁnite-dimensional vector spaces, show that dim L(V, W ) is equal

to (dimV )(dim W ).

C. (a) Let V and W be vector spaces. Deﬁne V ⊕ W to be the set of vectors (v, w)

with v ∈ V and w ∈ W . Deﬁne (v

, w

) + (v

, w

) = (v

+ v

, w

+ w

) and

r(v

, w

) = (rv

, rw

) for v

∈ V , w

∈ W and r ∈ R. Show that V ⊕ W is a

vector space.

(b) Show that dim(V ⊕ W ) = dim V + dimW .

D. Show that the set of all vectors x = (w, x, y, z) such that 2w − x + 3y + 5z = 0 is a

subspace of R

. Express this subspace as the kernel of a linear map.

E. Which of the following subsets of C[0, 1] are subspaces?

(a) W = {f : f(0) = f(1)}

(b) X = {f : f(0) + f(1) = 2}

(d) Z = {f : |f(0)| ≤ |f(1)|}

F. Let W

and W

be subspaces of a vector space V .

(a) Show that W

+ W

= {w

+ w

: w

∈ W

, w

∈ W

} is a subspace of V .

(b) Show that W

∩ W

is a subspace.

⊕W

, V ) by A(w

, w

) = w

+ w

. Show RanA = W

+ W

(d) Compute kerA.

(e) Prove that dim(W

+ W

) + dim(W

∩ W

) = dimW

+ dimW

G. Given a subset S of a vector space V , consider the collection of all subspaces of V

containing S. Show that there is a smallest subspace of V containing S, using the

intersection of this collection.

H. Show that if span{v

, . . . , v

} = V , then a basis for V may be obtained by deleting

every v

that belongs to span{v

: i < j}.

I. Let W be a subspace of a ﬁnite-dimensional vector space V .

(a) Show that a basis for W may be extended to a basis for V .

HINT: Start with a basis for W , add a basis for V , and use the previous exercise.

(b) Hence deduce that dim W ≤ dim V , with equality only when W = V .

J. Let A ∈ L(V, W ), where V has a basis v

, . . . , v

. Show that A is one-to-one if and

only if Av

, . . . , Av

are linearly independent.

1.5 The Role of Proofs 19

K. Let A =

be an upper triangular n × n matrix, meaning that a

= 0 if i > j.

Prove that A is invertible if and only if a

6= 0 for 1 ≤ i ≤ n.

L. Consider an n × n system of equations Ax = b. Show that a solution exists for every

vector b if and only if Ax = 0 has a unique solution.

1.5. The Role of Proofs

Mathematics is all about proofs. Mathematicians are not as much interested

in what is true as in why it is true. For example, you were taught in high school

that the roots of the quadratic equation ax

+ bx + c = 0 are

−b ±

√

− 4ac

provided that a 6= 0. A serious class would not have been given this as a fact to be

memorized. It would have been justiﬁed by the technique of completing the square.

This raises the formula from the realm of magic to the realm of understanding.

There are several important reasons for teaching this argument. The ﬁrst goes

beyondintellectual honesty and addresses the real point, which is that you shouldn’t

accept mathematics (or science) on faith. The essence of scientiﬁc thought is un-

derstanding why things work out the way they do.

Second, the formula itself does not help you do anything beyond what it is

designed to accomplish. It is no better than a quadratic solver button that could be

built into your calculator. The numbers a, b, c go into a black box and two numbers

come out or they don’t—you might get an error message if b

− 4ac < 0. At this

stage, you have no way of knowing if the calculator gave you a reasonable answer,

or why it might give an error. If you know where the formula comes from, you can

analyze all of these issues clearly.

Third, knowledge of the proof makes further progress a possibility. The cre-

ation of a new proof about something that you don’t yet know is much more difﬁcult

than understanding the arguments someone else has written down. Moreover, un-

derstanding these arguments makes it easier to push further. It is for this reason

that we can make progress. As Isaac Newton once said, “If I have seen further than

others, it is by standing on the shoulders of giants.” The ﬁrst step toward proving

things for yourself is to understand how others have done it before.

Fourth, if you understand that the idea behind the quadratic formula is com-

pleting the square, then you can always recover the quadratic formula whenever

you forget it. This nugget of the proof is a useful method of data compression that

saves you the trouble of memorizing a bunch of arcane formulae.

It is our hope that most students reading this book already have had some intro-

duction to proofs in their earlier courses. If this is not the case, the examples in this

section will help. This may be sufﬁcient to tackle the basic material in this book.

But be warned that some parts of this book require signiﬁcant sophistication on the

part of the reader.

20 Background

Direct Proofs. We illustrate several proof techniques that occur frequently.

The ﬁrst is directproof. In this technique, one takes a statement, usually one assert-

ing the existence of some mathematical object, and proceeds to verify it. Such an

argument may amount to a computation of the answer. On the other hand, it might

just show the existence of the object without actually computing it. The crucial dis-

tinction for existence proofs is between those that are constructive proofs—that

is, those that give you a method or algorithm for ﬁnding the object—and those that

are nonconstructive proofs—that is, they don’t tell you how to ﬁnd it. Needless

to say, constructive proofs do something more than nonconstructive ones, but they

sometimes take more work.

Every real number x has a decimal expansion x = a

. . . , where a

are integers and 0 ≤ a

≤ 9 for all i ≥ 1. This will be discussed thoroughly in

Chapter 2. This expansion is eventually periodic if there are integers N and d > 0

so that a

n+d

= a

for n ≥ N .

Occasionally a direct proof is just a straightforward calculation or veriﬁcation.

1.5.1. THEOREM. If the decimal expansion of a real number x is eventually

periodic, then x is rational.

PROOF. Suppose that N and d > 0 are given so that a

n+d

= a

for n ≥ N.

Compute 10

x and 10

N+d

x and observe that

N+d

x = b.a

N+1+d

N+2+d

N+3+d

N+4+d

. . .

= b.a

N+1

N+2

N+3

N+4

. . .

x = c.a

N+1

N+2

N+3

N+4

. . . ,

where b and c are integers that you can easily compute. Subtracting the second

equation from the ﬁrst yields

(10

N+d

− 10

)x = b − c.

Therefore, x =

b − c

N+d

− 10

is a rational number. ¥

The converse of this statement is also true. We will prove it by an existential

argument that does not actually exhibit the exact answer, although the argument

does provide a method for ﬁnding the exact answer. The next proof is deﬁnitely

more sophisticated than a computational proof. It still, like the last proof, has the

advantage of being constructive.

We need a simple but very useful fact.

1.5.2. PIGEONHOLE PRINCIPLE.

If n + 1 items are divided into n categories, then at least two of the items are in the

same category.

This is evident after a little thought, and we do not attempt to provide a formal

proof. Note that it has variants that may also be useful. If nd+1 objects are divided

1.5 The Role of Proofs 21

into n categories, then at least one category contains d + 1 items. Also, if inﬁnitely

many items are divided into ﬁnitely many categories, then at least one category has

inﬁnitely many items.

1.5.3. THEOREM. If x is rational, then the decimal expansion of x is eventually

periodic.

PROOF. Since x is rational, we may write it as x =

, where p, q are integers and

q > 0. When an integer is divided by q, we obtain another integer with a remainder

in the set {0, 1, . . . , q − 1}. Consider the remainders r

when 10

is divided by q

for 0 ≤ k ≤ q. There are q + 1 numbers r

, but only q possible remainders. By the

Pigeonhole Principle, there are two integers 0 ≤ k < k + d ≤ q so that r

= r

k+d

Therefore, q divides 10

k+d

− 10

exactly, say qm = 10

k+d

− 10

Now compute

k+d

− 10

= 10

−k

− 1

Divide 10

−1 into pm to obtain quotient a with remainder b, 0 ≤ b < 10

−1. So

x =

= 10

−k

a +

− 1

where 0 ≤ b < 10

− 1. Write b = b

. . . b

as a decimal number with exactly

d digits even if the ﬁrst few are zero. For example, if d = 4 and b = 13, we will

write b = 0013. Then consider the periodic (or repeating) decimal

r = 0.b

. . . b

. . . .

Using the proof of Theorem 1.5.1, we ﬁnd that (10

−1)r = b and thus r =

−1

Observe that 10

x = a + r = a.b

. . . b

. . . has a repeating decimal expansion.

The decimal expansion of x = 10

−k

(a + r) begins repeating every d terms after

the ﬁrst k. Therefore, this expansion is eventually periodic. ¥

Proof by Contradiction. The second common proof technique is generally

called proof by contradiction. Suppose that we wish to verify statement A. Now

either A is true or it is false. We assume that A is false and make a number of

logical deductions until we establish as true something that is clearly false. No

false statement can be deduced from a logical sequence of deductions based on a

valid hypothesis. So our hypothesis that A is false must be incorrect, whence A is

true.

Here is a well-known example of this type.

1.5.4. THEOREM.

√

3 is an irrational number.

PROOF. Suppose to the contrary that

√

3 = a/b, where a, b are positive integers

with no common factor. (This proviso of no common factor is crucial to setting

22 Background

the stage correctly. Watch for where it gets used.) Manipulating the equation, we

obtain

= 3b

When the number a is divided by 3, it leaves a remainder r ∈ {0, 1, 2}. Let us

write a = 3k + r. Then

= (3k + r)

= 3(3k

+ 2kr) + r











if r = 0

3(3k

+ 2k) + 1 if r = 1

3(3k

+ 4k + 1) + 1 if r = 2

Observe that a

is a multiple of 3 only when a is a multiple of 3. Therefore, we can

write a = 3c for some integer c. So 9c

= 3b

. Dividing by 3 yields b

= 3c

Repeating exactly the same reasoning, we deduce that b = 3d for some integer

d. It follows that a and b do have a common factor 3, contrary to our assumption.

The reason for this contradiction was the incorrect assumption that

√

3 was rational.

Therefore,

√

3 is irrational. ¥

The astute reader might question why a fraction may be expressed in lowest

terms. This is an easy fact that does not depend on deeper facts such as unique

factorization into primes. It is merely the observation that if a and b have a com-

mon factor, then after it is factored out, one obtains a new fraction a

with a

smaller denominator. This procedure must terminate by the time the denomina-

tor is reduced to 1, if not sooner. A very crude estimate of how many times the

denominator can be factored is b itself.

The same reasoning is commonly applied to verify “A implies B.” It is enough

to show that “A and not B” is always false. For then if A is true, it follows that not

B is false, whence B is true. This is usually phrased as follows: A is given as true.

Assume that B is false. If we can make a sequence of logical deductions leading to

a statement that is evidently false, then given that A is true, our assumption that B

was false is itself incorrect. Thus B is true.

Proof by Induction. The Principle of Induction is the mathematical version

of the domino effect.

1.5.5 PRINCIPLE OF INDUCTION. Let P (n), n ≥ 1, be a sequence of state-

ments. Suppose that we can verify the following two statements:

(1) P (1) is true.

(2) If n > 1 and P (k) is true for 1 ≤ k < n, then P (n) is true.

Then P (n) is true for each n ≥ 1.

We note that there is nothing special about starting at n = 1. For example, we

can also start at n = 0 if the statements are numbered beginning at 0. You may

have seen step (2) replaced by

) If n > 1 and P (n − 1) is true, then P (n) is true.