11
$\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$
4
  • $\begingroup$ Check RowReduce...this will reduce matrix to basis. $\endgroup$ Oct 16, 2013 at 17:30
  • $\begingroup$ I tried RowReduce, but that doesn't output a sublist of the original list. $\endgroup$ Oct 16, 2013 at 17:32
  • $\begingroup$ you need to implement these steps..math.stackexchange.com/questions/164016/… $\endgroup$ Oct 16, 2013 at 17:39
  • $\begingroup$ did u get time to check if any of these solution is working ? $\endgroup$ Oct 31, 2013 at 9:55

2 Answers 2

14
$\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
  • 5
    $\begingroup$ FWIW, RowReduce@Transpose@m may be used in place of Last@QRDecomposition@Transpose@m and is considerably faster. $\endgroup$
    – Michael E2
    Nov 5, 2016 at 20:44
  • $\begingroup$ Is this solution expected to work for "floats"? $\endgroup$
    – David
    Jul 9, 2022 at 4:12
2
$\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 and acknowledge you have read our privacy policy.

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