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, 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