# Remove linearly dependent vectors from a matrix

This may be a redundant question because I'm still studying this field. I'm attempting to write an algorithm that removes linearly dependent vectors from a matrix in a simple way.

First approach was to rewrite the definition $$c_1v_1 + \cdots + c_nv_n = 0$$ as

$$\begin{pmatrix} v_1 \\ \vdots \\ v_n \end{pmatrix} \begin{pmatrix} c_1 & \cdots & c_n \end{pmatrix} = 0$$

and solve for the constants, not sure if this is an optimal or even correct approach but I can't seem to reach some identification of a linearly dependent vector.

how can one approach this correctly?

• I think you want an algorithm, not a function. – Riquelme Aug 31 '19 at 21:05
• @Riquelme Correct. I meant a programming function and not a mathematical function, I'm used to computer science references. – Tomergt45 Aug 31 '19 at 21:09
• The method you meant is valid see: math.oregonstate.edu/home/programs/undergrad/…. Another approach if dividing each row by each other row and each column by each column yield save value respectively. The later is easier to program. – NoChance Aug 31 '19 at 21:46
• The QR decomposition mentioned in an answer below is probably the most computationally-efficient method, but you can also do this with good old Gaussian elimination or the Gram-Schmidt process. – amd Aug 31 '19 at 22:01

You can do QR decomposition programmatically (e.g., using numpy.linalg.qr), then every $$v_i$$ corresponding zero diagonal component of $$R$$ are what you're supposed to remove!
That is, once you get the upper triangular matrix, $$R$$, every $$v_i$$ for which $$R_{ii}=0$$ is the vector linearly dependent on $$v_1, \ldots, v_{i-1}$$.