Lin. Alg. - Half Planes (convex)

[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 [itex]A \cdot X >= 6[/itex]. 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.

 

[HallsofIvy]

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.

 

[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 [itex]A \cdot X >= c[/itex] 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 [itex]A \cdot P >= c[/itex] and [itex]A \cdot Q >= c[/itex]. 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, [itex]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[/itex]

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

 

[HallsofIvy]

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

 

[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 [itex]A \cdot P \geq c[/itex] and [itex]A \cdot Q \geq c[/itex]. So, we must show that [itex]A \cdot (1-t)P+ tQ \geq c[/itex]

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

=> (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!