Linear Algebra and Its Applications, Exercise 2.4.6

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

Answer: We first show that if the system Ax = b has at least one solution then the rank of A' is equal to the rank r of A:

If Ax = b for some x = (x_1, x_2, \dotsc, x_n) and v_1, v_2, \dotsc, v_n are the columns of A then we have

x_1v_1 + x_2v_2 + \cdots + x_nv_n = b

In other words, b is a linear combination of the columns of A with x_1, x_2, \dotsc, x_n being the coefficients.

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

We next show that if the rank of A' is the same as the rank r of A then the system Ax = b has at least one solution:

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

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

b = c_1v_1 + c_2v_2 + \cdots + c_nv_n

for some set of coefficients c_1, c_2, \dotsc, c_n. But if that is the case then the vector x = (c_1, c_2, \dotsc, c_n) is a solution to Ax = b.

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

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.

 Buy me a snack to sponsor more posts like this!

This entry was posted in linear algebra. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s