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 estimate
$$
\max\{\|u\|\_0,\|v\|\_0\}\leq d-s,
$$
where, as usual, 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}$.



How sparse can a matrix mapping between sparse vectors be?
$||v||\_0$, so $\leq d-s$: The matrix $A$ needs to have at least one entry for every entry of $v$ (otherwise it can't obtain that entry). It is also sufficient to have so many entries, as if we consider one $j$ with $u\_j \not= 0$ (which exists otherwise the system has a solution (the zero matrix) only if $v\_i = 0$ for all $i$) then we can set for every entry $v\_i \not= 0$ the matrix entry $A\_{i,j} = \frac{v\_i}{u\_j}$.


