In mathematics, more specifically in linear algebra, the spark of a m × n {\displaystyle m\times n} matrix A {\displaystyle A} is the smallest integer k {\displaystyle k} such that there exists a set of k {\displaystyle k} columns in A {\displaystyle A} which are linearly dependent. If all the columns are linearly independent, s p a r k ( A ) {\displaystyle \mathrm {spark} (A)} is usually defined to be 1 more than the number of rows. The concept of matrix spark finds applications in error-correction codes, compressive sensing, and matroid theory, and provides a simple criterion for maximal sparsity of solutions to a system of linear equations. The spark of a matrix is NP-hard to compute.
Definition Formally, the spark of a matrix A {\displaystyle A} is defined as follows:
where d {\displaystyle d} is a nonzero vector and ‖ d ‖ 0 {\displaystyle \|d\|_{0}} denotes its number of nonzero coefficients ( ‖ d ‖ 0 {\displaystyle \|d\|_{0}} is also referred to as the size of the support of a vector). Equivalently, the spark of a matrix A {\displaystyle A} is the size of its smallest circuit C {\displaystyle C} (a subset of column indices such that A C x = 0 {\displaystyle A_{C}x=0} has a nonzero solution, but every subset of it does not). If all the columns are linearly independent, s p a r k ( A ) {\displaystyle \mathrm {spark} (A)} is usually defined to be m + 1 {\displaystyle m+1} (if A {\displaystyle A} has m rows). By contrast, the rank of a matrix is the largest number k {\displaystyle k} such that some set of k {\displaystyle k} columns of A {\displaystyle A} is linearly independent.
Example Consider the following matrix A {\displaystyle A} .
A = [ 1 2 0 1 1 2 0 2 1 2 0 3 1 0 − 3 4 ] {\displaystyle A={\begin{bmatrix}1&2&0&1\\1&2&0&2\\1&2&0&3\\1&0&-3&4\end{bmatrix}}}
The spark of this matrix equals 3 because:
… excerpt ends here. Continue reading the full article.
