# spark of a matrix

Let $\mathbb{F}$ be a field, and let $m,n\in\mathbb{N}\setminus\{0\}.$ Consider an $m\times n$ matrix $A$ whose entries belong to $\mathbb{F}.$ Let $\displaystyle C_{1},\ldots,C_{n}\in\mathbb{F}^{m}$ be the columns of $A.$

###### Definition 1

The spark of the matrix $A$ is defined to be the infimum of the set of all positive integers $k$ with the property that

 $\exists\,j_{1},\ldots,j_{k}\in\{1,\ldots,n\}:\,\left\{\begin{array}[]{l}j_{1}<% \ldots

The notion of spark of a matrix was introduced by Donoho and Elad in [1]. It is strictly related to Compressed Sensing. The word “spark” comes from a verbal fusion of “sparse” and “rank”.

###### Remark 2

The following properties hold true:
(i) ${\rm spark}(A)\in\{1,\ldots,n\}\cup\{+\infty\},$ (ii) ${\rm spark}(A)=+\infty\,\Leftrightarrow\,{\rm rank}(A)=n,$ (iii) ${\rm spark}(A)=1$ if and only if the matrix $A$ has a zero column, (iv) if ${\rm spark}(A)\neq+\infty,$ then ${\rm spark}(A)\leq{\rm rank}(A)+1.$
Moreover, ${\rm spark}(A)$ coincides with the infimum of the set $\displaystyle\left\{\left\|x\right\|_{0}:\,x\in\mathbb{F}^{n}\setminus\{{\bf 0% }\},\,Ax={\bf 0}\right\}$, where $\displaystyle\left\|x\right\|_{0}$ is the Hamming weight of $x$ and ${\bf 0}$ stands for the appropriate zero vectors.

## References

• 1 D. L. Donoho and M. Elad, Optimally sparse representation in general (nonorthogonal) dictionaries via $\ell^{1}$ minimization, Proc. Natl. Acad. Sci. USA 100, No. 5: 2197 – 2202 (2003).
Title spark of a matrix SparkOfAMatrix 2013-03-22 19:36:23 2013-03-22 19:36:23 kammerer (26336) kammerer (26336) 21 kammerer (26336) Definition msc 15A03 RankOfAMatrix