0
$\begingroup$

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]]] ]
$\endgroup$
3
  • 1
    $\begingroup$ But ... do you understand the "recipe"? $\endgroup$ Oct 30, 2014 at 1:46
  • $\begingroup$ 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 $\endgroup$
    – lurscher
    Oct 30, 2014 at 6:23
  • $\begingroup$ You may read mathematica.stackexchange.com/a/25616/193 and then all the answers in that question $\endgroup$ Oct 30, 2014 at 12:46

2 Answers 2

3
$\begingroup$

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

which gives you the answer.

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

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

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}}
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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