1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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
    Staff Emeritus
    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
    Staff Emeritus
    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
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Lin. Alg. - Half Planes (convex)
  1. In^-1=In Lin alg (Replies: 4)

  2. Lin. Alg. Invertility (Replies: 1)

Loading...