Columns of matrix $A_{m \times n}$ span $\mathbb{R}^{m}$

I am having trouble understanding the following theorem given in my textbook:

Let $A$ be an $ m \times n $ coefficient matrix. Then the following statements are logically equivalent (That is, for a particular $A$, either they are all true or all false statements.)

a) For each b in $\mathbb{R}^{m}$, the equation $A$ x = b has a solution.
b) Each b in $\mathbb{R}^{m}$ is a linear combination of the columns of $A$.
c) The columns of $A$ span $\mathbb{R}^{m}$.
d) $A$ has a pivot position in every row.

I understand that a, b, c are restatements of each other. I would like some intuition on why statement d and the others (particularly c) are logically equivalent.

Solution 1:

You will find the answer to this in most introductory linear algebra textbooks but a quick answer would be as follows:

• If for each $b$, you have a solution to $Ax=b$, it implies that the columns of $A$ are linearly independent. If this were not true, then they would only span a subspace of $R^n$ and if we chose a vector $b$ which was not in this subspace, the above statement would not hold.
• Since $Ax=b$ can be written out as $\sum_i A_i x_i =b$ where $A_i$ denotes the $i^{th}$ column of A and since the columns of $A$ are linearly independent and span $R^n$, they form a basis for $R^n$ and thus, any bector $b$ can be written out as a linear combination of the basis and hence of the columns of A.
• All of the above statements imply that the matrix is full rank and invertible.
• If one started a Gaussian Elimination on A and found a row where there was no pivot, then the matrix is not invertible which contradicts the above statement.
• Another way of thinking about it is that through Gaussian Elimination (or Gauss-Jordan Elimination), you are trying to "create" an identity matrix on the left and the solution for $Ax=b$ on the right. If you are unable to find a pivot in any position, it implies that you are unable to span the whole space since you are constraining the possible RHS.