Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
@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
up vote 2 down vote accepted

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.
share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.