# Lin. Alg. - Half Planes (convex)

1. Feb 13, 2006

### mattmns

Hello, I am a little confused on how to prove these half planes are convex, and my book does not actually show an example.
----------
So here is a problem, my book briefly talks about it: Show that the plane 2x - 3y >= 6 is convex. So if we let A = (2,-3), and X = (x,y), then we can write the inequality $A \cdot X >= 6$. Prove that this half plane is convex.
---------
So I want to let there be a point P in this half plane, and a point Q on this plane, and then show that (1-t)P + tQ is of the same form and therefore the half plane is convex. The problem I am having is what do I let P and Q be equal to, in order to show this? Thanks.

2. Feb 14, 2006

### HallsofIvy

Staff Emeritus
P and Q must be points in the half-plane, of course. That is P= (x,y) where 2x- 3y>= 6, Q= (u, v) where 2u- 3v>= 6. As you say, the line segment between them is (1-t)P+ tQ= ((1-t)x+ tu, (1-t)y+ tv). Now can you show that, as long as 0<= t<= 1, that point is also in the half plane? That is, that 2[(1-t)x+ tu]- 3[(1-t)y+ tv]>= 6.

3. Feb 14, 2006

### mattmns

Thanks. The real problem is now to prove it in Rn

To make more clear, here is the actual problem from the book: Let A be a non-zero vector in Rn and let c be a fixed number. Show that the set of all elements X in Rn such that $A \cdot X >= c$ is convex.

So I would just let A = (a1, a2, ..., an), P = (x1, x2,..., xn) and Q = (y1, y2,..., yn) where P and Q are points in X, so $A \cdot P >= c$ and $A \cdot Q >= c$. And then (1-t)P+ tQ = ( (1-t)x1 + ty1, (1-t)x2 + ty2, ... , (1-t)xn + tyn) and show that this point is in X for 0 <= t <= 1. Meaning, $a_{1}[(1-t)x_{1} + ty_{1}] + a_{2}[(1-t)x_{2} + ty_{2}], + ... + a_{n}[(1-t)x_{n} + ty_{n}] >= c$

I have not worked this out yet, but I think it should work.

Last edited: Feb 14, 2006
4. Feb 14, 2006

### HallsofIvy

Staff Emeritus
Yep. Separate the xs from the ys and see what you get.

5. Feb 16, 2006

### mattmns

Ok, I just worked on the problem, and I think I have found a somewhat shorter way to do it. Well maybe it is not shorter, but instead I don't write everything out. I use the idea that the dot product is distributive and scalar multiplication is allowed (1-t), t.

-----
let A = (a1, a2, ..., an), P = (x1, x2,..., xn) and Q = (y1, y2,..., yn) where P and Q are points in X, so $A \cdot P \geq c$ and $A \cdot Q \geq c$. So, we must show that $A \cdot (1-t)P+ tQ \geq c$

but $A \cdot [(1-t)P+ tQ] \ = \ A \cdot P(1-t) + A \cdot Qt$
and $A \cdot P(1-t) + A \cdot Qt \geq c$ is clearly true because $A \cdot P \geq c$, and $A \cdot Q \geq c$
and so if we factor we have ((1-t) + t)(something greater than c) = 1(something greater than c).
So, $A \cdot [(1-t)P+ tQ] \geq c$

=> (1-t)P + tQ is in X, and therefore X is convex.
------

Does that look sufficient?

Also, the end looks a bit nasty, the whole "(something greater than c)" part, is there a prettier way to write this? Thanks!

Last edited: Feb 16, 2006