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!

Prove One but not both of these systems is consistent.

  1. May 4, 2017 #1
    Given the two systems below for an ##m \times n## matrix ##A##:

    • (Sy 1): ##Ax = 0, x \geq 0, x \neq 0##
    • (Sy 2): ##A^Ty > 0 ##

    I seek to prove: (Sy 1) is consistent ##\Leftrightarrow## (Sy 2) is inconsistent.

    I figured out how to prove Q ##\Rightarrow ## P by proving the contrapositive (##\neg##P ##\Rightarrow## ##\neg## Q).


    Sketch Proof for ##\neg##P ##\Rightarrow## ##\neg## Q: Let (Sy 1) be inconsistent, then ##0 \notin K = \{Ax: x \geq 0, x \neq 0\}##.
    >Separation Theorem 1 states: Let ##X## be a closed convex set in ##\mathbb{R}^n##. If ##p \notin X##, then for some ##p \neq 0## we have: ##\langle v, p \rangle < \inf_{x \in X}\langle v, x \rangle##.


    Since ##K## is a closed convex set, then by Separation Theorem 1, ##\exists y## such that
    \begin{eqnarray}
    \langle y, 0 \rangle = 0 & < & \inf_{x \geq 0, x \neq 0}\langle y, Ax \rangle
    \end{eqnarray}

    Since ##x \geq 0, x\neq 0##, then ##\inf \langle y, Ax, \rangle = y^TAx = (A^Ty)^Tx > 0##. We must now verify that ##A^Ty > 0 ##.

    If not true, then for some index ##i##, ##(A^Ty)_i \leq 0##. Pick ##x \in \mathbb{R}^n## to be the vector with coordinate ##x_j = \lambda \delta_{ij}##. Then:
    \begin{eqnarray}
    \langle y, Ax\rangle = \sum_{j = 1}^{n}(A^Ty)_jx_j = \lambda(A^Ty)_{i}
    \end{eqnarray}
    As ##\lambda \rightarrow \infty##, then ##\lambda(A^Ty)_{i} \rightarrow -\infty## if ##(A^Ty)_i < 0## or ##\lambda(A^Ty)_{i} = 0## if ##(A^Ty)_i = 0##.

    Thus ##\langle y, Ax \rangle \leq 0 = \langle y, 0\rangle##. This is a contradiction, thus ##A^Ty > 0##. Q.E.D.


    Now I seek to prove P ##\Rightarrow ## Q. However, I am stuck. I tried to mimic something similar to my proof for ##\neg##P ##\Rightarrow## ##\neg##Q.

    I let (Sy 1) be consistent, which meant ##0 \notin S(A) = \{x: x\in \text{Ker}(A), x\geq 0, x \neq 0\}##. However, I did not seem to get very far. Any suggestions on how I should go about it?

    Thank You for taking the time to read this. I appreciate any suggestions or feedback you give me. Take care and have a wonderful day.
     
  2. jcsd
  3. May 4, 2017 #2

    jedishrfu

    Staff: Mentor

    Where is the template? This is an important part of our site. We use it to gauge what you've learned so far.

    So what is your level of background and what course has this come up in?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Prove One but not both of these systems is consistent.
Loading...