# the system of linear equations

If you have a matrix M that looks like

\begin{bmatrix}1&0&1&1\\-1&2&0&4 \\ 0&2&1&5\end{bmatrix}

Does Mx=b (x and b are vectors) have a unique solution for all possible values of b?

And also how can I know the basis for the range space or the null space?

I have done Gaussian elimination on this matrix and I got \begin{bmatrix}1&0&1&1\\0&1&1/2&5/2 \\ 0&0&0&0\end{bmatrix} so I was guessing that \begin{pmatrix}1\\0\\0\end{pmatrix} and \begin{pmatrix}0\\1\\0\end{pmatrix} are the basis for the range space of this matrix.

• So, what I did so far is that changing the form of the matrix to \begin{bmatrix}1&0&1&1\\0&1&1/2&5/2 \\ 0&0&0&0\end{bmatrix} and I'm guessing the basis for the range space is 2. Am I correct? – Tatsunari Watanabe Apr 4 '18 at 11:30
• Now, you know that rank(M) = 2, do you know the rank-nullity theorem? You may include your comment into the question body so that we know that you've tried calculating the RREF of $M$. – GNUSupporter 8964民主女神 地下教會 Apr 4 '18 at 11:33
• Is that the one rank + nullity has to be the dimension? – Tatsunari Watanabe Apr 4 '18 at 11:35
• A google search gives the Wiki for this theorem, apply the formula to this case: rank(M) + nullity(M) = number of columns of M. – GNUSupporter 8964民主女神 地下教會 Apr 4 '18 at 11:39
• Does that mean that the nullity(M)=2? – Tatsunari Watanabe Apr 4 '18 at 11:45

## 2 Answers

Hint: add first row to the second row

The the second row is equal to the last row, so $\operatorname{rank}(M) = \dots$

Edit in response to OP's comment and edit:

OP has calculated the RREF of $M$

$$\begin{bmatrix}1&0&1&1\\0&1&1/2&5/2 \\ 0&0&0&0\end{bmatrix}.$$

$M$ can be viewed as a linear transformation from $\Bbb{R}^4$ to $\Bbb{R}^3$, so its range is its column space spanned by a basis $\{e_1,e_2\}$. (OP has got it right.)

The nullspace of $M$ as the set of $x \in \Bbb{R}^4$ so that $Mx = 0$. By the Rank-nullity Theorem, $\operatorname{nullity}(M) = 2$, so the nullspace of $M$ has dimension two.

From the third column of the RREF, we have basis vectors for the nullspace of $M$: $v_1 = (1, 1/2, -1, 0)^T$; from the fourth column, we have $v_2 = (1, 5/2, 0, -1)^T$.

Since $\operatorname{nullity}(M) > 0$, $Mx = b$ doesn't have unique solution.

• so \begin{pmatrix}1\\0\\0\end{pmatrix} and \begin{pmatrix}0\\1\\0\end{pmatrix} is the basis for the range space and \begin{pmatrix}1\\1/2\\0\end{pmatrix} and \begin{pmatrix}1\\5/2\\0\end{pmatrix} is the basis for the null space? – Tatsunari Watanabe Apr 4 '18 at 12:02
• @TatsunariWatanabe Yes for the first question; no for the 2nd one because the nullspace is a subspace of $\Bbb{R}^4$. Btw, your acct name reminds me of Shinzo Watanabe, the writer of a bible of (sde) XD. – GNUSupporter 8964民主女神 地下教會 Apr 4 '18 at 12:15

Your proposed basis doesn’t work. I suspect that you’re confusing the rule about how to read a basis for the row space of a matrix from its RREF with that of how to read a basis for its column space—its range.

Think about how you might compute the product of a matrix and vector. If you expand the product of $M$ with an arbitrary vector by columns, you have $$\begin{bmatrix}1&0&1&1\\-1&2&0&4 \\ 0&2&1&5\end{bmatrix} \begin{bmatrix}a\\b\\c\\d\end{bmatrix} = a\begin{bmatrix}1\\-1\\0\end{bmatrix} + b\begin{bmatrix}0\\2\\2\end{bmatrix} + c\begin{bmatrix}1\\0\\1\end{bmatrix} + d\begin{bmatrix}1\\4\\5\end{bmatrix},$$ so every such product is a linear combination of the columns of $M$, i.e., the range of $M$ is the span of its columns. In particular, every column of $M$ is an element of its range. Looking at your proposed basis for the range, we see that the last component of every linear combination of those vectors is $0$, so there’s no way to combine them to produce any of the last three columns of $M$. On the other hand, the original columns of $M$ that correspond to pivot columns in its RREF do form a basis for its range.

Basically, elementary row operations leave the row space of a matrix unchanged but change its column space. Consider, for example, the matrix $\tiny{\begin{bmatrix}1&1\\1&1\end{bmatrix}}$. Its column space is obviously spanned by $(1,1)^T$, but its RREF is $\tiny{\begin{bmatrix}1&1\\0&0\end{bmatrix}}$, whose column space is spanned by $(1,0)^T$. More generally, performing an elementary row operation is equivalent to left-multiplying by a certain invertible matrix $E$. The row space of a matrix $M$ is the orthogonal complement of its null space $\mathscr N(M)$. Since $E$ has full rank, $\mathscr N(EM)=\mathscr N(M)$ ($E$ can’t grow the null space because the only vector that it maps to $0$ is $0$), therefore the row spaces of $M$ and $EM$ are also identical. On the other hand, the range of $EM$ is the image under $E$ of the range of $M$. In general these are different subspaces of the codomain, although they’ll have the same dimension since $E$ has full rank.

Now, there’s a theorem that says that if $M\mathbf v$ and $M\mathbf w$ are linearly independent, then so are $\mathbf v$ and $\mathbf w$. (Proving this theorem is a useful exercise.) The sequence of elementary row operations applied to $M$ to obtain its RREF can be combined into a single invertible matrix $S$. This matrix preserves linear independence, so linearly-independent columns of $SM$ correspond to linearly-independent columns of $M$. The pivot columns of the RREF are obviously linearly independent, and the rank-nullity theorem tells us that the dimension of the range is equal to the number of pivot columns, so they form a basis for the range of $SM$. This means that the corresponding columns of $M$ are a basis for the range of $M$.