Namespaces
Variants
Actions

Difference between revisions of "Motzkin transposition theorem"

From Encyclopedia of Mathematics
Jump to: navigation, search
(some TeX)
(some TeX)
Line 52: Line 52:
 
==Farkas theorem.==
 
==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.
+
(See also [[#References|[a2]]].) Let $A$ be a given matrix and $\mathbf{b}$ 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.
Line 72: Line 72:
 
==Gordan's theorem.==
 
==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:
+
(See also [[#References|[a3]]].) Given a matrix $A$, the following are alternatives:
 
+
<ol style="list-style-type: none;">
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" />;
+
<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>
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" />.
+
</ol>
  
  
Line 82: Line 82:
 
==Stiemke's theorem.==
 
==Stiemke's theorem.==
  
(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:
+
(See also [[#References|[a9]]].) Given a matrix $A$, the following are alternatives:
 
+
<ol style="list-style-type: none;">
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" />;
+
<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>
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" />.
+
</ol>
  
 
<img style="border:1px solid;" src="https://www.encyclopediaofmath.org/legacyimages/common_img/m130240a.gif" />
 
<img style="border:1px solid;" src="https://www.encyclopediaofmath.org/legacyimages/common_img/m130240a.gif" />
Line 92: Line 92:
 
Figure: m130240a
 
Figure: m130240a
  
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" />
+
A hyperplane with normal $\mathbf{y}$ separating $\mathbf{b}$ and $\mathbf{R}^+(A)$
  
 
<img style="border:1px solid;" src="https://www.encyclopediaofmath.org/legacyimages/common_img/m130240b.gif" />
 
<img style="border:1px solid;" src="https://www.encyclopediaofmath.org/legacyimages/common_img/m130240b.gif" />
Line 98: Line 98:
 
Figure: m130240b
 
Figure: m130240b
  
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" />
+
Illustration of the alternatives \eqref{eq:2}: $L \cap C = \{\mathbf{0}\}$, $L^\perp \cap \textbf{int}\; C^* \neq \emptyset$
  
  
Line 104: Line 104:
 
==Separation theorems.==
 
==Separation theorems.==
  
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
+
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}
<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>
+
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/m13024091.png" /></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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130240/m13024092.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/m13024093.png" /></td> <td valign="top" style="width:5%;text-align:right;">(a2)</td></tr></table>
 
  
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
+
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/m13024096.png" /></td> <td valign="top" style="width:5%;text-align:right;">(a3)</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,
 
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. Fig.a1), 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}
  
<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>
+
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).
 
 
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
 
 
 
<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 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" />,
+
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$.
  
<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>
+
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 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>
 
  
 +
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. Fig.a2), for otherwise
 
are mutually exclusive (see e.g. Fig.a2), 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}
 +
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.
  
<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>
+
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.
 
 
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.
 
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.

Revision as of 08:18, 26 April 2016


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}$.

Figure: m130240a

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

Figure: m130240b

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


Separation theorems.

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. Fig.a1), 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. Fig.a2), 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} 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, "Über die Auflösungen linearer Gleighungen mit reelen 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=38643
This article was adapted from an original article by Adi Ben-Israel (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article