How to find linearly independent columns in a matrix 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!
 A: 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).
