For a matrix $M$ of rank $N\times N$, the number of non-zero elements should scale $\sim N$ or, at most, $\sim N \log(N)$ for $M$ to be sparse, otherwise most sparse matrix algorithms are of rather little help. (You can surely refine this statement for $N\times M$ matrices with $N\neq M$ ...)