July 5th, 2010, 10:06 AM  #1 
Newbie Joined: Jul 2010 Posts: 1 Thanks: 0  Linear algebra proofs
Hi, can someone please help me figure out these proofs? They're from Combinatorial Optimization by Cook, Cunningham, Pulleyblank,Schrijver. Thanks 2.15. Prove that there exists a vector x >= 0 such that Ax <= b, if and only if for each y >= 0 satisfying yTA >= 0 one has yT b >= 0. 2.16. Prove that there exists a vector x > 0 such that Ax = 0, if and only if for each y satisfying yTA >= 0 one has yTA = 0. (Stiemke's theorem (Stiemke [1915]).) 2.17. Prove that there exists a vector x != 0 satisfying x >= 0 and Ax = 0, if and only if there is no vector y satisfying yTA > 0. (Gordan's theorem (Gordan [1873]).) 2.18. Prove that there exists a vector x satisfying Ax < b, if and only if y = 0 is the only solution for y >= 0; yTA = 0; yT b <= 0. 2.19. Prove that there exists a vector x satisfying Ax < b and A'x <= b', if and only if for all vectors y; y' >= 0 one has: (i) if yTA + y'TA' = 0 then yT b + y'T b' >= 0, and (ii) if yTA + y'TA' = 0 and y != 0 then yT b + y'T b' > 0. Thanks guys 
July 8th, 2010, 10:39 PM  #2 
Senior Member Joined: Apr 2008 Posts: 435 Thanks: 0  Re: Linear algebra proofs
Why don't you show us your work and ideas, and we can take it from there. Most of these seem to be definitional. Though I must add, I don't know what you mean by T. What is T?


Tags 
algebra, linear, proofs 
Search tags for this page 
Click on a term to search for related topics.

Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Linear Transformations in Linear algebra  matqkks  Linear Algebra  1  February 7th, 2012 02:39 PM 
Linear algebra Transformation Proofs Help Please  mmmboh  Linear Algebra  1  February 8th, 2010 07:48 AM 
Numerical linear Algebra proofs  saeidmscs  Algebra  1  August 22nd, 2009 05:47 PM 
Linear Algebra.Linear Transformation.Help  ypatia  Linear Algebra  2  March 5th, 2009 02:49 PM 
Linear Algebra.Linear Transformations.Help!!  ypatia  Linear Algebra  1  March 2nd, 2009 07:28 PM 