The Dependency Algorithm

The dependency algorithm is a very useful method for figuring out the dependence relations for a given set of vectors in Rn.

Given vectors v1, v2, ..., vk in Rn:

Stack them together as the columns of a matrix and reduce the matrix to reduced row echelon form.

Find the columns of the reduced matrix which have leading 1's. Then the corresponding columns of the original matrix are linearly independent.

Every other vector of the original set is a linear combination of these independent vectors. The coefficients of that linear combination are the numbers in the corresponding column of the reduced matrix.

Here's an example. Suppose you are given five vectors in R4:

v1 = (–1, 1, 2, 5),

v2 = (3, –2, 0, 1),

v3 = (–5, 4, 4, 9),

v4 = (4, 0, –3, 2),

v5 = (18, –7, –8, 2).

Stack them into the columns of a matrix:

Reduce the matrix to reduced row-echelon form:

Then:

v1, v2 and v4 are linearly independent
v3 = 2v1 – v2
v5 = –v1 + 3v2 + 2v4.

(Notice that you may get a different choice of independent vectors if you arrange the V's in a different order. The algorithm "chooses" independent vectors from the set starting with the left-most vector and adding vectors to its right, as long as they're not linearly dependent on the ones already chosen.)

Why the dependency algorithm works. Suppose we have vectors v1, v2, ..., vk in Rn. To determine if they are linearly independent or not, we look for the solutions c1, c2, ..., ck of the linear dependence equation

c1v1 + c2v2 + ... + ckvk = 0 .

Think of the vectors v1, v2, ..., vk as column matrices; then the left-hand side of this relation is a linear combination of columns. Write it in contracted form:

.

This is a linear system in c1, c2, ..., ck. To find c1, c2, ..., ck, we look at its augmented matrix

and reduce it to reduced row-echelon form

.

Now work in the other direction: the linear system with this augmented matrix is

.

If we write the left-hand side in expanded form, we get

c1r1 + c2r2 + ... + ckrk = 0.

Let's summarize here before going further. The two main points:

The matrix with columns r1, r2, ..., rk is the reduced row-echelon form of the matrix with columns v1, v2, ..., vk. (We actually reduced the augmented matrix, but the column of constants had just zeroes, and didn't affect the row reduction.)
Solving a linear system by row reduction doesn't change its solutions, so any c1, c2, ..., ck which are a solution of c1v1 + c2v2 + ... + ckvk = 0 are a solution of c1r1 + c2r2 + ... + ckrk = 0 and vice versa.

Now:

The columns of the reduced matrix with leading 1's are elementary columns, and so are linearly independent – there is no non-trivial solution of c1r1 + c2r2 + ... + ckrk = 0 involving only these columns (i.e. with the other coefficients zero). Then there is no non-trivial solution of c1v1 + c2v2 + ... + ckvk = 0 involving only the corresponding columns of the original matrix, so those columns must be linearly independent.

Every column of the reduced matrix not containing a leading 1 can be written as a linear combination of the elementary columns which precede it using the numbers in that column as coefficients. The relation that expresses it as a linear combination of those elementary columns is a solution of c1r1 + c2r2 + ... + ckrk = 0, which thus translates back into the same relation between the corresponding columns of the original matrix.