July 5th, 2010, 10:06 AM  #1 
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 
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 
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 