Linear Systems and Gaussian Elimination

One of the great uses of matrices is representing and solving linear systems of algebraic equations. Here's an example of a system of two equations and two unknowns:

$$\large \begin{split} x-y&=1\\ 2x+y&=6\\ \end{split} $$

In general, a linear system could have any number of unknowns and any number of equations. Here's a general system with $\large m$ unknowns and $\large n$ equations:

$$\large \begin{split} a_{11}x_1+a_{12}x_2+\dots+a_{1m}x_m&=b_1\\ a_{21}x_1+a_{22}x_2+\dots+a_{2m}x_m&=b_2\\ \quad \vdots \quad\quad \vdots \quad\quad\quad\quad \vdots \quad \vdots \\ a_{n1}x_1+a_{n2}x_2+\dots+a_{nm}x_m&=b_n\\ \end{split} $$

We've already seen that any system of linear equations can be written as $\large A\vec{x}=\vec{b}$.

Solutions

We will look at what types of solutions we can get from an linear system of equations.

Two Lines

Let's return to the system of two equations and two unknowns:

$$\large \begin{split} x-y&=1\\ 2x+y&=6\\ \end{split} $$

These are equations of lines. A solution is the intersection of the two lines. There are three possibilities; we either have a single solution, no solution, or infinitely many solutions, as illustrated below:

A solution is any $\large(x,y)$ point where both equations are satisfied simultaneously. We see that there is no solution if the lines are parallel, and there are infinitely many solutions if the two lines are really the same line (if the two equations are equivalent).

Three Planes

What if we have 3 equations and 3 unknowns?

$$\large \begin{split} 2x+y+z&=-2\\ -x+4y-3z&=8\\ x+y-z&=1\\ \end{split} $$

These are now equations of planes. We are now looking for points of intersection of three planes. We end up with the same result: there is either one solution, no solution, or infinitely many solutions. Here's an image of the three planes above, and we can see there is a single point of intersection:

Note

With planes, there are two ways to end up with infinite solutions: (1) all three equations are the same plane; in this case, any point on that plane is a solution, or (2) the three planes intersect along a line, so any point on the line is a solution.

Larger Systems

Most systems of linear equations in STEM applications are much larger than $\large 2\times 2$ or $\large 3 \times 3$. It is common to have millions of equations and unknowns in big problems in data science or differential equations. But we can no longer visualize things once we get past planes!

The good news is that our result still holds:

Important

Any linear system of any size can have either one solution, no solution, or infinitely many solutions.

As we say with planes, there can be different ways for a system to have infinitely many solutions.

Warning

Infinitely many solutions doesn't mean any point is a solution! It means there is some infinite set of points that all satisfy the system of equations.

Finally, a definition:

A system is consistent if it has 1 or more solution and inconsistent if it has no solution.

Finding Solutions: Gaussian Elimination

Now, the meat of this lesson is in how to actually solve these systems of equations. How do we solve $\large A\vec{x}=\vec{b}$? We solved these things in high school through processes of elimination and substitution. This short video will illustrate some of things we can do to solve systems:

The video shows that there are essentially 3 things we can do to a system of equations without changing the solution set. We call these row operations:

1. Multiply an equation by a nonzero constant.
2. Interchange equations.
3. Add a multiple of one equation to another.

To solve a system of equations, we repeatedly and strategically apply the three steps above. This can be very systematic, and the result is the algorithm known as Gaussian Elimination.

The video below shows Gaussian Elimination on the following system:

$$\large \begin{split} x+y+2z&=9\\ 2x+4y-3z&=1\\ 3x+6y-5z&=0\\ \end{split} $$

At 14 minutes, this is the longest video of the class. Gaussian Elmination is a time consuming algorithm that requires us to be careful with arithmetic. We will do it a bit on HW in this lecture and the next. We will do it once on an exam. But really, Gaussian Elimination should primarily done by computers! We will see built in algorithms for Gaussian Elimination in Lab #2.

Note

Gaussian elimination is sometimes referred to as row reduction.

Note

Our video showed the most straightforward case: a system with $\large n$ equations and $\large n$ unknowns that has a single solution. We still need to see how to deal with systems with no solutions or infinitely many solutions. We still need to see how to deal with systems where there are more/fewer equations than unknowns. This will all be part of tomorrow's lecture.

Section Outcomes

I can:

• Recall definitions of coefficient matrix, right hand side vector, consistent, and inconsistent.
• Represent a system of equations as $\large A\vec{x}=\vec{b}$.
• Write an $\large A\vec{x}=\vec{b}$ system out as individual equations.
• Solve a system of equations using Gaussian Elimination.