Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Lin. Alg. - Half Planes (convex)

  1. Feb 13, 2006 #1
    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.
     
  2. jcsd
  3. Feb 14, 2006 #2

    HallsofIvy

    User Avatar
    Science Advisor

    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.
     
  4. Feb 14, 2006 #3
    Thanks. The real problem is now to prove it in Rn :smile:

    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.
     
    Last edited: Feb 14, 2006
  5. Feb 14, 2006 #4

    HallsofIvy

    User Avatar
    Science Advisor

    Yep. Separate the xs from the ys and see what you get.
     
  6. Feb 16, 2006 #5
    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!
     
    Last edited: Feb 16, 2006
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook