The column space of a matrix

The column space of an m x n matrix is the subspace of Rm spanned by the columns of the matrix.

An m x n matrix has n columns, but they are usually linearly dependent. To find a basis of the column space, you could transpose the matrix and then find a basis of the row space of the transpose. You can also use the dependency algorithm on the columns – the columns are already conveniently stacked into a matrix, so you just need to row reduce the matrix and use the result to pick out the independent columns of the original matrix. Either method will give you a basis of the column space; the dependency algorithm selects a basis from the original matrix columns.

To find a basis of the column space of a matrix

Reduce the matrix to reduced row-echelon form.

Use the dependency algorithm to pick out a set of linearly independent columns of the original matrix.

This algorithm also gives you the dimension of the column space.

The dimension of the column space of a matrix is the number of leading 1's in its reduced row-echelon form.

Proof. The dependency algorithm picks out a basis of the column space consisting of those columns of the original matrix corresponding to the columns of the reduced matrix with leading 1's. The number of those columns is thus the dimension of the column space.

The column space of A is intimately related to the consistency of linear systems of the form Ax = b.

The linear system Ax = b is consistent if and only if b is in the column space of A.

Proof. Suppose the matrix A has columns a1, a2, ..., an and suppose x is the column [x1, x2, ..., xn]. The left-hand side of Ax = b can be expanded into a linear combination of the columns of A:

x1a1 + x2a2 + ... + xnan = b.

This equation says that b is a linear combination of the columns a1, a2, ..., an, so the equation Ax = b holds if and only if b is in the column space of A.