Say I have the following system of linear equations and non-negativity constraints:
\begin{align*}
f:\quad 2x_1+1x_2+1x_3+0x_4&=4, \\
g:\quad 1x_1+2x_2+0x_3+1x_4&=3, \\
x_1,x_2,x_3,x_4 &\geq 0.
\end{align*}
Finding a column space basis $x_2$ and $x_3$ yields the basic feasible solution $x=(0,\frac{3}{2},\frac{5}{2},0)$ when solving the system reduced to just those two variables. I can't figure out why that coordinate is the coordinate of an extreme point of a polyhedron formed by the intersection of the linear equations.
I was thinking vaguely along the lines of "well $f$ and $g$ must intersect at one point since they are linearly independent, and since $x_2$ and $x_3$ form a basis for the column space, the reduced $f$ and $g$ must also intersect at that point". But I can't prove let alone generalise any of this.
Any help would be greatly appreciated!
Best Answer
Your polyhedron $P\subseteq\mathbb R^4$ is given by two equations intersecting in a plane together with the four inequalities $x_1,x_2,x_3,x_4\ge 0$.
Consider the linear form $\omega(x)=x_1+x_4$. Since $x_1,x_4\ge 0$, this linear form will be non-negative for all points in $P$. Hence, the minimum value $\omega$ takes on $P$ will be at least zero: $\min_{x\in P} \omega(x) \ge 0$. The only way it can be zero is by having $x_1=x_4=0$ and doing so you find that you get only a single point: $$ P \cap \{\, x \,|\, x_1=x_4=0 \,\} = \{\, (0, \tfrac 3 2, \tfrac 5 2, 0)\, \}. $$ Hence $v=(0, \tfrac 3 2, \tfrac 5 2, 0)$ is the unique point of $P$ minimizing $\omega$, so it is an extreme point (a vertex) of $P$.
Your linear system is given by the equation $Ax=b$ where $$ A = \begin{pmatrix} 2&1&1&0 \\ 1&2&0&1\end{pmatrix} \quad\text{and}\quad b = \begin{pmatrix} 4\\3 \end{pmatrix}. $$ The system $Ax=b$ is equivalent to the vector equation $$ x_1 \begin{pmatrix} 2\\1 \end{pmatrix} + x_2 \begin{pmatrix} 1\\2 \end{pmatrix} + x_3 \begin{pmatrix} 1\\0 \end{pmatrix} + x_4 \begin{pmatrix} 0\\1 \end{pmatrix} = \begin{pmatrix} 4\\3 \end{pmatrix}. $$ So the solutions of $Ax=b$ correspond to linear combinations of the columns of $A$ that evaluate to $b$.
Since the 2nd and 3rd column of $A$ form a basis of the column space, each vector in the column space of $A$ is a unique linear combination of those two columns. Since the rank of $A$ is $2$, any choice of $b$ is in the column space of $A$, so $Ax=b$ does indeed have solutions.
Looking at the vector equation above, we see that linear combinations of the 2nd and 3rd columns of $A$ that yield $b$ correspond to solutions of the linear system with $x_1,x_4=0$.
So, since there is a unique linear combination of the 2nd and 3rd columns of $A$ that yields $b$, there is a unique solution of $Ax=b$ with $x_1,x_4=0$.