Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

NOTE: I tried hard and came up with a lose proof, I have posted it as a answer. Do comment/correct if you can.

Let $$P=\{x|Ax\geq b\}, A\in \mathbb{R}^{m\times n}$$ $$Q=\{y|Gy\geq h\},G\in \mathbb{R}^{k\times n}$$ $$x,y\in\mathbb{R}^n$$

I have to prove that if the rows of A span $\mathbb{R}^n$ and the rows of G don't span $\mathbb{R}^n$ (clearly, they span some space less than n) then $P\neq Q$.

So, what I have tried:

I first tried to analyze what it means for a matrix whose rows don't span Rn. I figured that G must have a column full of zeros if its rows cannot span $\mathbb{R}^n$. Let that column be j. ($\therefore G_j=\mathbb{0}$)

Now, since P and Q are basically defined by linear constrained and P is more strict with respect to its constraints on x, $P\neq Q$ will happen only if I can find a $p$ such that $p\in Q, p \notin P$.

So,

PROPOSITION: $$\exists p\in\mathbb{R}^n$$ $$Gp\geq h$$ $$Ap<b$$ Now, I am stuck.

share|improve this question
    
@littleO, it is true that $m\geq n$ in my case but that's not important. I have been given that A is full row rank and G is not. That is given information. I need to deduce the non-equivalence of P and Q. –  Inquest Nov 9 '12 at 0:16
    
Do you mean to say $A$ spans $\mathbb{R}^m$? And $G$ cannot span $\mathbb{R}^k$? –  littleO Nov 9 '12 at 0:18
    
@littleO No. I mean that the rows of A span Rn and rows of G don't. –  Inquest Nov 9 '12 at 0:22
    
@littleO, good point. I wasnt thinking hard enough. I edited the question. –  Inquest Nov 9 '12 at 0:31

1 Answer 1

First, $G$ does not to have a column of zeros, or indeed any zeros, just in order to have less than full row rank, e.g., $$G=\pmatrix{1&2\cr3&6}$$

If $G$ doesn't have full row rank, then there's a nonzero vector $v$ such that $Gv=0$. Since $A$ has full row rank, $Av\ne0$. So if $y$ is in $Q$ then so is $y+tv$ for all real numbers $t$, but it's impossible to have $A(y+tv)=Ay+tAv\ge b$ for all real $t$. So there are values of $t$ for which $y+tv$ is in $Q$ but not in $P$.

share|improve this answer
    
Gerry, I misspoke, apologies. I wanted to say that the rows of G do not span $\mathbb{R}^n$, they span some lesser space. My comment about full row ranks is void. –  Inquest Nov 9 '12 at 0:32

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.