How to check if m n-sized vectors are linearly ind

Question

Disclaimer
This is not strictly a programming question, but most programmers soon or later have to deal with math (especially algebra), so I think that the answer could turn out to be useful to someone else in the future.

Now the problem
I'm trying to check if m vectors of dimension n are linearly independent. If m == n you can just build a matrix using the vectors and check if the determinant is != 0. But what if m < n?

Any hints?

---

See also this video lecture.

Answer 1

A very simple way, that is not the most computationally efficient, is to simply remove random rows until m=n and then apply the determinant trick.

• m < n: remove rows (make the vectors shorter) until the matrix is square, and then
• m = n: check if the determinant is 0 (as you said)
• m < n (the number of vectors is greater than their length): they are linearly dependent (always).

The reason, in short, is that any solution to the system of m x n equations is also a solution to the n x n system of equations (you're trying to solve Av=0). For a better explanation, see Wikipedia, which explains it better than I can.

Answer 2

Another way to check that m row vectors are linearly independent, when put in a matrix M of size mxn, is to compute

det(M * M^T)

i.e. the determinant of a mxm square matrix. It will be zero if and only if M has some dependent rows. However Gaussian elimination should be in general faster.