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