= Solution
Combine all inequalities, including nonnegativity, into $Cx\leq d$; explicitly, the rows $-e_j^Tx\leq0$ encode $x_j\geq0$. Let $x_*$ be a <vertex of a linear polyhedron>, equivalently an <extreme point> of the feasible <linear polyhedron>, and let $I$ index the <active constraints> there.
Suppose the active row normals have <rank> smaller than $n$. By the <rank-nullity theorem> there is a nonzero <vector> $h$ with $C_ih=0$ for every $i\in I$. Every inactive row has positive <slack variable> value $s_i=d_i-C_ix_*>0$. Since there are only finitely many rows, choose $\varepsilon>0$ so small that
$$
\varepsilon|C_ih|<s_i\qquad\text{for every inactive row with }C_ih\ne0.
$$
Then both $x_*+\varepsilon h$ and $x_*-\varepsilon h$ are <feasible points>: the <active constraints> remain equalities and no inactive inequality is violated. They are distinct, and $x_*$ is their <midpoint>, contradicting the <extreme point> property.
Therefore the active row normals have <rank> $n$, and \b[at least $n$ <linearly independent> constraints are satisfied with equality]. In particular at least $n$ constraints are tight, as claimed. Nonnegativity bounds must be counted: for example, at the origin these can supply all $n$ active rows. Degeneracy can make more than $n$ constraints tight, so the result does not assert exactly $n$.
Back to article page
