Return to Answer

Here is a proof that uses directly the separating hyperplane theorem, which states the following.

Given a matrix $A$ and column matrix $b$, \begin{align} Ax=b, &\text{ for some column matrix }x\ge0 \\ &\iff \\ y^TA\ge0 &\text{ for some column matrix }y \implies y^Tb\ge0 \end{align}

We put the required proposition into the above form with the exception that the matrix is transposed. The premise of the proposition is \begin{align} &\begin{bmatrix} A & b \\ 0 & 1 \end{bmatrix}\begin{bmatrix} -xx_1 \\ x_1 \end{bmatrix}\ge 0 \\ &\iff \\ &\begin{cases} Ax\le b \implies a'^Tx\le b' \\ x_1\ge0 \end{cases} \\ &\implies \\ &\begin{bmatrix}a'^T &b'\end{bmatrix} \begin{bmatrix}-xx_1 \\x_1 \end{bmatrix}\ge0 \end{align}

The conclusion of the proposition is \begin{align} &\begin{bmatrix}\lambda^T & \lambda_1\end{bmatrix}\begin{bmatrix} A & b \\ 0 & 1 \end{bmatrix}=\begin{bmatrix}a'^T & b'\end{bmatrix}, \text{ for some} \begin{bmatrix}\lambda^T & \lambda_1\end{bmatrix}\ge0 \\ &\iff \\ &\exists \lambda\ge0 \ni \begin{cases} \lambda^TA=a'^T \\ \lambda^Tb\le b' \end{cases} \end{align}

The premise and the conclusion are seen to be equivalent in view of the separating hyperplane theorem as stated above. We have now proved the desired proposition.

Here is a proof that uses directly the separating hyperplane theorem, which states the following.

Given a matrix $A$ and column matrix $b$, \begin{align} Ax=b, &\text{ for some column matrix }x\ge0 \\ &\iff \\ y^TA\ge0 &\text{ for some column matrix }y \implies y^Tb\ge0 \end{align}

We put as follows the required proposition into the above form with the exception that the matrix is transposed. The premise of the proposition is \begin{align} &\begin{bmatrix} A & b \\ 0 & 1 \end{bmatrix}\begin{bmatrix} -xx_1 \\ x_1 \end{bmatrix}\ge 0 \\ &\iff \\ &\begin{cases} Ax\le b \implies a'^Tx\le b' \\ x_1\ge0 \end{cases} \\ &\implies \\ &\begin{bmatrix}a'^T &b'\end{bmatrix} \begin{bmatrix}-xx_1 \\x_1 \end{bmatrix}\ge0 \end{align}

The conclusion of the proposition is \begin{align} &\begin{bmatrix}\lambda^T & \lambda_1\end{bmatrix}\begin{bmatrix} A & b \\ 0 & 1 \end{bmatrix}=\begin{bmatrix}a'^T & b'\end{bmatrix}, \text{ for some} \begin{bmatrix}\lambda^T & \lambda_1\end{bmatrix}\ge0 \\ &\iff \\ &\exists \lambda\ge0 \ni \begin{cases} \lambda^TA=a'^T \\ \lambda^Tb\le b' \end{cases} \end{align}

The premise and the conclusion are seen to be equivalent in view of the separating hyperplane theorem as stated above. We have now proved the desired proposition.

Here is a proof that uses directly the separating hyperplane theorem, which states the following.

Given a matrix $A$ and column matrix $b$, \begin{align} Ax=b, &\text{ for some column matrix }x\ge0 \\ &\iff \\ y^TA\ge0 &\text{ for some column matrix }y \implies y^Tb\ge0 \end{align}

We put the required proposition into the above form. The premise of the proposition is \begin{align} &\begin{bmatrix} A & b \\ 0 & 1 \end{bmatrix}\begin{bmatrix} -xx_1 \\ x_1 \end{bmatrix}\ge 0 \\ &\iff \\ &\begin{cases} Ax\le b \implies a'^Tx\le b' \\ x_1\ge0 \end{cases} \\ &\implies \\ &\begin{bmatrix}a'^T &b'\end{bmatrix} \begin{bmatrix}-xx_1 \\x_1 \end{bmatrix}\ge0 \end{align}

The conclusion of the proposition is \begin{align} &\begin{bmatrix}\lambda^T & \lambda_1\end{bmatrix}\begin{bmatrix} A & b \\ 0 & 1 \end{bmatrix}=\begin{bmatrix}a'^T & b'\end{bmatrix}, \text{ for some} \begin{bmatrix}\lambda^T & \lambda_1\end{bmatrix}\ge0 \\ &\iff \\ &\exists \lambda\ge0 \ni \begin{cases} \lambda^TA=a'^T \\ \lambda^Tb\le b' \end{cases} \end{align}

The premise and the conclusion are seen to be equivalent in view of the separating hyperplane theorem as stated above. We have now proved the desired proposition.

Here is a proof that uses directly the separating hyperplane theorem, which states the following.

Given a matrix $A$ and column matrix $b$, \begin{align} Ax=b, &\text{ for some column matrix }x\ge0 \\ &\iff \\ y^TA\ge0 &\text{ for some column matrix }y \implies y^Tb\ge0 \end{align}

We put the required proposition into the above form with the exception that the matrix is transposed. The premise of the proposition is \begin{align} &\begin{bmatrix} A & b \\ 0 & 1 \end{bmatrix}\begin{bmatrix} -xx_1 \\ x_1 \end{bmatrix}\ge 0 \\ &\iff \\ &\begin{cases} Ax\le b \implies a'^Tx\le b' \\ x_1\ge0 \end{cases} \\ &\implies \\ &\begin{bmatrix}a'^T &b'\end{bmatrix} \begin{bmatrix}-xx_1 \\x_1 \end{bmatrix}\ge0 \end{align}

The conclusion of the proposition is \begin{align} &\begin{bmatrix}\lambda^T & \lambda_1\end{bmatrix}\begin{bmatrix} A & b \\ 0 & 1 \end{bmatrix}=\begin{bmatrix}a'^T & b'\end{bmatrix}, \text{ for some} \begin{bmatrix}\lambda^T & \lambda_1\end{bmatrix}\ge0 \\ &\iff \\ &\exists \lambda\ge0 \ni \begin{cases} \lambda^TA=a'^T \\ \lambda^Tb\le b' \end{cases} \end{align}

The premise and the conclusion are seen to be equivalent in view of the separating hyperplane theorem as stated above. We have now proved the desired proposition.

Here is a proof that uses directly the separating hyperplane theorem, which states the following.

Given a matrix $A$ and column matrix $b$, \begin{align} Ax=b, &\text{ for some column matrix }x\ge0 \\ &\iff \\ y^TA\ge0 &\text{ for some column matrix }y \implies y^Tb\ge0 \end{align}

We will put the required proposition into the above form. $$\begin{bmatrix} A & b \\ 0 & 1 \end{bmatrix}\begin{bmatrix} -xx_1 \\ x_1 \end{bmatrix}\ge 0 \iff Ax\le b \implies a'^Tx\le b' \iff \begin{bmatrix}a'^T &b'\end{bmatrix} \begin{bmatrix} -xx_1 \\ x_1 \end{bmatrix}\ge0 $$

Here is a proof that uses directly the separating hyperplane theorem, which states the following.

Given a matrix $A$ and column matrix $b$, \begin{align} Ax=b, &\text{ for some column matrix }x\ge0 \\ &\iff \\ y^TA\ge0 &\text{ for some column matrix }y \implies y^Tb\ge0 \end{align}

We put the required proposition into the above form. The premise of the proposition is \begin{align} &\begin{bmatrix} A & b \\ 0 & 1 \end{bmatrix}\begin{bmatrix} -xx_1 \\ x_1 \end{bmatrix}\ge 0 \\ &\iff \\ &\begin{cases} Ax\le b \implies a'^Tx\le b' \\ x_1\ge0 \end{cases} \\ &\implies \\ &\begin{bmatrix}a'^T &b'\end{bmatrix} \begin{bmatrix}-xx_1 \\x_1 \end{bmatrix}\ge0 \end{align}

The conclusion of the proposition is \begin{align} &\begin{bmatrix}\lambda^T & \lambda_1\end{bmatrix}\begin{bmatrix} A & b \\ 0 & 1 \end{bmatrix}=\begin{bmatrix}a'^T & b'\end{bmatrix}, \text{ for some} \begin{bmatrix}\lambda^T & \lambda_1\end{bmatrix}\ge0 \\ &\iff \\ &\exists \lambda\ge0 \ni \begin{cases} \lambda^TA=a'^T \\ \lambda^Tb\le b' \end{cases} \end{align}

The premise and the conclusion are seen to be equivalent in view of the separating hyperplane theorem as stated above. We have now proved the desired proposition.