Let $s$ and $d$ be non-negative integers with $0\leq s<d$ and let $v,u\in \mathbb{R}^d$ be vectors satisfying the sparsity lower-bound
$$
d-s \leq \min\{\|u\|_0,\|v\|_0\},
$$
where, as ususal, for any vector $x \in \mathbb{R}^d$ we define $\|x\|_0:=\sum_{i=1}^d\,I_{x_i\neq 0}$.   

Let $A$ be an $d\times d$-matrix solving $Au=v$.   How sparse can $A$ be?  I.e.: what is
$$
\inf_{A\in L(\mathbb{R}^d),\,Au=v}\, \|A\|_0,
$$
where as above $\|A\|_0:=\sum_{i,j=1}^d\,I_{A_{i,j}\neq 0}$.