7
$\begingroup$

Given a list of vectors v = {v1, ..., vn}, which is the fastest way to find a maximal sublist of linearly independent vectors? I could add the vectors one by one to a list and check for the rank of the resulting matrix, but I would like to know if there's a better solution.

Thanks in advance.

$\endgroup$
  • $\begingroup$ Check RowReduce...this will reduce matrix to basis. $\endgroup$ – Rorschach Oct 16 '13 at 17:30
  • $\begingroup$ I tried RowReduce, but that doesn't output a sublist of the original list. $\endgroup$ – Oliver Miller Oct 16 '13 at 17:32
  • $\begingroup$ you need to implement these steps..math.stackexchange.com/questions/164016/… $\endgroup$ – Rorschach Oct 16 '13 at 17:39
  • $\begingroup$ did u get time to check if any of these solution is working ? $\endgroup$ – Rorschach Oct 31 '13 at 9:55
13
$\begingroup$
MatrixRank[m =
{{1, 2, 0, -3, 1, 0},
 {1, 2, 2, -3, 1, 2},
 {1, 2, 1, -3, 1, 1},
 {3, 6, 1, -9, 4, 3}}]

3

m[[ Flatten[ Position[#, Except[0, _?NumericQ], 1, 1]& /@
    Last @ QRDecomposition @ Transpose @ m ] ]]

{{1, 2, 0, -3, 1, 0},
{1, 2, 2, -3, 1, 2},
{3, 6, 1, -9, 4, 3}}

$\endgroup$
  • 2
    $\begingroup$ FWIW, RowReduce@Transpose@m may be used in place of Last@QRDecomposition@Transpose@m and is considerably faster. $\endgroup$ – Michael E2 Nov 5 '16 at 20:44
1
$\begingroup$

Taking http://www.math4all.in/public_html/linear%20algebra/chapter3.3.html as reference I have tried to do it, I have tried to follow the steps that I suggested you,

   MinimalSublist[x_List] := 
 Module[{tm, ntm, ytm, mm = x}, {tm = RowReduce[mm] // Transpose, 
   ntm = MapIndexed[{#1, #2, Total[#1]} &, tm, {1}], 
   ytm = Cases[ntm, {___, ___, d_ /; d == 1}]};
  Cases[ytm, {b_, {a_}, c_} :> mm[[All, a]]] // Transpose]

For

m1 = {{1, 2, 0, -3, 1, 0}, {1, 2, 1, -3, 1, 2}, {1, 2, 0, -3, 2, 
    1}, {3, 6, 1, -9, 4, 3}};
MinimalSublist[m1]

{{1, 0, 1}, {1, 1, 1}, {1, 0, 2}, {3, 1, 4}}

In M you see 1 row and n columns together,so you can transpose it to see it as {{1, 1, 1, 3}, {0, 1, 0, 1}, {1, 1, 2, 4}} column specific data.

Their count is always equal to rank of a matrix which you can check with MatrixRank[m1] as 3. To verify this result use this applet link, http://www.math4all.in/public_html/linear%20algebra/example3.7/index.html

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.