Solving systems of linear equations

Main topics:

• Gaussian elimination
• Solving systems of linear equations over ${\bf R}$
• Possible geometric structure of the solution set to a system of $3$ linear equations over ${\bf R}$ in $3$ unknowns
• Reduced row echelon form of a matrix is unique.
• Possible solution sets for a system of $3$ linear equations.

Planes in ${\bf R}^3$ are given by linear equations.

$$a_1^k\bar{x_1} + a_2^k\bar{x_2}+ \ldots + a_n^k\bar{x_n} = \bar{b_k}$$

This is "$k$ equations in $n$ unknowns$!

There is a vector equation behind this system of linear (scalar) equations.

Problem: Given all the coefficients and all the vectors $\bar{b_i}$, find the vectors $\bar{x_1},\ldots,\bar{x_n}$.

Example:

$\left\{ \begin{array}{rl} 3x+4y=9 \\ 5x+7y=2 \end{array} \right.$

• $3x+4y=9$
• $5x+7y=2$

Our vector space is ${\bf R}$, $x,y \in {\bf R}$.

Now let's simplify the algebra:

Idea: ignore the variables.

$\begin{array}{} 3&4&9&R_1 \\ 5&7&2&R_2 \\ 8&11&11&R_1+R_2 \end{array}$

This means $8x+11y=11$.

Example: Solve

$\left\{ \begin{array}{rl} x+z=5 \\ y+z=3 \\ 2x+z=8 \end{array} \right.$

Superposition of waves:

$\bar{w_1}+\bar{w_2}$

Different scales:

A linear equation looks like $$a_1^1\bar{x_1}+a_2^1\bar{x_2}+ \ldots + a_n^1\bar{x_n} = \bar{b_1}.$$

System of equations

Example:

$\left\{ \begin{array}{rl} 3x+4y=9 \\ 5x+7y=2 \end{array} \right.$

Generally: $$a_1^1\bar{x_1} + a_2^1\bar{x_2}+\ldots+a_n^1\bar{x_n} = \bar{b_1}$$ $$a_1^2\bar{x_1} + a_2^2\bar{x_2}+\ldots+a_n^2\bar{x_n} = \bar{b_2}$$

• 1. Translate

$\begin{array}{} 1 & 0 & 1 & 5 & R_1 \\ 0 & 1 & 1 & 3 & R_2 \\ 2 & 0 & 1 & 8 & R_3 \\ 0 & 0 & -1 & -2 & R_4=R_3-2R_1 \end{array}$

• 2. Solve

Means $-z=-2$

$\begin{array}{} 0 & 0 & 1 & 2 & R_5=-R_4 \\ 1 & 0 & 0 & 3 & R_6=R_1-R_5 \\ \end{array}$

$x=3$

$\begin{array}{} 0 & 1 & 0 & 1 & R_7=R_2-R_5 \\ \end{array}$

$y=1$

• 3. Interpret the solution

$x=3$, $y=1$, $z=2$

Let's review. We've learned how to solve systems via augmented matrices.

They look like this one:

$\left[ \begin{array}{ccc|c} 1 & 2 & 3 & 4 \\ 0 & 1 & 2 & 5 \end{array} \right]$

The left side of the bar has the coefficients of $x_1$, $x_2$, $x_3$ variables and the right side of the bar has the free terms.

The line is important! It reminds you: augmented matrix is not a matrix.

We solve them by means of appropriately recorded row operations.

Plan: $\left[ \begin{array}{cc|c} \cdot & \cdot & \cdot \\ \cdot & \cdot & \cdot \end{array} \right] \stackrel{{\rm row \hspace{3pt} op}}{\rightarrow} \left[ \begin{array}{cccc|c} 1 & 0 & 0 & 2 & 1 \\ 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 2 & 2 \end{array} \right]$

Example:

The result can be rewritten as the solution of the system...

$\left\{ \begin{array}{} x_1 & & & +2x_4 &= 1 &\rightarrow & x_1 = 1-2x_4 \\ & x_2 & & +x_4 &= 0 &\rightarrow & x_2=-x_4 \\ & & x_3 & +2x_4 &= 2 &\rightarrow & x_3=2-2x_4 \end{array} \right.$

Now what is the solution set $S \subset {\bf R}^4$, i.e., those $(x_1,x_2,x_3,x_4)$ that satisfy the system?

Idea: Make $x_4$ a parameter, $t$.

Then,

$\left\{ \begin{array}{} x_1 &=1-2t \\ x_2 &=-t \\ x_3 &=2 - 2t\\ x_4 &=t \end{array} \right.$

Rewrite in the vector form: $\left[ \begin{array}{} x_1 \\ x_2 \\ x_3 \\ x_4 \end{array} \right] = \left[ \begin{array}{} 1-2t \\ -t \\ 2-2t \\ t \end{array} \right] = \left[ \begin{array}{} 1 \\ 0 \\ 2 \\ 0 \end{array} \right] + \left[ \begin{array}{} -2t \\ -t \\ -2t \\ t \end{array} \right] = \left[ \begin{array}{} 1 \\ 0 \\ 2 \\ 0 \end{array} \right] + t\left[ \begin{array}{} -2 \\ -2 \\ -2 \\ 1 \end{array} \right]$

The vector on the left hand side is the vector $x$, solution, and the vectors on the right hand side are $a$ and $v$ respectively. In $t$, $a$ and $v$ are specific!

Thus $x=a+tv$, $t \in {\bf R}$.

So the solution set is $S = \{ x = a+tv \colon t \in {\bf R} \}$. By definition, $s$ is a line:

Example: Example of a plane as the solution set.

$$S = \{x = a+tv+sw \colon t, s \in {\bf R} \} \subset {\bf R}^4$$

Definition.

$a = \left[ \begin{array}{} 1 \\ 2 \\ 3 \\ 4 \end{array} \right]$, $v = \left[ \begin{array}{} 0 \\ 1 \\ 0 \\ 1 \end{array} \right]$, $w = \left[ \begin{array}{} 1 \\ 0 \\ 1 \\ 0 \end{array} \right]$

Rewrite.

$\left[ \begin{array}{} x_1 \\ x_2 \\ x_3 \\ x_4 \end{array} \right] = \left[ \begin{array}{} 1 \\ 2 \\ 3 \\ 4 \end{array} \right] + t \left[ \begin{array}{} 0 \\ 1 \\ 0 \\ 1 \end{array} \right] + s \left[ \begin{array}{} 1 \\ 0 \\ 1 \\ 0 \end{array} \right] = \left[ \begin{array}{} 1+s \\ 2+t \\ 3+s \\ 4+t \end{array} \right]$,

$s, t$ are two parameters.

Rewrite:

$\left\{ \begin{array}{} x_1 &= 1+5 \\ x_2 &= 2+t \\ x_3 &= 3+s \\ x_4 &= 4+t \end{array} \right. \rightarrow$

row-reduced echelon system.

Theorem: A homogeneous system with (like one above) $m$ linear equations and $n$ unknowns, with $n>m$, has at least one non-zero solution.

Idea of proof: There will be at most $m$ $1$'s in the reduced row echelon form. Hence there will be free variables (parameters). Give these parameters non-zero values. Find the dependent variables from the system. That gives us a non-zero solution.