For a general square matrix $A$, how do I find which columns are linearly dependent? When I say linear independent I mean not linearly dependent with any other column or any combination of other columns in the matrix.

For example:

\begin{matrix} 0 & -2 & 1 \\ 0 & -4 & 2 \\ 1 & -2 & 1 \end{matrix}

In this matrix we know that column 1 is linear independent and columns 2 and 3 are dependent.

I want something that always works, and I already have the SVD and QR decomposition implemented in Java and I hope one or both of them can help me solving this.

Thanks in advance!

  • $\begingroup$ Do not delete a question that has been answered, only to repost the very same question. $\endgroup$ – amWhy Apr 10 '14 at 17:10
  • 1
    $\begingroup$ It isn't the same question. My first question was poorly asked as you said. Your answer didn't answer this question, it simply solved the equation system. $\endgroup$ – Johan S Apr 10 '14 at 17:11
  • 1
    $\begingroup$ More importantly, @amWhy: how do I solve this? $\endgroup$ – Johan S Apr 10 '14 at 17:16
  • 1
    $\begingroup$ Sorry @amWhy but you said the question was ill-formed and others said so as well. I appreciate your efforts but as said your answer wasn't answering this question. $\endgroup$ – Johan S Apr 10 '14 at 17:36

Given $A\in\mathbb{R}^{m\times n}$, $m\geq n$, compute the (economy) QR factorisation. This gives $$ A = QR, \quad R\in\mathbb{R}^{n\times n}. $$ Now if $\mathrm{rank}(A)<n$, the upper triangular matrix $R$ has a staircase profile with some of the "steps" of the staircase over more than one column. Select column indices $j_1,\ldots,j_k$ such that if you remove these columns from $R$, you obtain a nonsingular upper triangular matrix (you can consider it as making each step of the staircase of length 1). The columns $j_1,\ldots,j_k$ can be expressed as linear combination of the remaining columns.

Example: The red columns indicate the columns which are linear combinations of the others.

$$ \begin{bmatrix} \times & \times & \color{red}\times & \times & \color{red}\times & \color{red}\times \\ 0 & \times & \color{red}\times & \times & \color{red}\times & \color{red}\times \\ 0 & 0 & \color{red}0 & \times & \color{red}\times & \color{red}\times \end{bmatrix} $$

Example: For the given matrix from the question, the QR factorisation is:

Q =

         0   -0.4472   -0.8944
         0   -0.8944    0.4472
   -1.0000         0         0

R =

   -1.0000    2.0000   -1.0000
         0    4.4721   -2.2361
         0         0         0

So one can pick the column 2 or 3 to make the matrix $R$ nonsingular and upper triangular (hence either the column 2 or 3 is a linear combination of the others).

  • $\begingroup$ I got my $R$ and $Q$, but I don't understand how I from that, find out which columns are linearly independent of the others? $\endgroup$ – Johan S Apr 10 '14 at 18:13
  • $\begingroup$ When you say "the others", is there any way to see which columns? When you say either column 2 or 3 is a linear combination of the others? $\endgroup$ – Johan S Apr 10 '14 at 18:23
  • $\begingroup$ Yes, column 2 is a linear combination of columns 1 and 3. Also, column 3 is a linear combination of columns 1 and 2. $\endgroup$ – Algebraic Pavel Apr 10 '14 at 18:45
  • $\begingroup$ if you swap column 1 and 2 in my question matrix $A$, how do I then find which are linear dependant? Thanks for the help so far by the way! I mean, I still don't fully understand, how do I from the $R$ matrix read out which are linearly independent? $\endgroup$ – Johan S Apr 10 '14 at 19:37
  • $\begingroup$ Same approach, delete columns of $R$ until it becomes nonsingular upper triangular. $\endgroup$ – Algebraic Pavel Apr 10 '14 at 22:45

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.