Page 439 - Advanced Linear Algebra
P. 439
Positive Solutions to Linear Systems: Convexity and Separation 423
Lemma 15.8 Let ( C ² ³ . Then the set
s Á
9 s ~¸(& & Á & ¹
is a closed, convex cone.
Proof. We leave it as an exercise to prove that is a convex cone and omit the
9
proof that is closed.
9
Theorem 15.9 (Farkas's lemma ) Let ( C ² ³ and let s be
s Á
nonzero. Then exactly one of the following holds:
)
1 There is a strictly positive solution " s to the system (% ~ .
)
2 There is a vector # s for which #( and º#Á » .
Proof. Suppose first that 1) holds. If 2) also holds, then
²#(³" ~ #²("³ ~ º#Á »
However, #( and " imply that ²#(³" . This contradiction implies
that 2) cannot hold.
Assume now that 1) fails to hold. By Lemma 15.8, the set
* ~ ¸(& & s Á & ¹ s
is closed and convex. The fact that 1) fails to hold is equivalent to ¤ * .
Hence, there is a hyperplane that strongly separates and . All we require is
*
*
that and be strictly separated, that is, for some and # s s ,
º#Á %» º#Á » for all % *
Since * , it follows that and so º#Á » . Also, the first inequality is
equivalent to º#Á (&» , that is,
!
º( #Á &»
!
for all & s Á & . We claim that this implies that ( # cannot have any
!
positive coordinates and thus #( . For if the th coordinate ²( #³ is
positive, then taking &~ for we get
! ²( #³
which does not hold for large . Thus, 2) holds.
In the exercises, we ask the reader to show that the previous result cannot be
improved by replacing #( in statement 2) with #( .
Exercises
1. Show that any hyperplane has the form >²5Á 5)) ³ for an appropriate
vector .
5
