# Finding maximal sublist of linearly independent vectors

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.

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

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}}

• FWIW, RowReduce@Transpose@m may be used in place of Last@QRDecomposition@Transpose@m and is considerably faster. Nov 5, 2016 at 20:44
• Is this solution expected to work for "floats"? Jul 9, 2022 at 4:12

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