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

  • 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

0

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$.

  • 0
    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.2012-11-09