1
$\begingroup$

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 Now, I am stuck.

  • 0
    @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.2012-11-09
  • 0
    Do you mean to say $A$ spans $\mathbb{R}^m$? And $G$ cannot span $\mathbb{R}^k$?2012-11-09
  • 0
    @littleO No. I mean that the rows of A span Rn and rows of G don't.2012-11-09
  • 0
    @littleO, good point. I wasnt thinking hard enough. I edited the question.2012-11-09

1 Answers 1