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

-
@GitGud Added explanation for logically equivalent. –  dal102 Feb 2 '13 at 21:01
I think you should say equivalent, rather than logically equivalent. –  1015 Feb 2 '13 at 21:49

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