 Solution

Choose an optimal feasible vector $x$ having as few positive coordinates as possible, and letIf the columns $(A_i{)}_{i\in S}$ were linearly dependent, there would be a nonzero vector $h$, supported on $S$, such that $Ah=0$. For all sufficiently small positive $\epsilon$, bothwould remain feasible.

If $c^{T}h\ne 0$, one of these two perturbations would increase the objective, contradicting optimality. Hence $c^{T}h=0$. We may then increase $\epsilon$ in one of the two directions until at least one positive coordinate first becomes zero. The resulting vector is still feasible and optimal but has smaller positive support, contradicting the choice of $x$.