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?

  • $\begingroup$ I think you want an algorithm, not a function. $\endgroup$ – Riquelme Aug 31 '19 at 21:05
  • $\begingroup$ @Riquelme Correct. I meant a programming function and not a mathematical function, I'm used to computer science references. $\endgroup$ – Tomergt45 Aug 31 '19 at 21:09
  • $\begingroup$ 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. $\endgroup$ – NoChance Aug 31 '19 at 21:46
  • $\begingroup$ 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. $\endgroup$ – 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}$.


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.