spark of a matrix

Let $𝔽$ be a field, and let $m,n\in \mathbb{N}\setminus \{0\}.$ Consider an $m\times n$ matrix $A$ whose entries belong to $𝔽.$ Let $C_1,\mathrm{\dots },C_n\in {𝔽}^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

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)$\mathrm{spark}\mathit{}\mathrm{(}A\mathrm{)}\mathrm{\in }\mathrm{\{}\mathrm{1}\mathrm{,}\mathrm{\dots }\mathrm{,}n\mathrm{\}}\mathrm{\cup }\mathrm{\{}\mathrm{+}\mathrm{\infty }\mathrm{\}}\mathrm{,}$(ii)$\mathrm{spark}\mathit{}\mathrm{(}A\mathrm{)}\mathrm{=}\mathrm{+}\mathrm{\infty }\mathrm{\iff }\mathrm{rank}\mathit{}\mathrm{(}A\mathrm{)}\mathrm{=}n\mathrm{,}$(iii)$\mathrm{spark}\mathit{}\mathrm{(}A\mathrm{)}\mathrm{=}\mathrm{1}$ if and only if the matrix $A$ has a zero column,(iv)if $\mathrm{spark}\mathit{}\mathrm{(}A\mathrm{)}\mathrm{\ne }\mathrm{+}\mathrm{\infty }\mathrm{,}$ then $\mathrm{spark}\mathit{}\mathrm{(}A\mathrm{)}\mathrm{\le }\mathrm{rank}\mathit{}\mathrm{(}A\mathrm{)}\mathrm{+}\mathrm{1}\mathrm{.}$
Moreover, $\mathrm{spark}\mathit{}\mathrm{(}A\mathrm{)}$ coincides with the infimum of the set $\mathrm{\{}{\mathrm{\parallel }x\mathrm{\parallel }}_{\mathrm{0}}\mathrm{:}x\mathrm{\in }{\mathrm{F}}^n\mathrm{\setminus }\mathrm{\{}\mathrm{0}\mathrm{\}}\mathrm{,}A\mathit{}x\mathrm{=}\mathrm{0}\mathrm{\}}$, where ${\mathrm{\parallel }x\mathrm{\parallel }}_{\mathrm{0}}$ is the Hamming weight of $x$ and $\mathrm{0}$ stands for the appropriate zero vectors.