I want to prove that a polyhedron $P = \{x\in\mathbb{R}^n\;:\;Ax\leq b\}$ has an extreme point if and only if it does not contain a line, but I want to do so in a particular way (I am aware of a proof by induction on $n$ which generalizes this result for any closed convex set, but this is not how I want to go about the proof here). Specifically I want to utilize the result that:
$x$ is an extreme point of $P$ if and only if $\text{rank}(A^=) = n$, where $A^=$ is the matrix of tight/active constraints of $x$.
I already know how to prove that if $P$ contains a line then $P$ has no extreme points, but my question is about the converse. I have an informal sketch of a proof, but I would appreciate some help making it rigorous. I want to show that if $P$ contains no extreme points, then it must contain a line. Here is my rough idea:
Let $x\in P$. We know it is not extreme, so therefore there exists $d_1\in\mathbb{R}^n$ such that $x + td_1\in P$ for $t\in (-\varepsilon_1, \varepsilon_1)$ for sufficiently small $\varepsilon_1$. Either $x + td_1$ is a line contained in $P$, in which case we are done, or $x \pm td_1$ has an active/tight constraint for some $t = t_1$. WLOG assume the '+' case, i.e. it is $x + t_1d_1$ which has an active constraint. By assumption, $x + t_1d_1$ is not an extreme point, and so therefore there exists $d_2\in\mathbb{R}^n$ which is not in $\text{span}(d_1)$ such that $(x + t_1d_1) \pm td_2\in P$ for $t\in (-\varepsilon_2, \varepsilon_2)$ for sufficiently small $\varepsilon_2$. Either $P$ contains the line $(x + t_1d_1) + td_2$ in which case we are done, or there exists $t = t_2$ such that $(x + t_1d_1) \pm t_2d_2$ which has an active constraint. Again WLOG assume the '+' case. Since $d_2$ is not in $\text{span}(d_1)$ then the active constraint from before is still active, and now a new constraint is active too. We iterate this process, so that we find a $d_3\in\mathbb{R}^n$ not in $\text{span}(d_1, d_2)$ such that $(x + t_1d_1 + t_2d_2) \pm td_3$ is contained in $P$ for small $t$ and either this is a line in $P$ or there is $t_3$ such that $x + t_1d_1 + t_2d_2 + t_3d_3$ has an active constraint. Since $d_3\notin\text{span}(d_1, d_2)$, the original two active constraints will still be active, and so there is now a third active constraint, etc. At some point we will have either found a line, or we will have $x + t_1d_1 + \cdots + t_nd_n$ which has $n$ active constraints. But then this should imply that the matrix of active constraints $A^=$ for this point is rank $n$, which would imply that $x + t_1d_1 + \cdots + t_nd_n$ is extreme, which contradicts the hypothesis. So therefore, at some iteration of this process we will necessarily have found a direction $d_i$ such that the line in that direction was contained in $P$.
My intuition tells me something like this should work, but I am struggling to make this rigorous. Specifically, I make the claim that each $d_i$ is not in the span of the preceding $d_1,\dots, d_{i - 1}$, but I don't know how to guarantee this is true. Second, I claim that since each $d_i$ is not in the span of the prior $d_1,\dots, d_{i - 1}$ then the constraints that were active before still remain active after traveling in direction $d_i$. This feels like it should be true, but I am not sure how to prove it. Finally, by my argument I should have at least $n$ active constraints if we end up iterating $n$ times, but I don't actually know how to prove that the rank of $A^=$ is actually equal to $n$ in this case (which gives us the desired contradiction if we have gotten to this stage). Maybe it is the case that $\text{rank}(A^=)$ is still strictly less than $n$, even though we have $n$ active constraints. I hope that this is impossible, but I am not sure how to prove it.
If someone could help make these points rigorous so that this becomes a valid proof, or instead shows why this proof cannot work, I would be very appreciative.
I'm fairly sure your proof can be made rigorous. At each stage of your procedure, let $\ A_j^=\ $ be the matrix of tight constraints and $\ A_j^<\ $ the matrix of slack constraints for $\ \displaystyle x_j=x+\sum_{i=1}^jt_id_i\ $. Because $\ x_j \ $ is not an extreme point, the rank of $\ A_j^=\ $ is less than $\ n\ $, so you can choose $\ d_{j+1}\ $ to lie in its kernel. Then all of the constraints with matrix $\ A_j^=\ $ will remain tight for $\ x_j+td_{j+1}\ $ (regardless of whether $\ d_{j+1}\in\text{span}\left(d_1,d_2,\dots,d_j\right)\ $ or not). If $\ x_j+td_{j+1}\ $ is not a line, then one or more of the constraints with matrix $\ A_j^<\ $ must be tight for $\ x_{j+1}=x_j+t_{j+1}d_{j+1}\ $. Therefore $\ A_j^=\ $ must be a strict submatrix of $\ A_{j+1}^=\ $. Since $\ A\ $ has only a finite number of rows, your procedure must terminate either with a line $\ x_k+td_{k+1}\ $ for some $\ k\ $, or with $\ A_k^==A\ $, and hence $\ Ax_k=b\ $. In the latter case, since $\ x_k\ $ is not an extreme point, then the rank of $\ A\ $ must be less than $\ n\ $ and hence have a non-empty kernel. If $\ d\ $ is any non-zero member of the kernel, then $\ x_k+td\ $ will be a line in $\ P\ $.