Prove One but not both of these systems is consistent.

[Kevin_H]

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.

 

[jedishrfu]

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?