Section 2.2 Intro to Solving Systems, Gaussian Elimination
Subsection 2.2.1 Existence and Uniqueness
When solving a system, we have two main questions:
- Existence. Does the system have at least one solution?
- Uniqueness. If the system has a solution, is it unique? Or, is there more than one solution?
Subsection 2.2.2 Triangular Systems, Back-Substitution
Some systems are particularly simple to solve.
\begin{equation*}
\begin{array}{rrrrr}
2x \amp + y \amp - z \amp = \amp -2 \\
\amp 3y \amp + z \amp = \amp 10 \\
\amp \amp 3z \amp = \amp 3
\end{array}
\end{equation*}
Notice that the last equation has only one variable, and so can be solved to determine the value of \(z\text{.}\) In this case, \(3z = 3\) implies that \(z = 1\text{.}\) In other words, if \((x,y,z)\) is a solution to this system, it must have \(z=1\) in order to satisfy the 3rd equation. Then, we can work backwards and determine the remaining values. First, this value of \(z\) can be used to solve for \(y\) in the second equation. If \(z = 1\text{,}\) then \(3y + 1 = 10\text{,}\) and solving for \(y\) gives \(y = 3\text{.}\) Finally, the values of \(y\) and \(z\) can be used to solve for \(x\text{,}\) using the first equation. If \(z = 1\) and \(y = 3\text{,}\) then \(2x + 3 - 1 = -2\text{,}\) and solving for \(x\) gives \(x = -2\text{.}\) Thus, this system has a single unique solution, \((-2,3,1)\text{.}\)Systems with this “staircase” form are called triangular. More precisely,
Definition 2.2.2.
A linear system is triangular if the last equation has at most 1 variable, the 2nd-last has at most 2 variables, the 3rd-last has at most 3 variables, etc.Triangular systems can be solved using this simple technique, called back-substitution. This technique can be used for any triangular system to solve for the value of each variable.
Subsection 2.2.3 Gaussian Elimination, Elementary Operations
Gaussian elimination is a procedure, or algorithm, to transform a system of linear equations to triangular form, making it much easier to solve. Broadly, it involves combining equations of a system in various ways. Each step replaces the current system with another somewhat simpler system, without changing the solution set.
Definition 2.2.3.
Two linear systems are called equivalent if they share the same solution set. That is, every solution of the first system is a solution of the second system, and vise versa.
In other words, the simpler system is equivalent to the original system, in that the simpler system has the same solution set as the original system. After the system is converted into triangular form, solving this resulting system gives the solution to the original system.
Definition 2.2.4. Elementary operations.
Denote equation \(i\) by \(E_i\text{.}\) Then, the elementary operations are,- Interchange. Interchange the order of two equations in the system, \(E_1 \leftrightarrow E_j\text{.}\)
- Scaling. Multiply (or divide) an equation by a non-zero real number, \(kE_i \rightarrow E_i\text{.}\)
- Replacement. Add to one equation a multiple of another equation, \(E_i + kE_j \rightarrow E_i\text{.}\)
The fact that these elementary operations do not change the solution set of the system is crucial, and it somewhat subtle, and will be explained after an example.
Example 2.2.5.
\begin{equation*}
\begin{array}{rrrrr}
2x \amp + y \amp + z \amp = \amp 1 \\
4x \amp + y \amp \amp = \amp -2 \\
-2x \amp + 2y \amp + z \amp = \amp 7
\end{array}
\end{equation*}
We want to convert this system into triangular form, from which it will be easy to solve. To do this, we need to eliminate the variables below the main diagonal, i.e. eliminate \(x\) from the 2nd and 3rd equation and \(y\) from the 3rd equation. To do this, first, add \(-2\) times the 1st equation to the 2nd equation, and add the 1st equation to the 3rd equation. This results in the equivalent system,
\begin{equation*}
\begin{array}{rrrrr}
2x \amp + y \amp + z \amp = \amp 1 \\
\amp -y \amp -2z \amp = \amp -4 \\
\amp 3y \amp + 2z \amp = \amp 8
\end{array}
\end{equation*}
Notice that this involved choosing appropriate multiples of the 1st equation to add to the other equations. Next, we use the 2nd equation to eliminate \(y\) in the 3rd equation, by adding 3 times the 2nd equation to the 3rd equation. This is results in the system,
\begin{equation*}
\begin{array}{rrrrr}
2x \amp + y \amp + z \amp = \amp 1 \\
\amp -y \amp -2z \amp = \amp -4 \\
\amp \amp -4z \amp = \amp -4
\end{array}
\end{equation*}
This system is in triangular form, so we can use back substitution. Solving for \(z\text{,}\) we get \(z = 1\text{.}\) Then, solving for \(y\) gives \(y = 2\text{,}\) and finally \(x = -1\text{.}\)Subsection 2.2.4 Remark on Elementary Operations
A crucial property of elementary operations is that applying them does not change the solution set of the system. More precisely, if an elementary operation transforms system 1 into system 2, then system 1 and system 2 have the same solution set.
- First, interchanging two equations \(E_i \leftrightarrow E_j\text{,}\) i.e. rearranging the order of the equations, clearly does not affect the solutions of those two equations, and so doesn't affect the solution set of the system.
- Also, multiplying an equation \(E_i\) by a non-zero constant \(k\) does not change the solutions of that equation, as any solution of \(E_i\) is also a solution of \(kE_i\text{,}\) and vise versa. This is true as long as \(k \neq 0\text{,}\) as if \(k = 0\text{,}\) then \(0 \cdot K_i\) is just the equation \(0 = 0\) for which any tuple will be a solution.
- Finally, consider adding a multiple of an equation to another equation, \(E_i + kE_j \rightarrow E_i\text{.}\) Let \((x_1, \dots, x_n)\) be a solution to the original system. Then, it is a solution of \(E_i\) and \(E_j\text{.}\) From before, it is also a solution to \(kE_j\text{.}\) This implies that \((x_1, \dots, x_n)\) is a solution to the sum \(E_i + kE_j\text{.}\)
Subsection 2.2.5 Solving Systems of Two Equations in Two Variables
Consider a system of two equations in two unknowns,
\begin{align*}
a x_1 + b x_2 \amp = y_1 \\
c x_1 + d x_2 \amp = y_2
\end{align*}
Here, we have relabelled variables for simplicity. The variables here are \(x_1\) and \(x_2\text{,}\) and the coefficients are \(a, b, c, d, y_1, y_2\text{.}\) Using elimination, we can solve this system. For example, to eliminate \(x_1\) in the second equation, subtract \(c\) times the first equation to \(a\) times the second equation. The resulting equation is,
\begin{equation*}
(ad - bc) x_2 = a y_2 - c y_1
\end{equation*}
Then, we can solve for \(x_2\) by dividing both sides by \(ad - bc\text{,}\)
\begin{equation*}
x_2 = \frac{1}{ad - bc} \brac{a y_2 - c y_1}
\end{equation*}
This is the unique solution for \(x_2\text{,}\) provided that \(ad - bc \neq 0\text{.}\) Similarly, starting from the original system,
\begin{align*}
a x_1 + b x_2 \amp = y_1 \\
c x_1 + d x_2 \amp = y_2
\end{align*}
We can eliminate \(x_2\) in the second equation by subtracting \(d\) times the first equation from \(b\) times the second equation. The resulting equation is,
\begin{equation*}
(ad - bc) x_1 = d y_1 - b y_2
\end{equation*}
Then, similarly, solving for \(x_1\text{,}\)
\begin{equation*}
x_1 = \frac{1}{ad - bc} \brac{d y_1 - b y_2}
\end{equation*}
Again, provided that \(ad - bc \neq 0\text{.}\) For simplicity, we will denote \(\Delta = ad - bc\) (this will be revisited later). Then, if \(\Delta \neq 0\text{,}\) the unique solution is,
\begin{equation*}
(x,y) = \brac{\frac{1}{\Delta} \brac{d y_1 - b y_2}, \frac{1}{\Delta} \brac{a y_2 - c y_1}}
\end{equation*}
Note that this unique solution only exists if \(\Delta \neq 0\text{.}\) If \(\Delta = 0\text{,}\) then there may be infinitely many solutions, or no solution.
