- #1
Kevin_H
- 5
- 0
Given the two systems below for an ##m \times n## matrix ##A##:
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.
- (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.