Namespaces
Variants
Actions

Difference between revisions of "Motzkin transposition theorem"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (Corrected category.)
(correction)
 
(6 intermediate revisions by one other user not shown)
Line 1: Line 1:
{{TEX|part}}
+
{{TEX|done}}
  
 
The thesis of T.S. Motzkin, [[#References|[a6]]], in particular his transposition theorem, was a milestone in the development of linear inequalities and related areas.
 
The thesis of T.S. Motzkin, [[#References|[a6]]], in particular his transposition theorem, was a milestone in the development of linear inequalities and related areas.
Line 19: Line 19:
  
  
==Relations between a)–f).==
+
==Relations between a)–f)==
  
  
Line 33: Line 33:
 
The following two versions of Motzkin's transposition theorem, [[#References|[a6]]], concern systems c) and f):
 
The following two versions of Motzkin's transposition theorem, [[#References|[a6]]], concern systems c) and f):
  
(solvability of c)) Given matrices <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m13024033.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m13024034.png" /> and vectors <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m13024035.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m13024036.png" />, the following are equivalent:
+
<ol style="list-style-type: none;">
 +
<li>'''(solvability of c))''' Given matrices $A$, $B$ and vectors $\mathbf{b}$, $\mathbf{c}$, the following are equivalent:</li>
 +
<li><ol style="list-style-type: none;">
 +
<li>c1) the system $A\mathbf{x}\leq\mathbf{b}$, $B\mathbf{x}<\mathbf{c}$ has a solution $\mathbf{x}$;</li>
 +
<li>c2) for all vectors $\mathbf{y}\geq\mathbf{0}$, $\mathbf{z}\geq\mathbf{0}$, \begin{equation} A^T\mathbf{y}+B^T\mathbf{z}=\mathbf{0} \;\Rightarrow\;\mathbf{b}^T\mathbf{y}+\mathbf{c}^T\mathbf{z}\geq\mathbf{0}. \end{equation} and \begin{equation} A^T\mathbf{y}+B^T\mathbf{z}=\mathbf{0}, \mathbf{z}\neq\mathbf{0} \;\Rightarrow\;\mathbf{b}^T\mathbf{y}+\mathbf{c}^T\mathbf{z}>\mathbf{0}. \end{equation}</li>
 +
</ol></li>
 +
<li>'''(solvability of f))''' Let $A$, $B$, $C$ be given matrices, with $A$ non-vacuous. Then the following are alternatives:</li>
 +
<li><ol style="list-style-type: none;">
 +
<li>f1) $A\mathbf{x}>\mathbf{0}$, $B\mathbf{x}\geq\mathbf{0}$, $C\mathbf{x}=\mathbf{0}$ has a solution $\mathbf{x}$;</li>
 +
<li>f2) $A^T\mathbf{y}_1+B^T\mathbf{y}_2+C^T\mathbf{y}_3=\mathbf{0}$, $\mathbf{y}_1\gneq\mathbf{0}$, $\mathbf{y}_2\geq\mathbf{0}$ has solutions $\mathbf{y}_1$, $\mathbf{y}_2$, $\mathbf{y}_3$.</li>
 +
</ol></li>
 +
</ol>
  
c1) the system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m13024037.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m13024038.png" /> has a solution <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m13024039.png" />;
+
Special cases of Motzkin's theorem include the following theorems.
  
c2) for all vectors <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m13024040.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m13024041.png" />,
 
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m13024042.png" /></td> </tr></table>
 
  
and
+
==Farkas theorem==
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m13024043.png" /></td> </tr></table>
+
(See also [[#References|[a2]]].) Let $A$ be a given matrix and $\mathbf{b}$ a given vector.
 
 
(solvability of f)) Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m13024044.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m13024045.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m13024046.png" /> be given matrices, with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m13024047.png" /> non-vacuous. Then the following are alternatives:
 
 
 
f1) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m13024048.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m13024049.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m13024050.png" /> has a solution <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m13024051.png" />;
 
 
 
f2) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m13024052.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m13024053.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m13024054.png" /> has solutions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m13024055.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m13024056.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m13024057.png" />.
 
 
 
Special cases of Motzkin's theorem include the following theorems.
 
 
 
==Farkas theorem.==
 
(See also [[#References|[a2]]].) Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m13024058.png" /> be a given matrix and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m13024059.png" /> a given vector.
 
  
 
Farkas' theorem for system a) says that the following are equivalent:
 
Farkas' theorem for system a) says that the following are equivalent:
 
+
<ol style="list-style-type: none;">
a1) the system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m13024060.png" /> has a solution <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m13024061.png" />;
+
<li>a1) the system $A\mathbf{x}\leq\mathbf{b}$ has a solution $\mathbf{x}$;</li>
 
+
<li>a2) $A^T\mathbf{y}=\mathbf{0}, \;\mathbf{y}\geq\mathbf{0} \;\Rightarrow\; \mathbf{b}^T\mathbf{y}\geq 0$.</li>
a2) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m13024062.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m13024063.png" /> <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m13024064.png" /> <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m13024065.png" />.
+
</ol>
  
 
Farkas' theorem for system b) says that the following are equivalent:
 
Farkas' theorem for system b) says that the following are equivalent:
 
+
<ol style="list-style-type: none;">
b1) the system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m13024066.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m13024067.png" /> has a solution <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m13024068.png" />;
+
<li>b1) the system $A\mathbf{x}=\mathbf{b}$, $\mathbf{x}\geq\mathbf{0}$ has a solution $\mathbf{x}$;</li>
 
+
<li>b2) $A^T\mathbf{y}\geq\mathbf{0} \;\Rightarrow\; \mathbf{b}^T\mathbf{y}\geq 0$.</li>
b2) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m13024069.png" /> <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m13024070.png" /> <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m13024071.png" />.
+
</ol>
  
 
The positively homogeneous systems d) and e) are covered by the following two theorems.
 
The positively homogeneous systems d) and e) are covered by the following two theorems.
  
==Gordan's theorem.==
 
(See also [[#References|[a3]]].) Given a matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m13024072.png" />, the following are alternatives:
 
  
d1) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m13024073.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m13024074.png" /> has a solution <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m13024075.png" />;
 
  
d2) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m13024076.png" /> has a solution <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m13024077.png" />.
+
==Gordan's theorem==
  
==Stiemke's theorem.==
+
(See also [[#References|[a3]]].) Given a matrix $A$, the following are alternatives:
(See also [[#References|[a9]]].) Given a matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m13024078.png" />, the following are alternatives:
+
<ol style="list-style-type: none;">
 +
<li>d1) $A\mathbf{x}=\mathbf{0}$, $\mathbf{x}\gneq\mathbf{0}$ has a solution $\mathbf{x}$;</li>
 +
<li>d2) $A^T\mathbf{y}>\mathbf{0}$ has a solution $\mathbf{y}$.</li>
 +
</ol>
  
e1) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m13024079.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m13024080.png" /> has a solution <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m13024081.png" />;
 
  
e2) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m13024082.png" /> has a solution <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m13024083.png" />.
 
  
<img style="border:1px solid;" src="https://www.encyclopediaofmath.org/legacyimages/common_img/m130240a.gif" />
+
==Stiemke's theorem==
  
Figure: m130240a
+
(See also [[#References|[a9]]].) Given a matrix $A$, the following are alternatives:
 +
<ol style="list-style-type: none;">
 +
<li>e1) $A\mathbf{x}=\mathbf{0}$, $\mathbf{x}>\mathbf{0}$ has a solution $\mathbf{x}$;</li>
 +
<li>e2) $A^T\mathbf{y}\gneq\mathbf{0}$ has a solution $\mathbf{y}$.</li>
 +
</ol>
  
A hyperplane with normal <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m13024084.png" /> separating <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m13024085.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m13024086.png" />
 
  
<img style="border:1px solid;" src="https://www.encyclopediaofmath.org/legacyimages/common_img/m130240b.gif" />
 
  
Figure: m130240b
+
==Separation theorems==
  
Illustration of the alternatives (a6): <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m13024087.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m13024088.png" />
+
<span id="Fig1">
 +
[[File:Motzkin-transposition-theorem-1.gif| right| frame| Figure 1. A hyperplane with normal $\mathbf{y}$ separating $\mathbf{b}$ and $\mathbf{R}^+(A)$]]
 +
</span>
  
==Separation theorems.==
+
The above results are separation theorems, or statements about the existence of [[hyperplane]]s separating certain disjoint [[convex set]]s. First, some terminology. A set $P\subset\mathbf{R}^n$ is polyhedral (and necessarily convex) if it is the intersection of finitely many closed half-spaces, say
The above results are separation theorems, or statements about the existence of hyperplanes separating certain disjoint convex sets. First, some terminology. A set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m13024089.png" /> is polyhedral (and necessarily convex) if it is the intersection of finitely many closed half-spaces, say
+
\begin{equation} P:=\{\mathbf{x}\colon B\mathbf{x}\leq\mathbf{b}\} \end{equation}
 +
for some matrix $B$ and vector $\mathbf{b}$.
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m13024090.png" /></td> <td valign="top" style="width:5%;text-align:right;">(a1)</td></tr></table>
+
A finitely generated cone is the set of non-negative linear combinations of finitely many vectors (generators). An example is the cone generated by the columns of a matrix $A$:
 +
\begin{equation} \mathbf{R}^+(A):=\{A\mathbf{x}\colon \mathbf{x}\leq\mathbf{0}\} \end{equation}
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m13024091.png" /></td> </tr></table>
+
The dual (or polar) $S^*$ of a non-empty set $S\subset\mathbf{R}^n$ is defined as
 +
\begin{equation} S^*:=\{\mathbf{y}\colon \mathbf{s}\in S \;\Rightarrow\;\mathbf{y}^T\mathbf{s}\geq 0\}; \end{equation}
 +
it is a closed [[convex cone]]. In particular,
 +
\begin{equation}\label{eq:1} \left(\mathbf{R}^+(A)\right)^* =\{\mathbf{y}\colon A^T\mathbf{y}\geq \mathbf{0}\} \end{equation}
 +
is a polyhedral cone. Farkas' theorem b1) states that the vector $\mathbf{b}$ is in the cone $\mathbf{R}^+(A)$. The equivalent statement b2) says that $\mathbf{b}$ cannot be separated from $\mathbf{R}^+(A)$ by a [[hyperplane]]: such a separating hyperplane would have a normal $\mathbf{y}$ satisfying
 +
\begin{equation} \mathbf{b}^T\mathbf{y} < 0,\quad\mathbf{v}^T\mathbf{y}\geq 0 \end{equation}
 +
for all $\mathbf{v}\in\mathbf{R}^+(A)$ (see e.g. [[#Fig1|Figure&nbsp;1]]), which by \eqref{eq:1} is a negation of b2). Farkas' theorem for system b) states that for any matrix $A$,
 +
\begin{equation} \mathbf{R}^+(A)=\left(\mathbf{R}^+(A)\right)^{**} \end{equation}
  
A finitely generated cone is the set of non-negative linear combinations of finitely many vectors (generators). An example is the cone generated by the columns of a matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m13024092.png" />:
+
In general, a set $C\subset\mathbf{R}^n$ is a closed [[convex cone]] if and only if $C=C^{**}$. Farkas' theorem for system b) also implies that a cone in $\mathbf{R}^n$ is polyhedral if and only if it is finitely generated (the Farkas–Minkowski–Weyl theorem, [[#References|[a8]]], Corol. 7.1a). More generally, a set $S\subset\mathbf{R}^n$ is polyhedral if and only if it is the sum of a finitely generated cone and the [[convex hull]] of finitely many points (the Minkowski–Steinitz–Weyl theorem, [[#References|[a8]]], Corol. 7.1b).
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m13024093.png" /></td> <td valign="top" style="width:5%;text-align:right;">(a2)</td></tr></table>
+
The theorems of Stiemke and Gordan can be interpreted as geometric statements about intersections $C \cap L$ of a [[Pointed set|pointed]] closed [[convex cone]] $C$ and a subspace $L$ in $\mathbf{R}^n$. Let $\mathbf{R}^n_{+}$ denote the non-negative orthant in $\mathbf{R}^n$.
  
The dual (or polar) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m13024094.png" /> of a non-empty set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m13024095.png" /> is defined as
+
Thus, Gordan' theorem d1) says that $\mathbf{R}^n_{+}\cap N(A)\neq\mathbf{0}$, where $N(A)=\{\mathbf{x}\colon A\mathbf{x}=\mathbf{0}\}$ is the null space of $A$. And Stiemke's theorem e1) says that $\mathbf{int}\left(\mathbf{R}^n_{+}\right)\cap N(A)\neq\emptyset$, where $\mathbf{int}\left(\mathbf{R}^n_{+}\right)=\{\mathbf{x}\in\mathbf{R}^n\colon\mathbf{x>0}\}$.
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m13024096.png" /></td> <td valign="top" style="width:5%;text-align:right;">(a3)</td></tr></table>
+
In each case, the dual system uses the intersection $C^* \cap L^\perp$, where $L^\perp$ is the orthogonal complement of $L$. For example, the statements
 +
\begin{equation}\label{eq:2} \exists\mathbf{0}\neq\mathbf{x}\in C \cap L \quad\text{and}\quad \exists\mathbf{y}\in\left(\mathbf{int}\,C^*\right) \cap L^\perp \end{equation}
 +
are mutually exclusive (see e.g. [[#Fig2|Figure&nbsp;2]]), for otherwise
 +
\begin{equation} \mathbf{x}^T\mathbf{y} \begin{cases} =0 & \text{since}\;\mathbf{x}\perp\mathbf{y}, \\ >0 & \text{since}\;\mathbf{0}\neq\mathbf{x}\in C,\;\mathbf{y}\in\mathbf{int}\,C^* . \end{cases}\end{equation}
  
it is a closed convex cone. In particular,
+
<span id="Fig2">
 +
[[File:Motzkin-transposition-theorem-2.gif| right| frame| Figure 2. Illustration of the alternatives \eqref{eq:2}: $L \cap C = \{\mathbf{0}\}$, $L^\perp \cap \textbf{int}\; C^* \neq \emptyset$]]
 +
</span>
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m13024097.png" /></td> <td valign="top" style="width:5%;text-align:right;">(a4)</td></tr></table>
+
To make the statements in \eqref{eq:2} alternatives, one has to show that one of them occurs, the hard part of the proof. Returning to the theorems of Gordan and Stiemke, recall that $\left(\mathbf{R}^n_{+}\right)^*=\mathbf{R}^n_{+}$ and $N(A)^\perp=\mathbf{R}(A^T)$. Then Gordan's theorem d1), $\mathbf{R}^n_{+} \cap N(A)\neq\mathbf{0}$, and d2), $\mathbf{int}\left(\mathbf{R}^n_{+}\right)\cap\mathbf{R}(A^T)\neq\emptyset$, are alternatives.
  
is a polyhedral cone. Farkas' theorem b1) states that the vector <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m13024098.png" /> is in the cone <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m13024099.png" />. The equivalent statement b2) says that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m130240100.png" /> cannot be separated from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m130240101.png" /> by a hyperplane: such a separating hyperplane would have a normal <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m130240102.png" /> satisfying
+
Likewise, Stiemke's theorems e1), $\mathbf{int}\left(\mathbf{R}^n_{+}\right)\cap N(A)\neq\emptyset$, and e2), $\mathbf{R}^n_{+} \cap \mathbf{R}(A^T)\neq\mathbf{0}$, are alternatives.
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m130240103.png" /></td> </tr></table>
+
For history, see [[#References|[a8]]], pp. 209–228. For theorems of alternatives, see [[#References|[a5]]], pp. 27–37. Generalizations can be found in [[#References|[a10]]], [[#References|[a1]]], [[#References|[a11]]], Sec. 21–22, especially Thm. 21.1; 22.6. Finally, see [[#References|[a7]]], [[#References|[a5]]], p.100, for applications.
  
for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m130240104.png" /> (see e.g. Fig.a1), which by (a4) is a negation of b2). Farkas' theorem for system b) states that for any matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m130240105.png" />,
+
==References==
 
 
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m130240106.png" /></td> <td valign="top" style="width:5%;text-align:right;">(a5)</td></tr></table>
 
 
 
In general, a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m130240107.png" /> is a closed convex cone if and only if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m130240108.png" />. Farkas' theorem for system b) also implies that a cone in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m130240109.png" /> is polyhedral if and only if it is finitely generated (the Farkas–Minkowski–Weyl theorem, [[#References|[a8]]], Corol. 7.1a). More generally, a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m130240110.png" /> is polyhedral if and only if it is the sum of a finitely generated cone and the convex hull of finitely many points (the Minkowski–Steinitz–Weyl theorem, [[#References|[a8]]], Corol. 7.1b).
 
 
 
The theorems of Stiemke and Gordan can be interpreted as geometric statements about intersections <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m130240111.png" /> of a pointed closed convex cone <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m130240112.png" /> and a subspace <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m130240113.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m130240114.png" />. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m130240115.png" /> denote the non-negative orthant in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m130240116.png" />.
 
 
 
Thus, Gordan' theorem d1) says that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m130240117.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m130240118.png" /> is the null space of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m130240119.png" />. And Stiemke's theorem e1) says that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m130240120.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m130240121.png" />.
 
 
 
In each case, the dual system uses the intersection <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m130240122.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m130240123.png" /> is the orthogonal complement of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m130240124.png" />. For example, the statements
 
 
 
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m130240125.png" /></td> <td valign="top" style="width:5%;text-align:right;">(a6)</td></tr></table>
 
 
 
are mutually exclusive (see e.g. Fig.a2), for otherwise
 
 
 
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m130240126.png" /></td> </tr></table>
 
 
 
To make the statements in (a6) alternatives, one has to show that one of them occurs, the hard part of the proof. Returning to the theorems of Gordan and Stiemke, recall that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m130240127.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m130240128.png" />. Then Gordan's theorem d1), <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m130240129.png" />, and d2), <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m130240130.png" />, are alternatives.
 
 
 
Likewise, Stiemke's theorems e1), <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m130240131.png" />, and e2), <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m130240132.png" />, are alternatives.
 
 
 
For history, see [[#References|[a8]]], pp. 209–228. For theorems of alternatives, see [[#References|[a5]]], pp. 27–37. Generalizations can be found in [[#References|[a10]]], [[#References|[a1]]], [[#References|[a11]]], Sec. 21–22, especially Thm. 21.1; 22.6. Finally, see [[#References|[a7]]], [[#References|[a5]]], p.100, for applications.
 
  
====References====
+
<table>
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  K. Fan,  "Systems of linear inequalities"  H.W. Kuhn (ed.)  A.W. Tucker (ed.) , ''Linear Inequalities and Related Systems'' , ''Ann. of Math. Stud.'' , '''38''' , Princeton Univ. Press  (1956,})  pp. 99–156</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  J. Farkas,  "Über die Theorie der einfachen Ungleichungen"  ''J. Reine Angew. Math.'' , '''124'''  (1902)  pp. 1–24</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  P. Gordan,  "Über die Auflösungen linearer Gleighungen mit reelen Coefficienten"  ''Math. Ann.'' , '''6'''  (1873)  pp. 23–28</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  "Linear inequalities and related systems"  H.W. Kuhn (ed.)  A.W. Tucker (ed.) , ''Ann. of Math. Stud.'' , '''38''' , Princeton Univ. Press  (1956)</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  O.L. Mangasarian,  "Nonlinear programming" , McGraw-Hill  (1969)</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  T.S. Motzkin,  "Beiträge zur Theorie der linearen Ungleichungen"  ''Inaugural Diss. (Basel, Jerusalem)''  (1936)</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  T.S. Motzkin,  "Two consequences of the transposition theorem on linear inequalities"  ''Econometrica'' , '''19'''  (1951)  pp. 184–185</TD></TR><TR><TD valign="top">[a8]</TD> <TD valign="top">  A. Schrijver,  "Theory of linear and integer programming" , Wiley/Interscience  (1986)</TD></TR><TR><TD valign="top">[a9]</TD> <TD valign="top">  E. Stiemke,  "Über positive Lösungen homogener linearer Gleichungen"  ''Math. Ann.'' , '''76'''  (1915)  pp. 340–342</TD></TR><TR><TD valign="top">[a10]</TD> <TD valign="top">  A.W. Tucker,  "Dual systems of homogeneous linear relations"  H.W. Kuhn (ed.)  A.W. Tucker (ed.) , ''Linear Inequalities and Related Systems'' , ''Ann. of Math. Stud.'' , '''38''' , Princeton Univ. Press  (1956)  pp. 3–18</TD></TR><TR><TD valign="top">[a11]</TD> <TD valign="top">  R.T. Rockafellar,  "Convex analysis" , Princeton Univ. Press  (1970)</TD></TR></table>
+
<TR><TD valign="top">[a1]</TD> <TD valign="top">  K. Fan,  "Systems of linear inequalities"  H.W. Kuhn (ed.)  A.W. Tucker (ed.) , ''Linear Inequalities and Related Systems'' , ''Ann. of Math. Stud.'' , '''38''' , Princeton Univ. Press  (1956,})  pp. 99–156</TD></TR>
 +
<TR><TD valign="top">[a2]</TD> <TD valign="top">  J. Farkas,  "Über die Theorie der einfachen Ungleichungen"  ''J. Reine Angew. Math.'' , '''124'''  (1902)  pp. 1–24</TD></TR>
 +
<TR><TD valign="top">[a3]</TD> <TD valign="top">  P. Gordan,  "Ueber die Auflösung linearer Gleichungen mit reellen Coefficienten"  ''Math. Ann.'' , '''6'''  (1873)  pp. 23–28</TD></TR>
 +
<TR><TD valign="top">[a4]</TD> <TD valign="top">  "Linear inequalities and related systems"  H.W. Kuhn (ed.)  A.W. Tucker (ed.) , ''Ann. of Math. Stud.'' , '''38''' , Princeton Univ. Press  (1956)</TD></TR>
 +
<TR><TD valign="top">[a5]</TD> <TD valign="top">  O.L. Mangasarian,  "Nonlinear programming" , McGraw-Hill  (1969)</TD></TR>
 +
<TR><TD valign="top">[a6]</TD> <TD valign="top">  T.S. Motzkin,  "Beiträge zur Theorie der linearen Ungleichungen"  ''Inaugural Diss. (Basel, Jerusalem)''  (1936)</TD></TR>
 +
<TR><TD valign="top">[a7]</TD> <TD valign="top">  T.S. Motzkin,  "Two consequences of the transposition theorem on linear inequalities"  ''Econometrica'' , '''19'''  (1951)  pp. 184–185</TD></TR>
 +
<TR><TD valign="top">[a8]</TD> <TD valign="top">  A. Schrijver,  "Theory of linear and integer programming" , Wiley/Interscience  (1986)</TD></TR>
 +
<TR><TD valign="top">[a9]</TD> <TD valign="top">  E. Stiemke,  "Über positive Lösungen homogener linearer Gleichungen"  ''Math. Ann.'' , '''76'''  (1915)  pp. 340–342</TD></TR>
 +
<TR><TD valign="top">[a10]</TD> <TD valign="top">  A.W. Tucker,  "Dual systems of homogeneous linear relations"  H.W. Kuhn (ed.)  A.W. Tucker (ed.) , ''Linear Inequalities and Related Systems'' , ''Ann. of Math. Stud.'' , '''38''' , Princeton Univ. Press  (1956)  pp. 3–18</TD></TR>
 +
<TR><TD valign="top">[a11]</TD> <TD valign="top">  R.T. Rockafellar,  "Convex analysis" , Princeton Univ. Press  (1970)</TD></TR></table>

Latest revision as of 19:13, 31 March 2017


The thesis of T.S. Motzkin, [a6], in particular his transposition theorem, was a milestone in the development of linear inequalities and related areas.

For two vectors $\mathbf{u} = (u_i)$ and $\mathbf{v} = (v_i)$ of equal dimension one denotes by $\mathbf{u}\geq\mathbf{v}$ and $\mathbf{u}>\mathbf{v}$ that the indicated inequality holds componentwise, and by $\mathbf{u}\gneq\mathbf{v}$ the fact $\mathbf{u}\geq\mathbf{v}$ and $\mathbf{u}\neq\mathbf{v}$.

Systems of linear inequalities appear in several forms; the following examples are typical:

  1. a) $A\mathbf{x}\leq\mathbf{b}$;
  2. b) $A\mathbf{x}=\mathbf{b}$, $\mathbf{x}\geq\mathbf{0}$;
  3. c) $A\mathbf{x}\leq\mathbf{b}$, $B\mathbf{x}<\mathbf{c}$;
  4. d) $A\mathbf{x}=\mathbf{0}$, $\mathbf{x}\gneq\mathbf{0}$;
  5. e) $A\mathbf{x}=\mathbf{0}$, $\mathbf{x}>\mathbf{0}$;
  6. f) $A\mathbf{x}>\mathbf{0}$, $B\mathbf{x}\geq\mathbf{0}$, $C\mathbf{x}=\mathbf{0}$.

In each of these so-called primal systems the existence of solutions is characterized by means of a dual system, using the transposes of matrices in the primal system. Hence the name "transposition theorem" . The relation between the primal and dual systems is sometimes given as a "theorem of alternatives" , listing alternatives, i.e. statements $P$, $Q$ satisfying $P\Leftrightarrow\neg Q$ (where $\neg$ denotes negation), in words: either $P$ or $Q$ but never both.


Relations between a)–f)

a) and b) are equivalent representations. Indeed, they can be written as \begin{equation} (A, -A, I) \begin{pmatrix} \mathbf{x}^+ \\ \mathbf{x}^- \\ \mathbf{s} \end{pmatrix} = \mathbf{b} \quad\text{and}\quad \begin{pmatrix} \mathbf{x}^+ \\ \mathbf{x}^- \\ \mathbf{s} \end{pmatrix} \geq \mathbf{0}, \end{equation} \begin{equation} \begin{pmatrix} A \\ -A \\ -I \end{pmatrix}\mathbf{x}\leq\begin{pmatrix} \mathbf{b} \\ -\mathbf{b} \\ \mathbf{0} \end{pmatrix},\end{equation} respectively.

The remaining systems involve strict inequalities or non-trivial solutions. For example, d) and e) concern the existence of non-trivial solutions and positive solutions, respectively, for the system \begin{equation} A\mathbf{x}=\mathbf{0}, \;\mathbf{x}\geq\mathbf{0}. \end{equation}

Taking $B=0$ and $\mathbf{c}>\mathbf{0}$ in c) gives a), showing that a) and b) are special cases of c). Similarly, the systems d) and e) are special cases of f), which itself is a special case of c) with $\mathbf{b}=\mathbf{0}$, $\mathbf{c}=\mathbf{0}$. In fact, every system of linear inequalities can be written as c).

The following two versions of Motzkin's transposition theorem, [a6], concern systems c) and f):

  1. (solvability of c)) Given matrices $A$, $B$ and vectors $\mathbf{b}$, $\mathbf{c}$, the following are equivalent:
    1. c1) the system $A\mathbf{x}\leq\mathbf{b}$, $B\mathbf{x}<\mathbf{c}$ has a solution $\mathbf{x}$;
    2. c2) for all vectors $\mathbf{y}\geq\mathbf{0}$, $\mathbf{z}\geq\mathbf{0}$, \begin{equation} A^T\mathbf{y}+B^T\mathbf{z}=\mathbf{0} \;\Rightarrow\;\mathbf{b}^T\mathbf{y}+\mathbf{c}^T\mathbf{z}\geq\mathbf{0}. \end{equation} and \begin{equation} A^T\mathbf{y}+B^T\mathbf{z}=\mathbf{0}, \mathbf{z}\neq\mathbf{0} \;\Rightarrow\;\mathbf{b}^T\mathbf{y}+\mathbf{c}^T\mathbf{z}>\mathbf{0}. \end{equation}
  2. (solvability of f)) Let $A$, $B$, $C$ be given matrices, with $A$ non-vacuous. Then the following are alternatives:
    1. f1) $A\mathbf{x}>\mathbf{0}$, $B\mathbf{x}\geq\mathbf{0}$, $C\mathbf{x}=\mathbf{0}$ has a solution $\mathbf{x}$;
    2. f2) $A^T\mathbf{y}_1+B^T\mathbf{y}_2+C^T\mathbf{y}_3=\mathbf{0}$, $\mathbf{y}_1\gneq\mathbf{0}$, $\mathbf{y}_2\geq\mathbf{0}$ has solutions $\mathbf{y}_1$, $\mathbf{y}_2$, $\mathbf{y}_3$.

Special cases of Motzkin's theorem include the following theorems.


Farkas theorem

(See also [a2].) Let $A$ be a given matrix and $\mathbf{b}$ a given vector.

Farkas' theorem for system a) says that the following are equivalent:

  1. a1) the system $A\mathbf{x}\leq\mathbf{b}$ has a solution $\mathbf{x}$;
  2. a2) $A^T\mathbf{y}=\mathbf{0}, \;\mathbf{y}\geq\mathbf{0} \;\Rightarrow\; \mathbf{b}^T\mathbf{y}\geq 0$.

Farkas' theorem for system b) says that the following are equivalent:

  1. b1) the system $A\mathbf{x}=\mathbf{b}$, $\mathbf{x}\geq\mathbf{0}$ has a solution $\mathbf{x}$;
  2. b2) $A^T\mathbf{y}\geq\mathbf{0} \;\Rightarrow\; \mathbf{b}^T\mathbf{y}\geq 0$.

The positively homogeneous systems d) and e) are covered by the following two theorems.


Gordan's theorem

(See also [a3].) Given a matrix $A$, the following are alternatives:

  1. d1) $A\mathbf{x}=\mathbf{0}$, $\mathbf{x}\gneq\mathbf{0}$ has a solution $\mathbf{x}$;
  2. d2) $A^T\mathbf{y}>\mathbf{0}$ has a solution $\mathbf{y}$.


Stiemke's theorem

(See also [a9].) Given a matrix $A$, the following are alternatives:

  1. e1) $A\mathbf{x}=\mathbf{0}$, $\mathbf{x}>\mathbf{0}$ has a solution $\mathbf{x}$;
  2. e2) $A^T\mathbf{y}\gneq\mathbf{0}$ has a solution $\mathbf{y}$.


Separation theorems

Figure 1. A hyperplane with normal $\mathbf{y}$ separating $\mathbf{b}$ and $\mathbf{R}^+(A)$

The above results are separation theorems, or statements about the existence of hyperplanes separating certain disjoint convex sets. First, some terminology. A set $P\subset\mathbf{R}^n$ is polyhedral (and necessarily convex) if it is the intersection of finitely many closed half-spaces, say \begin{equation} P:=\{\mathbf{x}\colon B\mathbf{x}\leq\mathbf{b}\} \end{equation} for some matrix $B$ and vector $\mathbf{b}$.

A finitely generated cone is the set of non-negative linear combinations of finitely many vectors (generators). An example is the cone generated by the columns of a matrix $A$: \begin{equation} \mathbf{R}^+(A):=\{A\mathbf{x}\colon \mathbf{x}\leq\mathbf{0}\} \end{equation}

The dual (or polar) $S^*$ of a non-empty set $S\subset\mathbf{R}^n$ is defined as \begin{equation} S^*:=\{\mathbf{y}\colon \mathbf{s}\in S \;\Rightarrow\;\mathbf{y}^T\mathbf{s}\geq 0\}; \end{equation} it is a closed convex cone. In particular, \begin{equation}\label{eq:1} \left(\mathbf{R}^+(A)\right)^* =\{\mathbf{y}\colon A^T\mathbf{y}\geq \mathbf{0}\} \end{equation} is a polyhedral cone. Farkas' theorem b1) states that the vector $\mathbf{b}$ is in the cone $\mathbf{R}^+(A)$. The equivalent statement b2) says that $\mathbf{b}$ cannot be separated from $\mathbf{R}^+(A)$ by a hyperplane: such a separating hyperplane would have a normal $\mathbf{y}$ satisfying \begin{equation} \mathbf{b}^T\mathbf{y} < 0,\quad\mathbf{v}^T\mathbf{y}\geq 0 \end{equation} for all $\mathbf{v}\in\mathbf{R}^+(A)$ (see e.g. Figure 1), which by \eqref{eq:1} is a negation of b2). Farkas' theorem for system b) states that for any matrix $A$, \begin{equation} \mathbf{R}^+(A)=\left(\mathbf{R}^+(A)\right)^{**} \end{equation}

In general, a set $C\subset\mathbf{R}^n$ is a closed convex cone if and only if $C=C^{**}$. Farkas' theorem for system b) also implies that a cone in $\mathbf{R}^n$ is polyhedral if and only if it is finitely generated (the Farkas–Minkowski–Weyl theorem, [a8], Corol. 7.1a). More generally, a set $S\subset\mathbf{R}^n$ is polyhedral if and only if it is the sum of a finitely generated cone and the convex hull of finitely many points (the Minkowski–Steinitz–Weyl theorem, [a8], Corol. 7.1b).

The theorems of Stiemke and Gordan can be interpreted as geometric statements about intersections $C \cap L$ of a pointed closed convex cone $C$ and a subspace $L$ in $\mathbf{R}^n$. Let $\mathbf{R}^n_{+}$ denote the non-negative orthant in $\mathbf{R}^n$.

Thus, Gordan' theorem d1) says that $\mathbf{R}^n_{+}\cap N(A)\neq\mathbf{0}$, where $N(A)=\{\mathbf{x}\colon A\mathbf{x}=\mathbf{0}\}$ is the null space of $A$. And Stiemke's theorem e1) says that $\mathbf{int}\left(\mathbf{R}^n_{+}\right)\cap N(A)\neq\emptyset$, where $\mathbf{int}\left(\mathbf{R}^n_{+}\right)=\{\mathbf{x}\in\mathbf{R}^n\colon\mathbf{x>0}\}$.

In each case, the dual system uses the intersection $C^* \cap L^\perp$, where $L^\perp$ is the orthogonal complement of $L$. For example, the statements \begin{equation}\label{eq:2} \exists\mathbf{0}\neq\mathbf{x}\in C \cap L \quad\text{and}\quad \exists\mathbf{y}\in\left(\mathbf{int}\,C^*\right) \cap L^\perp \end{equation} are mutually exclusive (see e.g. Figure 2), for otherwise \begin{equation} \mathbf{x}^T\mathbf{y} \begin{cases} =0 & \text{since}\;\mathbf{x}\perp\mathbf{y}, \\ >0 & \text{since}\;\mathbf{0}\neq\mathbf{x}\in C,\;\mathbf{y}\in\mathbf{int}\,C^* . \end{cases}\end{equation}

Figure 2. Illustration of the alternatives \eqref{eq:2}: $L \cap C = \{\mathbf{0}\}$, $L^\perp \cap \textbf{int}\; C^* \neq \emptyset$

To make the statements in \eqref{eq:2} alternatives, one has to show that one of them occurs, the hard part of the proof. Returning to the theorems of Gordan and Stiemke, recall that $\left(\mathbf{R}^n_{+}\right)^*=\mathbf{R}^n_{+}$ and $N(A)^\perp=\mathbf{R}(A^T)$. Then Gordan's theorem d1), $\mathbf{R}^n_{+} \cap N(A)\neq\mathbf{0}$, and d2), $\mathbf{int}\left(\mathbf{R}^n_{+}\right)\cap\mathbf{R}(A^T)\neq\emptyset$, are alternatives.

Likewise, Stiemke's theorems e1), $\mathbf{int}\left(\mathbf{R}^n_{+}\right)\cap N(A)\neq\emptyset$, and e2), $\mathbf{R}^n_{+} \cap \mathbf{R}(A^T)\neq\mathbf{0}$, are alternatives.

For history, see [a8], pp. 209–228. For theorems of alternatives, see [a5], pp. 27–37. Generalizations can be found in [a10], [a1], [a11], Sec. 21–22, especially Thm. 21.1; 22.6. Finally, see [a7], [a5], p.100, for applications.

References

[a1] K. Fan, "Systems of linear inequalities" H.W. Kuhn (ed.) A.W. Tucker (ed.) , Linear Inequalities and Related Systems , Ann. of Math. Stud. , 38 , Princeton Univ. Press (1956,}) pp. 99–156
[a2] J. Farkas, "Über die Theorie der einfachen Ungleichungen" J. Reine Angew. Math. , 124 (1902) pp. 1–24
[a3] P. Gordan, "Ueber die Auflösung linearer Gleichungen mit reellen Coefficienten" Math. Ann. , 6 (1873) pp. 23–28
[a4] "Linear inequalities and related systems" H.W. Kuhn (ed.) A.W. Tucker (ed.) , Ann. of Math. Stud. , 38 , Princeton Univ. Press (1956)
[a5] O.L. Mangasarian, "Nonlinear programming" , McGraw-Hill (1969)
[a6] T.S. Motzkin, "Beiträge zur Theorie der linearen Ungleichungen" Inaugural Diss. (Basel, Jerusalem) (1936)
[a7] T.S. Motzkin, "Two consequences of the transposition theorem on linear inequalities" Econometrica , 19 (1951) pp. 184–185
[a8] A. Schrijver, "Theory of linear and integer programming" , Wiley/Interscience (1986)
[a9] E. Stiemke, "Über positive Lösungen homogener linearer Gleichungen" Math. Ann. , 76 (1915) pp. 340–342
[a10] A.W. Tucker, "Dual systems of homogeneous linear relations" H.W. Kuhn (ed.) A.W. Tucker (ed.) , Linear Inequalities and Related Systems , Ann. of Math. Stud. , 38 , Princeton Univ. Press (1956) pp. 3–18
[a11] R.T. Rockafellar, "Convex analysis" , Princeton Univ. Press (1970)
How to Cite This Entry:
Motzkin transposition theorem. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Motzkin_transposition_theorem&oldid=38641
This article was adapted from an original article by Adi Ben-Israel (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article