# Submatrix with linearly independent columns

What I want is the submatrix where all the linearly dependent rows have been eliminated.

I tried implementing this solution, but it doesn't work in the following example:

mm = SparseArray[{{1, 3} ->
0.3828286316736664, {2, 1} -> -1., {2, 3} ->
0.9238193756199684, {3, 2} -> -0.3828286316736664, {4, 2} ->
0.9238193756199684, {5, 3} -> -0.3828286316736664, {6,
3} -> -0.9238193756199684, {7, 4} ->
0.0679619061399982, {7, 5} ->
0.30155693875441497, {8, 4} -> -0.9976879167925299, {8, 5} ->
0.9534481699017866, {9, 4} -> -0.0679619061399982, {9, 8} ->
0.4709417025109601, {10, 4} ->
0.9976879167925299, {10, 8} -> -0.8821643343709143, {11,
5} -> -0.30155693875441497, {_, _} -> 0}, {11, 10}]

MatrixRank[mm]


the matrix rank is 6. We now run the recipe in the other answer, but I get the new matrix to have rank 1:

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

• But ... do you understand the "recipe"? – Dr. belisarius Oct 30 '14 at 1:46
• not much. Flatten removes one level of depth, but I don't understand what the prefix operator is doing with all those linear operators. The prefix operator help doesn't have any examples to speak of – lurscher Oct 30 '14 at 6:23
• You may read mathematica.stackexchange.com/a/25616/193 and then all the answers in that question – Dr. belisarius Oct 30 '14 at 12:46

I would approach this specific straightforward example in a straightforward way.

Eliminate your matrix using RowReduce[mm];

red=RowReduce[mm]];
red//MatrixForm


$\begin{pmatrix} 1 & 0.&0.&0.&0.&0.&0.&0.&0.&0.&\\ 0 & 1 &0.&0.&0.&0.&0.&0.&0.&0.&\\ 0 & 0 &1 &0.&0.&0.&0.&0.&0.&0.&\\ 0 & 0 &0 &1&0.&0.&0.&0.&0.&0.&\\ 0 & 0&0&0&1&0.&0.&0.&0.&0.&\\ 0 & 0&0&0&0&0&0&1 &0.&0.&\\ 0 & 0&0&0&0&0&0&0&0&0&\\ 0 & 0&0&0&0&0&0&0&0&0&\\ 0 & 0&0&0&0&0&0&0&0&0&\\ 0 & 0&0&0&0&0&0&0&0&0&\\ 0 & 0&0&0&0&0&0&0&0&0&\\ \end{pmatrix}$

Now this is sufficiently easy as it leaves us with a very simple selection. The columns in red with a "1" identify the column vectors in mm that form the independent vector set.

Select the column vectors from mm with:

vectoridx = Flatten@Position[Round@Total@RowReduce[mm], 1]

(* {1, 2, 3, 4, 5, 8} *)

mm[[All,vectoridx]]


Now I will take a slightly more comprehensive approach to illustrate how the method you tried to use works:

vectorstokeep = Length@vectoridx;


This chops off the zero vectors from the selection below:

mm.Transpose[RowReduce[mm]][[All, 1 ;; vectorstokeep]]


The difference with what you are trying is that the QRDecompositon is used instead of RowReduce to make the selection of the positions more generic (which in your case you do not need).

If you want to understand this method, break it up in three pieces:

red = Last@QRDecomposition@Transpose@mm


provides the QR reduction (more generic);

pos = Position[#, Except[0., _?NumericQ], 1, 1] & /@ red


provides the relevant columns to select. Except[0., _?NumericQ] identifies non-zero numbers and Position[#, Except[0., _?NumericQ], 1, 1] gives the position of these non-zero numbers in the matrix. The 1,1 at the end of Position signifies the level specification and the fact that only the first found number is returned respectively.

 mm[[Flatten[pos]]]


selects these columns.

Please note in Except[0, _?NumericQ] I replaced NumericalQ with NumericQ and 0 with 0..

• oh I see, the "prefix" operator is actually a functional composition operator. Doh! – lurscher Oct 30 '14 at 20:10
• so is it working for you now? – Sander Nov 3 '14 at 3:04

Straightforward way to select linearly independent rows is to compute MatrixRank[] of 1 row, 2 rows, 3 rows and so on. After that, choose positions from the list of ranks, where rank is changed.

LinIndependentRows[A_List] :=
Module[{ranks},
ranks = MatrixRank[A[[1 ;; #]]] & /@ Range[Length@A];
FirstPosition[ranks, #] & /@ Range[MatrixRank@A]];

A = {{0, 1, -1, 0, 0}, {1, 0, 1, 0, -1}, {1, 1, 1, -1, -1},
{-1, -1, -1, 1, 0}, {-1, -1, -1, 1, 1}, {1, 0, 1, 0, 0},
{0, -1, 0, -1, -1}};
pos = LinIndependentRows[A]

{{1}, {2}, {3}, {4}, {7}}


This gives the list of positions of linearly independent rows. Then just choose corresponding rows from matrix A.

A[[Flatten@pos, All]]

{{0, 1, -1, 0, 0}, {1, 0, 1, 0, -1}, {1, 1, 1, -1, -1},
{-1, -1, -1, 1, 0}, {0, -1, 0, -1, -1}}