Exercise 2.4.6. Given a matrix with rank show that the system has a solution if and only if the matrix also has rank , where is formed by taking the columns of and adding as an additional column.

Answer: We first show that if the system has at least one solution then the rank of is equal to the rank of :

If for some and are the columns of then we have

In other words, is a linear combination of the columns of with being the coefficients.

Consider the matrix formed by adding the vector to as an additional column. The rank of is equal to the number of columns of that are linearly independent. From above we know that is a linear combination of the columns of and thus of the other columns of . The number of linearly independent columns in is therefore the same as the number of linearly independent columns in so that both matrices have the same rank .

We next show that if the rank of is the same as the rank of then the system has at least one solution:

The rank of is the number of linearly independent columns of . If the rank of is the same as that of then there are only linearly independent columns of as well. But since every column of is also in that means that the column of equal to must be linearly dependent on the other columns of and thus linearly dependent on the columns of . (If this were not the case, i.e., if were linearly independent of the other columns of , then the rank of would be equal to not to .)

Since is linearly dependent on the columns of and thus is a linear combination of those columns, we must have

for some set of coefficients . But if that is the case then the vector is a solution to .

Summing up, we have shown that if has at least one solution then the rank of is equal to the rank of , and also that if the rank of is equal to the rank of then has at least one solution. We have therefore shown that the system has a solution if and only if the matrix has the same rank as the original matrix .

NOTE: This continues a series of posts containing worked out exercises from the (out of print) book Linear Algebra and Its Applications, Third Edition by Gilbert Strang.

If you find these posts useful I encourage you to also check out the more current Linear Algebra and Its Applications, Fourth Edition, Dr Strang’s introductory textbook Introduction to Linear Algebra, Fourth Edition and the accompanying free online course, and Dr Strang’s other books.