What do you mean by vector being larger than another? Vector spaces do not, in general, have an order defined on them. Also, what does "yTA" mean?
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