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

# Systems of Linear Equations ## 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: 1. Substitution 2. Elimination of variables 3. Matrix methods :::{#exr-lineareq} Provide a system of 2 equations with 2 unknowns that has 1. one solution 2. no solution 3. infinite solutions ::: ## 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$ \textbf{coefficient matrix} ${\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}$$ :::{#exr-augmatrix} 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$$ ::: ## 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}$. :::{#exm-solvesys} Solve the following system of equations by using elementary row operations: $$\begin{matrix} x & - & 3y & = & -3\\ 2x & + & y & = & 8 \end{matrix}$$ ::: :::{#exr-solvesys1} 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. 1. $$ \begin{cases} x + y + 2z = 2\\ 3x - 2y + z = 1\\ y - z = 3 \end{cases}$$ 2. $$ \begin{cases} 2x + 3y - z = -8\\ x + 2y - z = 12\\ -x -4y + z = -6 \end{cases}$$ ::: ## Answers to Examples and Exercises {-} Answer to @exr-lineareq: There are many answers to this. Some possible simple ones are as follows: 1. One solution: $$\begin{matrix} -x & + & y & = & 0\\ x & + & y & = & 2 \end{matrix}$$ 2. No solution: $$\begin{matrix} -x & + & y & = & 0\\ x & - & y & = & 2 \end{matrix}$$ 3. Infinite solutions: $$\begin{matrix} -x & + & y & = & 0\\ 2x & - & 2y & = & 0 \end{matrix}$$ Answer to @exr-augmatrix: $\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 @exm-solvesys: $$\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 @exr-solvesys1: 1. x = 2, y = 2, z = -1 2. x = -17, y = -3, z = -35