Vertices of a convex set

Question

Let $C$ be a convex set in $\mathbb{R}^{n}$ defined by the system of inequalities $Ax\leq b$, where $x\in\mathbb{R}^{n}$ and $b\in\mathbb{R}^{m}$, with $m>n$. My question is the following: a vertex of $C$ is a point in $C$ solving a system of $n$ linearly independent equations $\sum_j a_{ij}x_{j}=b_{i}$?

Answer 1

Yes!

First, let $x\in C$ solve a linear system $A_Ix\leq b_I$ ($I\subseteq [m]$, $|I|=n$), rows of $A_I$ linearly independent i.e. $A_I$ invertible. If we can express $x$ as a strict convex combination of any two elements $y,z\in C$, i.e. $x=\lambda y+(1-\lambda)z, \lambda\in(0,1)$, then $$b_I=A_Ix=\lambda A_Iy+(1-\lambda)A_Iz$$ and as $A_Iy\leq b_I, A_Iz\leq b_I$ ($y,z\in C$), we have $A_Iy=b_I, A_Iz=b_I$. If $A_I$ was invertible, we know that $x=y=z$. Therefore $x$ is a vertex$.

For the other direction, let $x\in C$ be a vertex. Obviously $x$ must lie in the boundary of $C$, so it lies in at least one supporting hyperplane, i.e. $\sum_j a_{ji}x_j=b_i$ for at least one $i\in[m]$. Let $I\subseteq[m]$ be all indices such that $\sum_j a_{ji}x_j=b_i$ holds, so $A_Ix=b_I$ and with $J=[m]\setminus I$, $A_Jx<b_J$.

Assume for contradiction that $A_I$ is not invertible. Then there exists a $u\in\mathbb{R}^n, u\neq 0$ such that $A_I(x+\mu u)=A_Ix+\mu A_Iu=b_I$. As $A_Jx<b_J$, we can find $\mu>0$ sufficiently small enough such that $A_J(x+\mu u)\leq b_J$ and $A_J(x-\mu u)\leq b_J$, yielding $y=x+\mu u,z=x-\mu u \in C$ with $x=\frac{1}{2}(y+z)$, contradicting that $x$ is a vertex.