There exists a solution with at most $m$ nonzero elements. $x \in \mathbb{R}^n$, $A \in \mathbb{R}^{m \times n}$ and $$Ax=b, x \geq 0$$ has a nonempty solution set.
Prove that there exists a solution with at most $m$ nonzero elements.
 A: If $n\le m$, there is nothing to show. Let $n > m$, say, $n=m+k$. Then we have to find a solution with $k$ zero entries. By the rank-nullity formula,
$$
n = \dim\ker A + \dim\operatorname{im}A\le \dim\ker A + m,
$$
hence $\dim\ker A\ge k$. So, we find a linearly independent set $\{x_1,\ldots,x_k\}$ in $\ker A$. The matrix $X = [x_1,\ldots,x_k]\in\mathbb R^{n\times k}$ thus has (row-)rank $k$. Hence, we can pick $k$ rows of $X$ with indices $r_1,\ldots,r_k$ which are linearly independent. Let $X'\in\mathbb R^{k\times k}$ be the matrix with these rows.
Let $x_0$ be a solution of $Ax=b$ and let $x_0'\in\mathbb R^k$ be the extraction from $x_0$ with entries $r_1,\ldots,r_k$. Then the system $X'u = -x_0'$ has a solution $u\in\mathbb R^k$.
Let $\pi$ be a permutation such that $\pi(r_j) = j$ and let $P$ be the corresponding permutation matrix. Clearly,
$$
x = x_0 + u_1x_1 + \ldots + u_kx_k = x_0 + Xu
$$
is a solution of $Ax=b$ and
$$
Px = Px_0 + PXu = \binom{x_0'}{*} + \binom{X'u}{*} = \binom{0}{*}
$$
has $k$ zero entries. Hence so does $x$.
