5
$\begingroup$

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!

$\endgroup$
4
  • $\begingroup$ Do not delete a question that has been answered, only to repost the very same question. $\endgroup$
    – amWhy
    Commented Apr 10, 2014 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
    Commented Apr 10, 2014 at 17:11
  • 1
    $\begingroup$ More importantly, @amWhy: how do I solve this? $\endgroup$
    – Johan S
    Commented Apr 10, 2014 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
    Commented Apr 10, 2014 at 17:36

1 Answer 1

6
$\begingroup$

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

$\endgroup$
6
  • $\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
    Commented Apr 10, 2014 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
    Commented Apr 10, 2014 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$ Commented Apr 10, 2014 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
    Commented Apr 10, 2014 at 19:37
  • $\begingroup$ Same approach, delete columns of $R$ until it becomes nonsingular upper triangular. $\endgroup$ Commented Apr 10, 2014 at 22:45

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .