If there is a sparse solution then is the smallest l1 norm solution at least as sparse? Consider the linear equation $Ax=b$ where $A$ is a matrix and $b$ and $x$ are vectors. Suppose there exists a vector $x_S$ that solves this equation ($Ax_S=b$) and $x_S$ has $k$ entries of value $0$ (i.e., $x_S$ is a sparse solution). Now consider the solution $x_m$ that has smallest $\ell_1$ norm of all the solutions. Does $x_m$ have to have at least $k$ entries of value $0$?

I'm going to think of the solution spaces as lines (planes, hyperplanes) and write them that way. You can turn them back into non-square matrix equations easily, and square matrix equations by adding linearly redundant equations.
First, it is possible that there are sparse and non-sparse solutions with the same minimal $\ell_1$ norm: as a simple example $x+y=1$ has solutions $(\alpha,1-\alpha)$ with the same $\ell_1$ norm for all $\alpha\in[0,1]$
It's easy to see in 2-d that this is the only sort of counterexample: if a line crosses both axes then either one of the crossings has the minimal $\ell_1$ norm or they both do and so does everything on the segment between them.
In 3-d the answer is in the negative. Consider the line that passes through $(0,0,1)$ and $(1/4,1/4,0)$. The point $(1/4,1/4,0)$ is less sparse than $(0,0,1)$ but has a smaller $\ell_1$ norm.
