= Vertex of a linear polyhedron
{title2=$\operatorname{rank}A_{I(p)}=n$}
= Vertices of a linear polyhedron
{synonym}
For a <linear polyhedron> $P=\{x\in\mathbb R^n:Ax\leq b\}$, a <vertex of a linear polyhedron> is a <feasible point> $p$ at which the normals of the <active constraints> span $\mathbb R^n$. Equivalently, $n$ <linearly independent> <active constraints> uniquely determine $p$. A <linear polyhedron> may be unbounded or lower-dimensional; the definition applies in those cases as well as to a <convex polytope>.
Such a <point> is an <extreme point>. Indeed, if $p=\lambda u+(1-\lambda)v$ with $u,v\in P$ and $0<\lambda<1$, every <active constraint> at $p$ must also be an equality at $u$ and $v$. Selecting $n$ independent active rows forces $u=v=p$. Conversely, if the active normals do not span $\mathbb R^n$, take a nonzero <vector> $h$ annihilated by all active rows. The finitely many inactive inequalities have positive slack, so both $p+\varepsilon h$ and $p-\varepsilon h$ remain feasible for sufficiently small $\varepsilon>0$. Their <midpoint> is $p$, so $p$ is not an <extreme point>. Thus these notions coincide for a <linear polyhedron>.
Back to article page
