no $k$-sparse vector in null space of $A$ where $y=Ax$ Here is a part of my notes on compressed sensing. Suppose we are given an underdetermined linear system of equations $Y=AX$. For a unique solution,
What we need: 

subtraction of no two $k$-sparse vectors ($x_1$, $x_2$) must be in nullspace of $A$.

What is required for the following to hold:

since the subtraction of two $k$-sparse vectors is at most
  $2k$-sparse, $2k$ columns of the matrix must be linearly independent
  then no $k$-sparse vector will be in null space of $A$.

I don't understand the part where a connection between sparsity and the columns of the matrix being linearly independent is made. An explanation would be great. 

I presume the formulation should be that every 2k columns of $A$ should be linearly independent, as this implies that there are no 2k sparse vector in the null space:
To see this, denote $(\vec{a}_1,...,\vec{a}_N)$ the column vectors of $A$ and let $X$ be a 2k-sparse vector, i.e. there are at most $2k$ nonvanishing components of $X$. This means that there is a set of at most 2k indices $i_1,\ldots,i_m$, with $m\leq 2k$ so that every component of $X$ outside this set vanishes. 
In order for $X$ to be in the kernel of $A$ we must have:
$$ AX = \sum_{j=1}^m \vec{a}_{i_j} x_{i_j}=0 $$
But as every collecting of at most $2k$ vectors of $A$ are assumed linearly independent we must have every $x_{i_1}=...=x_{i_m}=0$. So every component of $X$ vanishes and $X$ was the zero vector.
