7 Systems of Linear Equations
7.1 Linear Equation
Linear equations take form of a_1 x_1 + a_2 x_2 + \cdots + a_n x_n = b
- a_i are parameters or coefficients
- x_i are variables or unknowns
Linear because only one variable per term and degree is at most 1.
We are often interested in solving linear systems like
\left\{\begin{array}{ll} x-3y &= -3\\ 2x +y &= 8 \end{array}\right.
More generally, we might have a system of m equations in n unknowns \begin{matrix} a_{11}x_1 & + & a_{12}x_2 & + & \cdots & + & a_{1n}x_n & = & b_1\\ a_{21}x_1 & + & a_{22}x_2 & + & \cdots & + & a_{2n}x_n & = & b_2\\ \vdots & & & & \vdots & & & \vdots & \\ a_{m1}x_1 & + & a_{m2}x_2 & + & \cdots & + & a_{mn}x_n & = & b_m \end{matrix}
A solution to a linear system of m equations in n unknowns is a set of n numbers x_1, x_2, \cdots, x_n that satisfy each of the m equations.
Example: x=3 and y=2 is the solution to the above 2\times 2 linear system. If you graph the two lines, you will find that they intersect at (3,2).
Does a linear system have one, no, or multiple solutions? For a system of 2 equations with 2 unknowns (i.e., two lines):
- One solution: The lines intersect at exactly one point.
- No solution: The lines are parallel.
- Infinite solutions: The lines coincide.
Methods to solve linear systems:
- Substitution
- Elimination of variables
- Matrix methods
Exercise 7.1 Provide a system of 2 equations with 2 unknowns that has
- one solution
- no solution
- infinite solutions
7.2 Systems of Equations as Matrices
Matrices provide an easy and efficient way to represent linear systems such as \begin{matrix} a_{11}x_1 & + & a_{12}x_2 & + & \cdots & + & a_{1n}x_n & = & b_1\\ a_{21}x_1 & + & a_{22}x_2 & + & \cdots & + & a_{2n}x_n & = & b_2\\ \vdots & & & & \vdots & & & \vdots & \\ a_{m1}x_1 & + & a_{m2}x_2 & + & \cdots & + & a_{mn}x_n & = & b_m \end{matrix}
as {\bf A x = b} where
The m \times n {\bf A} is an array of m n real numbers arranged in m rows by n columns: {\bf A}=\begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & & \ddots & \vdots \\ a_{m1} & a_{m2} & \cdots & a_{mn} \end{bmatrix}
The unknown quantities are represented by the vector {\bf x}=\begin{bmatrix} x_1\\x_2\\\vdots\\x_n \end{bmatrix}.
The right hand side of the linear system is represented by the vector {\bf b}=\begin{bmatrix} b_1\\b_2\\\vdots\\b_m \end{bmatrix}.
Augmented Matrix: When we append \bf b to the coefficient matrix \bf A, we get the augmented matrix \widehat{\bf A}=[\bf A | b] \begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n} & | & b_1\\ a_{21} & a_{22} & \cdots & a_{2n} & | & b_2\\ \vdots & & \ddots & \vdots & | & \vdots\\ a_{m1} & a_{m2} & \cdots & a_{mn} & | & b_m \end{bmatrix}
Exercise 7.2 Create an augmented matrix that represent the following system of equations:
2x_1 -7x_2 + 9x_3 -4x_4 = 8
41x_2 + 9x_3 -5x_6 = 11
x_1 -15x_2 -11x_5 = 9
7.3 Finding Solutions to Augmented Matrices and Systems of Equations
Row Echelon Form: Our goal is to translate our augmented matrix or system of equations into row echelon form. This will provide us with the values of the vector x which solve the system. We use the row operations to change coefficients in the lower triangle of the augmented matrix to 0. An augmented matrix of the form \begin{bmatrix} \fbox{$a'_{11}$}& a'_{12} & a'_{13}& \cdots & a'_{1n} & | & b'_1\\ 0 & \fbox{$a'_{22}$} & a'_{23}& \cdots & a'_{2n} & | & b'_2\\ 0 & 0 & \fbox{$a'_{33}$}& \cdots & a'_{3n} & | & b'_3\\ 0 & 0 &0 & \ddots & \vdots & | & \vdots \\ 0 & 0 &0 &0 & \fbox{$a'_{mn}$} & | & b'_m \end{bmatrix}
is said to be in row echelon form — each row has more leading zeros than the row preceding it.
Reduced Row Echelon Form: We can go one step further and put the matrix into reduced row echelon form. Reduced row echelon form makes the value of x which solves the system very obvious. For a system of m equations in m unknowns, with no all-zero rows, the reduced row echelon form would be
\begin{bmatrix} \fbox{$1$} & 0 & 0 & 0 & 0 & | & b^*_1\\ 0 & \fbox{$1$} & 0 & 0 & 0 & | & b^*_2\\ 0 & 0 & \fbox{$1$} & 0 & 0 & | & b^*_3\\ 0 & 0 & 0 &\ddots & 0 & | &\vdots\\ 0 & 0 & 0 & 0 & \fbox{$1$} & | & b^*_m \end{bmatrix}
Gaussian and Gauss-Jordan elimination: We can conduct elementary row operations to get our augmented matrix into row echelon or reduced row echelon form. The methods of transforming a matrix or system into row echelon and reduced row echelon form are referred to as Gaussian elimination and Gauss-Jordan elimination, respectively.
Elementary Row Operations: To do Gaussian and Gauss-Jordan elimination, we use three basic operations to transform the augmented matrix into another augmented matrix that represents an equivalent linear system – equivalent in the sense that the same values of x_j solve both the original and transformed matrix/system:
Interchanging Rows: Suppose we have the augmented matrix {\widehat{\bf A}}=\begin{bmatrix} a_{11} & a_{12} & | & b_1\\ a_{21} & a_{22} & | & b_2 \end{bmatrix} If we interchange the two rows, we get the augmented matrix \begin{bmatrix} a_{21} & a_{22} & | & b_2\\ a_{11} & a_{12} & | & b_1 \end{bmatrix} which represents a linear system equivalent to that represented by matrix \widehat{\bf A}.
Multiplying by a Constant: If we multiply the second row of matrix \widehat{\bf A} by a constant c, we get the augmented matrix \begin{bmatrix} a_{11} & a_{12} & | & b_1\\ c a_{21} & c a_{22} & | & c b_2 \end{bmatrix} which represents a linear system equivalent to that represented by matrix \widehat{\bf A}.
Adding (subtracting) Rows: If we add (subtract) the first row of matrix \widehat{\bf A} to the second, we obtain the augmented matrix \begin{bmatrix} a_{11} & a_{12} & | & b_1\\ a_{11}+a_{21} & a_{12}+a_{22} & | & b_1+b_2 \end{bmatrix} which represents a linear system equivalent to that represented by matrix \widehat{\bf A}.
Example 7.1
Solve the following system of equations by using elementary row operations: \begin{matrix} x & - & 3y & = & -3\\ 2x & + & y & = & 8 \end{matrix}
Exercise 7.3 Put the following system of equations into augmented matrix form. Then, using Gaussian or Gauss-Jordan elimination, solve the system of equations by putting the matrix into row echelon or reduced row echelon form.
- \begin{cases} x + y + 2z = 2\\ 3x - 2y + z = 1\\ y - z = 3 \end{cases}
- \begin{cases} 2x + 3y - z = -8\\ x + 2y - z = 12\\ -x -4y + z = -6 \end{cases}
Answers to Examples and Exercises
Answer to Exercise 7.1:
There are many answers to this. Some possible simple ones are as follows:
One solution: \begin{matrix} -x & + & y & = & 0\\ x & + & y & = & 2 \end{matrix}
No solution: \begin{matrix} -x & + & y & = & 0\\ x & - & y & = & 2 \end{matrix}
Infinite solutions: \begin{matrix} -x & + & y & = & 0\\ 2x & - & 2y & = & 0 \end{matrix}
Answer to Exercise 7.2:
\begin{bmatrix} 2 & -7 & 9 & -4 & 0 & 0| & 8\\ 0 & 41 & 9 & 0 & 0 & 5 | & 11\\ 1 & -15 & 0 & 0 & -11 & 0 | & 9 \end{bmatrix}
Answer to Example 7.1:
\begin{matrix} x & - & 3y & = & -3\\ 2x & + & y & = & 8 \end{matrix}
\begin{matrix} x & - & 3y & = & -3\\ & & 7y & = & 14\\ \end{matrix}
\begin{matrix} x & - & 3y & = & -3\\ & & y & = & 2\\ \end{matrix}
\begin{matrix} x & = & 3\\ y & = & 2\\ \end{matrix}
Answer to Exercise 7.3:
x = 2, y = 2, z = -1
x = -17, y = -3, z = -35