Suppose we are given a polyhedron $P = \{x\in\mathbb{R}^n | Ax = b, x\geq 0\}$, where $A\in\mathbb{R}^{m\times n}$ has linearly independent rows. I want to show that an extreme point of this polyhedron is a basic feasible solution to the associated linear program $\text{max}\{c^Tx | Ax = b, x\geq 0\}$.
My attempt is by using tight/active constraints, as follows. First, we can re-write the polyhedron P as $P = \{x\in\mathbb{R}^n | \begin{pmatrix}A\\ -A\\ -I\end{pmatrix}x\leq\begin{bmatrix}b\\ -b\\ 0\end{bmatrix}\}$. For concise-ness take $M := \begin{pmatrix}A\\ -A\\ -I\end{pmatrix}$ and $f := \begin{bmatrix}b\\ -b\\ 0\end{bmatrix}$, so $P = \{x\in\mathbb{R}^n | Mx\leq f\}$. Then if $\bar{x}$ is an extreme point of $P$, we know that the matrix of tight/active constraints $M^=$ is rank $n$, i.e. the columns of $M^=$ are linearly independent. In order to show that $\bar{x}$ is a BFS (basic feasible solution), I want to find a basis $B$ (given by some subset of the column indices $\{1, ..., n\}$ which form a basis of $\mathbb{R}^m$) such that $\bar{x}$ is a BFS for $B$, i.e. $\bar{x}_j = 0$ for all components $j\notin B$. To do this, I first look at $M^=$. The block constraints $Ax\leq b$ and $-Ax\leq -b$ are clearly tight for $\bar{x}$, but since $\text{rank}(\begin{pmatrix}A\\ -A\end{pmatrix}) = \text{rank}(A) = m\leq n$, then it must be that at least $n - m$ of the constraints of the block $-Ix\leq 0$ are tight for $\bar{x}$ as well. Or in other words, there must be at least $n - m$ components of $\bar{x}$ that are $0$.
So take $J\subset \{1, ..., n\}$ to be any particular $n - m$ indices for which $\bar{x}_j = 0\; \forall j\in J$. What I am trying to show is that $\{1, ..., n\}\setminus J$ is a basis for which $\bar{x}$ is a BFS. So let $B := \{1, ..., n\}\setminus J$. Since $|B| = m$, then to show $B$ is a basis, it suffices to show that the columns of $B$ are linearly independent. So if they were not, then the columns of $A_B$ would be linearly dependent, and so the columns of $A$ would be too. So let $d\in\mathbb{R}^n\setminus 0$ be a vector such that $Ad = 0$. We can assume W.L.O.G. that $d_J = 0$. We know that $\begin{pmatrix}A\\ -A\\ -I_J \;0\end{pmatrix}$ is a sub-matrix of $M^=$. If it were $\textit{equal}$ to $M^=$, then we would have that $M^=d = \begin{pmatrix}Ad\\ -Ad\\ (-I_J \;0)d\end{pmatrix} = \begin{pmatrix}0\\ 0\\ 0\end{pmatrix}$, which means the columns of $M^=$ are linearly dependent, which would contradict the fact that $\text{rank}(M^=) = n$, meaning that $B$ must have actually been linearly independent columns (hence a basis).
But the other possibility is that there are strictly more rows of $M$ that are in $M^=$, which must come from the basic components of $\bar{x}$ being 0. If $d$ is non-zero for such a component, then $d$ is no longer in the null space of $M^=$, and I no longer have a way of contradicting the linear independence of the columns of $M^=$. How do I address this issue to complete the proof? Or have I simply gone about this the wrong way?
