Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Do you know a proof for the fundamental theorem of linear inequalities, which does not employ an implicit use of the simplex algorithm?

Let $a_1, \dots, a_n, b \in \mathbb R^m$. Then either $b$ is a non-negative linear combination of linearly independent vectors from $a_1,\dots,a_n$, or there does exist $c \in \mathbb R^n$ such that $\{cx = 0\}$ contains $(t-1)$ linearly independent vectors from $a_1,\dots,a_n$ and such that we have $cb < 0$ and $c a_1, \dots, c a_n \geq 0$, where $t = \dim\operatorname{span}\{a_1,\dots,a_n,b\}$.

By a variant of Caratheodory's theorem. We know that $b$ is a non-negative linear combination of linearly independent vectors from $a_1,\dots,a_n$ if and only if $b$ is a non-negative linear combination of vectors from $a_1,\dots,a_n$. The existence of $c$ follows from the Hahn-Banach separation theorem. It remains to build $c$ such that it contains enough vectors from $\{a_1,\dots,a_n\}$.

Addendum: The difficulity boils down to the following question: Given a spanning set $a_1, \dots, a_n$ of $\mathbb R^m$ and a vector $b$, can you choose $m-1$ linearly independent vectors $z_1, \dots, z_{m-1}$ of the $a_i$, such that the $a_i$ and $b$ lie on different sides of $\operatorname{span} \{ z_1, \dots, z_{m-1} \}$?

share|improve this question

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.