《linear algebra and its applications the duality theorem》由会员分享，可在线阅读，更多相关《linear algebra and its applications the duality theorem（12页珍藏版）》请在金锄头文库上搜索。
1、CHAPTER 13The Duality TheoremLet X be a linear space over the reals, dim X = n. Its dual X consists of all linear functions on X. If X is represented by column vectors x of n components x1,. , xn, then elements of X are traditionally represented as row vectorswith n components t , . , in. The value
2、ofat x isIx1 + . +Snxn.(1)If we regardas a 1 x n matrix and regard x as an n x 1 matrix, (1) is their matrix product lx. Let Y be a subspace of X; in Chapter 2 we have defined the annihilator Y1 of Yas the set of all linear functions t; that vanish on Y, that is, satisfyty = 0for all y in Y.(2)Accor
3、ding to Theorem 3 of Chapter 2, the dual of X is X itself, and according to Theorem 5 there, the annihilator of Y1 is Y itself. In words: if tx = O for allin Y1, then x belongs to Y. Suppose Yis defined as the linear space spanned by m given vectors yi,. ,yn in X. That is, Y consists of all vectors
4、y of the form(3)Clearly, l; belongs to Y1 iffYj = 0,j = 1,., M.(4)Linear Algebra and Its Applications, Second Edition, by Peter D. Lax Copyright Q 2007 John Wiley we claim it is closed. To see this we first note that any vector y which may be represented in form (5) may be represented so in various
5、ways. Among all these representations there is by local compactness one, or several, for which E pj is as small as possible. We call such a representation of y a minimal representation.Now let z, be a sequence of points of K converging to the limit z in the Euclidean norm. Represent each z minimally
6、:Z. = E pn.jyj.(5)We claim that E p, j = P is a bounded sequence. For suppose on the contrary that P - oo. Since the sequence z is convergent, it is bounded; thereforetends to zero:Zn_Pn.iyJ0. PnP.The numbers pn, j/P are nonnegative and their sum is 1. Therefore by compactness we can select a subseq
7、uence for which they converge to limits:Pn.j 9j- P11204LINEAR ALGEBRA AND ITS APPLICATIONSThese limits satisfy qj = 1. It follows from (5)“ thatE gjyi = 0.Subtract this from (5):For each j for which qj 0, pn.joo; therefore for n large enough, this is a positive representation of z, showing that (5)
8、is not a minimal representation. This contradiction shows that the sequence Pn = E p, j is bounded. But then by local compactness we can select a subsequence for which p, ,j - pj for all j. Let n tend to oc in (5); we obtainz = limz = P,)jThus the limit z can be represented in the form (5); this pro
9、ves that the set K of all points of form (5) is closed in the Euclidean norm. We note that the origin belongs to K. Let y be a vector that does not belong to K. Since K is closed and convex, according to the hyperplane separation Theorem 7 of Chapter 12 there is a closed halfspace(7)that contains K
10、but not y:ny c. Combining this with (8), we getny c,j = l. , infor all k 0; this is the case only ifl1)y0,j=1,.,m.(9)(10)Thus if y is not of form (5), there is an q that according to (10) satisfies (6) but according to (9) violates (6). This completes the proof of Theorem 1.0THE DUALITY THEOREM205EX
11、ERCISE I.Show that K defined by (5) is a convex set.We reformulate Theorem 1 in matrix language by defining the n x m matrix Y asy = (yI) .,ym),that is, the matrix whose columns are y,. We denote the column vector formed byPh,.,Pm by P:We shall call a vector, column or row, nonnegative, denoted as 0
12、, if all its components are nonnegative. The inequality x z means x - z _ 0.EXERCISE 2.Show that if x z and 0, then i x z.Theorem 1.Given an n x m matrix Y, a vector y with n components can be written in the formy=YP,P-0(11)tthttifiifevery row veca sasesorY 0(12)also satisfiesy_0.(12)For the proof,
13、we merely observe that (11) is the same as (5), (12) the same as (6), and (12) the same as (6).The following is a useful extension.Theorem 2.Given an n x m matrix Y and a column vector components, the inequalityywith nyYP,P0(13)can be satisfied if everythat satisfies4Y0,40(14)206LINEAR ALGEBRA AND I
14、TS APPLICATIONSalso satisfiesby_ 0.(15)Proof. To prove necessity, multiply (13) byon the left and use (14) to deduce (15). Conversely by definition of 0 for vectors, (13) means that there is a column vector z with n components such that y=Yp+z,z_0,p0.(13)We can rewrite (13) by introducing the n x n
15、identity matrix I, the augmentedmatrix (Y, 1) and the augmented vector (p ). In terms of these (13) can be written aszy=(Y,I)(P),(P) 0(13)“and (14) can be written as(Y,I) 0.(14)We now apply Theorem 1 to the augmented matrix and vector to deduce that if (15) is satisfied whenever (14) is, then (13)“
16、has a solution, as asserted in Theorem 2.OTheorem 3 (Duality Theorem).Let Y be a given n x m matrix, y a given column vector with n components, and y a given row vector with m components.We define two quantities, S and s, as follows:DefinitionS = sup yp Pfor all column vectors p with m components satisfying(16)yYP,P_0.We call the set of p satisfying (17) admissible for the sup problem (16).Definition(17)s = i
