RREF: When a System Has No Solution

Last week I promised I would go over row reductions, and I thought the best way to do so would be to incorporate one of the fundamental concepts of linear algebra:

Reduced Row Echelon Form (RREF)

Assume we have the following variables:

$\begin{aligned}x&=\text{Money invested in AAPL},\\ y&=\text{Money invested in MSFT},\\ z&=\text{Money invested in NVDA},\\ w&=\text{Money invested in SPY}\end{aligned}$

But for some reason, a system is set up where these variables must satisfy the following equations:

$\begin{aligned}x_1+2x_2-x_3+3x_4&=9,\\ 2x_1+5x_2-2x_3+4x_4&=16,\\-x_1-x_2+2x_3-x_4&=-4,\\ 3x_1+7x_2-3x_3+7x_4&=23 \end{aligned}$

The objective is to find the values of:

$x_1,x_2,x_3,x_4$

How do we do it?

We use linear algebra and set up the system as:

$Ax=b$

Where:

$\begin{aligned}A&=\begin{bmatrix}1&2&-1&3\\ 2&5&-2&4\\-1&-1&2&-1\\ 3&7&-3&7 \end{bmatrix}\\ x&=\begin{bmatrix}x_1\\ x_2\\ x_3\\ x_4 \end{bmatrix}\\ b&=\begin{bmatrix}9\\ 16\\-4\\ 23 \end{bmatrix}\end{aligned}$

Thus:

$\begin{bmatrix}1&2&-1&3\\ 2&5&-2&4\\-1&-1&2&-1\\ 3&7&-3&7 \end{bmatrix}\begin{bmatrix}x_1\\ x_2\\ x_3\\ x_4 \end{bmatrix}=\begin{bmatrix}9\\ 16\\-4\\ 23 \end{bmatrix}$

The next step is to use row reductions to arrive at the RREF for matrix A.

But first, we need to set up the “game board”:

$\left[\begin{array}{cccc|c}1&2&-1&3&9\\ 2&5&-2&4&16\\-1&-1&2&-1&-4\\ 3&7&-3&7&23 \end{array}\right]$

When we row reduce, there are three operations we can perform:

$\begin{aligned}&R_i\to R_i+c\cdot R_j,\\ &R_i\to c\cdot R_i,\\ &R_i\leftrightarrow R_j,\\ &\text{Such that}\ c\in \mathbb{R}\end{aligned}$

In other words, we can:
- Replace a row with the sum of itself and a scalar multiple of another row.
- Multiply a row by a scalar.
- Interchange two rows.

The main idea behind RREF is that we work from left to right, creating pivots. Each pivot should be a “1“, with zeros both above and below it.

Let's start!

The entry in row 1, column 1 is already “1”, so we can use it as our first pivot. We want all entries below it to become “0“:

$\left[\begin{array}{cccc|c}1&2&-1&3&9\\ 2&5&-2&4&16\\-1&-1&2&-1&-4\\ 3&7&-3&7&23 \end{array}\right]\xrightarrow{\begin{aligned}&R_2\to R_2-2R_1\\ &R_3\to R_3+R_1\\ &R_4\to R_4-3R_1 \end{aligned}}\left[\begin{array}{cccc|c}1&2&-1&3&9\\ 0&1&0&-2&-2\\0&1&1&2&5\\ 0&1&0&-2&-4 \end{array}\right]$

Now we have our first pivot in row 1, so we move to column 2. Row 2 already contains our next pivot:

$\left[\begin{array}{cccc|c}1&2&-1&3&9\\ 0&1&0&-2&-2\\0&1&1&2&5\\ 0&1&0&-2&-4 \end{array}\right]\xrightarrow{\begin{aligned}&R_1\to R_1-2R_2\\ &R_3\to R_3-R_2\\ &R_4\to R_4-R_2 \end{aligned}}\left[\begin{array}{cccc|c}1&0&-1&7&13\\ 0&1&0&-2&-2\\0&0&1&4&7\\ 0&0&0&0&-2 \end{array}\right]$

At this point, we can already see something important.

The last row represents:

$0x_1+0x_2+0x_3+0x_4=0=-2$

That is a contradiction.

Therefore, the system has no solution.

At this point, if our only goal were to determine whether the system is consistent, we could stop. We already know the answer.

However, let's continue to obtain the actual RREF of matrix A.

We already have a pivot in column 3, so we eliminate the “-1“ above it:

$\left[\begin{array}{cccc|c}1&0&-1&7&13\\ 0&1&0&-2&-2\\0&0&1&4&7\\ 0&0&0&0&-2 \end{array}\right]\xrightarrow{R_1\to R_1+R_3}\left[\begin{array}{cccc|c}1&0&0&11&20\\ 0&1&0&-2&-2\\0&0&1&4&7\\ 0&0&0&0&-2 \end{array}\right]$

Now we have reached the actual RREF of matrix A:

$\left[\begin{array}{cccc|c}1&0&0&11&20\\ 0&1&0&-2&-2\\0&0&1&4&7\\ 0&0&0&0&-2 \end{array}\right]$

This is why RREF is so powerful.

We started with four equations and four unknowns, and it might have looked like our goal was simply to isolate:

$x_1,x_2,x_3,x_4$

But RREF tells us much more than that.

It can tell us whether a system has:
- One unique solution
- Infinitely many solutions
- No solution at all

In this case, RREF exposes the contradiction directly.

Until next week,
Peace.✌️

RREF: When a System Has No Solution

Keep Reading