4
$\begingroup$

Does the minimum number of dependent rows in a matrix have a specific name? (the way "rank" refers to the maximum number of independent rows). This comes up in calculating distances of codes. There are plenty of algorithms to calculate rank; are there any for this minimum other than brute force? Any reference to or description of the algorithm are appreciated; same for any sw package that might have that implemented.

$\endgroup$
4
  • $\begingroup$ Have you heard of null-space? $\endgroup$
    – polfosol
    Commented Jun 14, 2016 at 6:59
  • 2
    $\begingroup$ I don't see the relevance of nullspace here. If rows 1, 2, 3 are dependent, and rows 4, 5, 6, 7 are dependent, how does the nullspace direct you to rows 1, 2, 3 as the answer OP wants? $\endgroup$ Commented Jun 14, 2016 at 7:29
  • 2
    $\begingroup$ It is known (due to Alex Vardy et al IIRC) that the problem of determining whether a given linear code has non-zero words of weight below a given value is in one of those nasty NP-categories (NP-hard?). As finding a check matrix for a given linear code is straightforward, we can safely assume that no such algorithm with polynomial complexity is known. $\endgroup$ Commented Jun 14, 2016 at 10:17
  • $\begingroup$ I suspected that in spite of its somewhat similar definition to rank, the "minimal linearly dependent set" (using the terminology of the link given in the answer below) is much harder to calculate. $\endgroup$
    – unknown
    Commented Jun 14, 2016 at 16:12

2 Answers 2

3
$\begingroup$

Let $\phi: V \rightarrow W$ be a linear transformation and let $M$ be the matrix corresponding to $\phi$ using the bases $B$ and $B'$ for $V$ and $W$, respectively. In the following paper, a method for determining the dimension $d$ of the Kernel of $\phi$ is presented by looking at $M$. Their idea for determining $d$ is to count the number of linearly dependent row vectors in $M$. http://www.math.uchicago.edu/~may/VIGRE/VIGRE2008/REUPapers/Klein.pdf

Also, the following page of MATLAB Central can be helpful: http://www.mathworks.com/matlabcentral/newsreader/view_thread/157533?requestedDomain=www.mathworks.com

$\endgroup$
3
  • $\begingroup$ You do realize that the question was not about calculating the dimension of the kernel but rather locating the vector with the lowest number of non-zero coordinates (w.r.t. the given base). $\endgroup$ Commented Jun 14, 2016 at 10:20
  • 1
    $\begingroup$ @JyrkiLahtonen: You are right, but I mentioned this reference because of the question "Does the minimum number of dependent rows in a matrix have a specific name?" $\endgroup$ Commented Jun 14, 2016 at 10:39
  • $\begingroup$ Thanks for clarifying. Sorry about jumping on the case. $\endgroup$ Commented Jun 14, 2016 at 10:49
3
$\begingroup$

Spark of a matrix. Spark condition is used in the compressed sensing theory. It is a merge of the words sparse and rank.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .