Prove One but not both of these systems is consistent.

In summary, the conversation discusses two systems for an ##m \times n## matrix ##A##: ##Ax = 0, x \geq 0, x \neq 0## and ##A^Ty > 0##. The goal is to prove that if (Sy 1) is consistent then (Sy 2) is inconsistent. The speaker mentions using the contrapositive to prove this and uses Separation Theorem 1 to show that if (Sy 1) is inconsistent, then (Sy 2) is inconsistent. They also mention being stuck on proving the other direction and ask for suggestions. They also mention the lack of a template for this conversation and express appreciation for any feedback or suggestions.
  • #1
Kevin_H
5
0
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.
 
Physics news on Phys.org
  • #2
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?
 

1. How do you prove that one but not both of these systems is consistent?

The most common way to prove that one but not both of these systems is consistent is through the use of a proof by contradiction. This involves assuming both systems are consistent and then showing that this leads to a contradiction, thus proving one of the systems must be inconsistent.

2. What is the importance of proving consistency in a scientific experiment?

Proving consistency is crucial in a scientific experiment as it ensures that the results obtained can be trusted and replicated. A consistent experiment means that the results are not affected by any external factors and are reliable.

3. Can an inconsistent system still produce accurate results?

No, an inconsistent system cannot produce accurate results. If a system is inconsistent, it means that there is a contradiction in the assumptions or principles it is based on, which can lead to unpredictable and unreliable results.

4. What are some common techniques used to prove consistency?

Aside from proof by contradiction, other techniques used to prove consistency include mathematical induction, proof by construction, and model theory. These methods involve systematically analyzing the principles of a system and showing that they are logically sound and consistent.

5. Are there any limitations to proving consistency?

There are some limitations to proving consistency, as it can be a complex and time-consuming process. In some cases, it may be impossible to prove consistency due to the complexity of the system or the lack of information. Also, proving consistency does not necessarily mean that the system is completely free of errors or flaws.

Similar threads

  • Calculus and Beyond Homework Help
Replies
16
Views
860
  • Calculus and Beyond Homework Help
Replies
1
Views
456
  • Calculus and Beyond Homework Help
Replies
24
Views
616
  • Calculus and Beyond Homework Help
Replies
2
Views
132
  • Calculus and Beyond Homework Help
Replies
13
Views
2K
  • Calculus and Beyond Homework Help
2
Replies
43
Views
3K
  • Calculus and Beyond Homework Help
Replies
8
Views
533
  • Calculus and Beyond Homework Help
Replies
6
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
8
Views
1K
Back
Top