# Linear algebra proofs

• Jul 5th 2010, 11:12 AM
nieldv
Linear algebra 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
• Jul 5th 2010, 01:12 PM
HallsofIvy
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?
• Jul 5th 2010, 01:19 PM
nieldv
that would mean every value in the vector is larger than the corresponding value in the other vector. in other words, (2,3) > (1,2)
yTA means (y transposed) * A