1 Answers
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 {\displaystyle \mathrm {spark} } 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.