Chapter 5: Matrices
Section 5.7 Matrices
Gaussian Elimination
When we encounter the following system of two linear equations in two unknowns:
x + y = 70
24x + 14y = 1180
The general form for a system of \(n\) linear equations in \(n\) unknowns is $$ \begin{aligned} a_{11}x_1 + a_{12}x_2 + \dots + a_{1n}x_n & = b_1 \\ a_{21}x_1 + a_{22}x_2 + \dots + a_{2n}x_n & = b_2 \\ \vdots \\ a_{n1}x_1 + a_{n2}x_2 + \dots + a_{nn}x_n & = b_2 \end{aligned} $$ with a matrix of coefficients: $$ \begin{pmatrix} a_{11} & a_{12} & \dots & a_{1n} \\ a_{21} & a_{22} & \dots & a_{2n} \\ \vdots \\ a_{n1} & a_{n2} & \dots & a_{nn} \\ \end{pmatrix} $$ To solve this system of equations, we first form the augmented \( n \times (n+1) \) matrix by adding the column of \(b's\) to the matrix of coefficients: $$ \begin{pmatrix} a_{11} & a_{12} & \dots & a_{1n} & b_1 \\ a_{21} & a_{22} & \dots & a_{2n} & b_2 \\ \vdots & \vdots & \vdots & \vdots & \vdots \\ a_{n1} & a_{n2} & \dots & a_{nn} & b_n \\ \end{pmatrix} $$ The next step is to "transform" the augmented matrix into one where the matrix-of-coefficients part is an upper triangle matrix , that is, all values of this \(n \times n\) matrix below the main diagnol are \(0's\). The result will be a matrix of the form: $$ \begin{pmatrix} c_{11} & c_{12} & \dots & \dots & c_{1n} & d_1 \\ 0 & c_{22} & \dots & \dots & c_{2n} & d_2 \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\ 0 & 0 & \dots & c_{(n-1)(n-1)} & c_{(n-1)n} & d_{n-1} \\ 0 & 0 & \dots & 0 & c_{nn} & d_n \\ \end{pmatrix} $$ Now we can turn this back into a system of equations of the form: $$ \begin{pmatrix} c_{11}x_1 & c_{12}x_2 & \dots & \dots & c_{1n}x_n & d_1 \\ 0 & c_{22}x_2 & \dots & \dots & c_{2n}x_n & d_2 \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\ 0 & 0 & \dots & c_{(n-1)(n-1)}x_{n-1} & c_{(n-1)n}x_n & d_{n-1} \\ 0 & 0 & \dots & 0 & c_{nn}x_{n} & d_n \\ \end{pmatrix} $$ and solve the equations from the bottom up. We solve: $$ c_{nn}x_n = d_n $$ for \(x_n\). Knowing the value of \(x_n\), we can then solve the next-to-last equation: $$ c_{(n-1)(n-1)}x_{n-1} + c_{(n-1)n}x_n = d_{n-1} $$ for \(x_{n-1}\) and so forth, back up to the top row.
This process is solving systems of linear equations is known as Gaussian elimination , named for the famous German mathematician Karl Friedrich Gauss.
But how do we do the transformation? The allowable operations to carry out this transformation are called elementary row operations, none of which change the solution set of the underlying equations. These operations (performed on the augmented matrix) are:
- i. Switch any two rows of the matrix.
- ii. Multiply all the elements in any one row of the matrix by a non-zero scalar.
- iii. Add a scalar multiple of any one row to another row.
In the next section, we will explore Gauss-Jordan Elimination, an advanced variation of Gaussian elimination. Unlike the traditional method, Gauss-Jordan elimination transforms the system into a Reduced Row Echelon Form (RREF), enabling a direct solution without requiring back-substitution.
Gauss-Jordan Elimination
Let's take the system of equations: $$ \begin{aligned} 2x - 3y + z & = -22 \\ 7x + 9y - 3z & = 14 \\ 6x + 7y + 2z & = 91 \end{aligned} $$This system of linear equations can be written in augmented matrix form:
\[ \begin{bmatrix} 2 & -3 & 1 & \vert & -22 \\ 7 & 9 & -3 & \vert & 14 \\ 6 & 7 & 2 & \vert & 91 \end{bmatrix} \]Here, the left part of the matrix represents the coefficients of the variables, while the rightmost column represents the constants on the right-hand side of the equations.
After Applying Gauss-Jordan Elimination, the matrix is transformed into Reduced Row Echelon Form (RREF):
\[ \begin{bmatrix} 1 & 0 & 0 & \vert & -4 \\ 0 & 1 & 0 & \vert & 11 \\ 0 & 0 & 1 & \vert & 19 \end{bmatrix} \] So the solution to this system of equations is \(x = -4, y = 11, z = 19\).Steps for Gauss-Jordan Elimination
Gauss-Jordan Elimination is an extension of Gaussian Elimination that transforms a matrix into the identity matrix, making it easier to extract solutions directly. This method provides a direct solution without requiring back substitution, unlike standard Gaussian Elimination.
- Step 1: Normalize the Pivot Element
- Identify the pivot element at position (i, i).
- Divide the entire row by this pivot to make the leading coefficient 1.
- Step 2: Eliminate Other Entries in the Column
- Modify all rows except the pivot row by subtracting a multiple of the pivot row to make all other values in the column zero.
- Step 3: Repeat for Each Column
- Loop through each column, repeating Step 1 and Step 2, until the matrix is transformed into an identity matrix.
- Final Output:
- The left side of the augmented matrix becomes an identity matrix, while the right side contains the solutions to the system.
Example 1
Solving the system of equations:
x + y = 70
24x + 14y = 1180
using Gaussian elimination, we first form the augmented matrix:
$$
\begin{pmatrix}
1 & 1 & 70 \\
24 & 14 & 1180
\end{pmatrix}
$$
We multiply row 1 by the scalar -24 and add the result to row 2 (the third elementary row operation), giving :
$$
\begin{pmatrix}
1 & 1 & 70 \\
0 & -10 & -500
\end{pmatrix}
$$
We divide row 2 by - 10, giving:
$$
\begin{pmatrix}
1 & 1 & 70 \\
0 & 1 & 50
\end{pmatrix}
$$
We multiply row 2 by -1 and add to row 1, giving:
$$
\begin{pmatrix}
1 & 0 & 20 \\
0 & 1 & 50
\end{pmatrix}
$$
The last row represents the equation:
$$
y = 50
$$
The first row represents the equation:
$$
x = 20
$$
The solution is x = 20, y = 50.
Example 2
Let's apply Gaussian elimination to the system of 3 equations in 3 unknowns shown here: $$ \begin{aligned} 2x - 3y + z & = -22 \\ 7x + 9y - 3z & = 14 \\ 6x + 7y + 2z & = 91 \end{aligned} $$ The augmented matrix is: $$ \begin{pmatrix} 2 & -3 & 1 & -22 \\ 7 & 9 & -3 & 14 \\ 6 & 7 & 2 & 91 \end{pmatrix} $$ A series of elementary row operations, as shown here, will convert the \(3 \times 3\) matrix of coefficients to upper triangular form. First, multiply row 1 by \(\frac{1}{2}\) to produce a 1 in the (1,1) position: $$ \frac{1}{2} \begin{pmatrix} 2 & -3 & 1 & -22 \\ 7 & 9 & -3 & 14 \\ 6 & 7 & 2 & 91 \end{pmatrix} $$ giving: $$ \begin{pmatrix} 1 & -\frac{3}{2} & \frac{1}{2} & -11 \\ 7 & 9 & -3 & 14 \\ 6 & 7 & 2 & 91 \end{pmatrix} $$ Then multiply row 1 by -7 and add it to row 2, giving: $$ \begin{pmatrix} 1 & -\frac{3}{2} & \frac{1}{2} & -11 \\ 0 & \frac{39}{2} & -\frac{13}{2} & 91 \\ 6 & 7 & 2 & 91 \end{pmatrix} $$ Then multiply row 1 by -6 and add it to row 3, giving: $$ \begin{pmatrix} 1 & -\frac{3}{2} & \frac{1}{2} & -11 \\ 0 & \frac{39}{2} & -\frac{13}{2} & 91 \\ 0 & 16 & -1 & 157 \end{pmatrix} $$ Now multiply row 2 by \(\frac{2}{39}\) to produce a 1 in the (2,2) position: $$ \begin{pmatrix} 1 & -\frac{3}{2} & \frac{1}{2} & -11 \\ 0 & 1 & -\frac{1}{3} & \frac{14}{3} \\ 0 & 16 & -1 & 157 \end{pmatrix} $$ multiply row 2 by -16 and add it to row 3: $$ \begin{pmatrix} 1 & -\frac{3}{2} & \frac{1}{2} & -11 \\ 0 & 1 & -\frac{1}{3} & \frac{14}{3} \\ 0 & 0 & \frac{13}{3} & \frac{247}{3} \end{pmatrix} $$ divide row 3 by \(\frac{13}{3}\), giving: $$ \begin{pmatrix} 1 & -\frac{3}{2} & \frac{1}{2} & -11 \\ 0 & 1 & -\frac{1}{3} & \frac{14}{3} \\ 0 & 0 & 1 & 19 \end{pmatrix} $$ multiply row 3 by \(\frac{1}{3}\), add to row 2, giving: $$ \begin{pmatrix} 1 & -\frac{3}{2} & \frac{1}{2} & -11 \\ 0 & 1 & 0 & 11 \\ 0 & 0 & 1 & 19 \end{pmatrix} $$ multiply row 3 by \(-\frac{1}{2}\) and add to row 1, multiply row 2 by \(\frac{3}{2}\) and add to row 1. $$ \begin{pmatrix} 1 & 0 & 0 & -4 \\ 0 & 1 & 0 & 11 \\ 0 & 0 & 1 & 19 \end{pmatrix} $$ The bottom row represents the equation: $$ z = 19 $$ The second row represents the equation: $$ y = 11 $$ Finally, from the top row: $$ x = -4 $$ So the solution to this system of equations is \(x = -4, y = 11, z = 19\).Practice
(1) Solve the following system of equations using Gauss-Jordan Elimination3x - 5y = 5 7x + y = 37
Application: Create Matrix Inverse
$$ A = \begin{pmatrix} 1 & 3 \\ 2 & 2 \\ \end{pmatrix} $$ Please find the inverse of \(A\) : \(A^{-1}\)Append Identify matrix to original matrix: $$ \begin{pmatrix} 1 & 3 & 1 & 0 \\ 2 & 2 & 0 & 1 \\ \end{pmatrix} $$ multiply row 1 by -2 and add to row 2, giving: $$ \begin{pmatrix} 1 & 3 & 1 & 0 \\ 0 & -4 & -2 & 1 \\ \end{pmatrix} $$ divide row 2 by -4, giving: $$ \begin{pmatrix} 1 & 3 & 1 & 0 \\ 0 & 1 & \frac{1}{2} & -\frac{1}{4} \\ \end{pmatrix} $$ multiply row 2 by -3 and add to row 1, giving: $$ \begin{pmatrix} 1 & 0 & -\frac{1}{2} & \frac{3}{4} \\ 0 & 1 & \frac{1}{2} & -\frac{1}{4} \\ \end{pmatrix} $$ $$ A^{-1} = \begin{pmatrix} -\frac{1}{2} & \frac{3}{4} \\ \frac{1}{2} & -\frac{1}{4} \\ \end{pmatrix} $$
Practice
(1) Please find the inverse of matrix A: $$ \begin{pmatrix} -1 & 2 & -3 \\ 2 & 1 & 0 \\ 4 & -2 & 5 \end{pmatrix} $$Gauss-Jordan Elimination Algorithm
for each row i: divisor = matrix[i][i] //matrix[i][i] is the pivot element //This step divides the entire row by the pivot to make the pivot element 1. for each column j in row i: matrix[i][j] /= divisor //Make all other elements in the column zero using row operations. for each row j not equal to i: multiplier = -matrix[j][i] for each column k in row j: matrix[j][k] = matrix[j][k] + multiplier*matrix[i][k]