## 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 .

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