Tutorials on Advanced Math and Computer Science Concepts

Matrix Representations of Systems

Solving linear systems is a problem core to Linear Algebra. You will notice that so far we have already encountered a few different linear systems. Being able to solve these systems is an important skill, and Linear Algebra provides some helpful techniques to be able to do this.

First, we will start by formally defining what a linear system is. This will allow us to have consistent terminology to discuss how to manipulate and solve them. A linear system is a set of linear equations. A linear equation is an equation written in the form $a_1x_1 + a_2x_2 + ... + a_nx_n = b$, where $a_1, a_2, ..., a_n$ are constants.

We refer to $a_1,a_2,..., a_n$ as the coefficients of the equation. The value b is typically referred to as the right hand side, and the x values are unknowns, or variables. A system has a solution at $x_1 = s_1, x_2 = s_2, ..., x_n = s_n$, which is often displayed as a vector $\left[\begin{array}{cc} s_1 \\ s_2 \\ ... \\ s_n \end{array}\right]$

A system of linear equations is composed of many linear equations as defined above. A general definition would be:

$a_{11}x_{11} + a_{12}x_{12} + ... + a_{1n}x_n = b_1$

$a_{21}x_{21} + a_{22}x_{22} + ... + a_{2n}x_n = b_2$

$a_{n1}x_{n1} + a_{n2}x_{n2} + ... + a_{mn}x_n = b_m$

We want to be able to establish a solution for any system of linear equations. From previous math courses, you likely learned at least one method of solving linear systems. Let's do an example to see one way that we can solve a system.

Example: Find the solution to the linear system
$x_1 + x_2 - 2x_3 = 4$

$x_1 + 3x_2 - x_3 = 7$

$2x_1 + x_2 - 5x_3 = 7$

There are many ways to come to the solution of this system. I will work by eliminating variables by subtracting the equations, allowing us to isolate for single variables.

First, subtract equation 1 from equation 2 to get: $-2x_2 - x_3 = -3$. We will call this equation 4

Next, subtract 2 times equation 2 from equation 3 to get: $5x_3+3x_3 = 7$. We will call this equation 5

Finally, add 3 times equation 4 to equation 5 to get: $-x_2 = -5$. This tells us $x_2 = 5$.

Now, substitute $x_2 = 5$ into equation 4 to get: $-x_3 = 7$, which tells us $x_3 = 7$.

Finally substitute $x_2 = 5$ and $x_3 = 7$ into equation 1 to get: $x_1 + 5 -14 = 4$, which gives us $x_1 = 13$

So, we have a solution as $\left[\begin{array}{cc} 13 \\ 5 \\ 7 \end{array}\right]$

This is one way that we are able to solve systems of linear equations. The general steps we can have when doing elimination are:

  1. Multiply one equation by a non zero constant
  2. Interchange the location of two equations
  3. Add a multiple of one equation to another equation

To be consistent with our vector notation for solutions to a linear system, we also have a matrix representation for a system. This will allow us to more easily keep track of the equations, and in turn solve them more effectively.

If we have a system of equations in the form:

$a_{11}x_{11} + a_{12}x_{12} + ... + a_{1n}x_n = b_1$

$a_{21}x_{21} + a_{22}x_{22} + ... + a_{2n}x_n = b_2$

$a_{n1}x_{n1} + a_{n2}x_{n2} + ... + a_{mn}x_n = b_m$

The following matrix can be used to represent the system:

$\left[\begin{array}{cc} a_{11} & \dots & a_{1n} & |&  b_1 \\ \dots & \dots & \dots & | & \dots \\ a_{m1} & \dots & a_{mn} & | & b_m \end{array}\right]$

We call this matrix an augmented matrix. It contains all of the coefficients of our linear system, as well as the right hand side. We can use this matrix to solve our linear systems, using a process called row reduction. The idea is the exact same as our previous example, we eliminate variables until we get a solution for one of them. The only difference is that our matrix only tracks the coefficients, so we are trying to set the coefficients to 0.

Example: Solve the system of equations

$x_1 + x_2 - 2x_3 = 4$
$x_1 + 3x_2 - x_3 = 7$
$2x_1 + x_2 - 5x_3 = 7$

First, we create the matrix to represent the equation.

$\left[\begin{array}{cc} 1 & 1 & -2 & | & 4 \\ 1 & 3 & -1 & | & 7 \\ 2 & 1 & -5 & | & 7 \end{array}\right]$

Now, we proceed as normal. First, I am going to subtract row 1 by row 2.

$\left[\begin{array}{cc} 1 & 1 & -2 & | & 4 \\ 0 & -2 & -1 & | & -3 \\ 2 & 1 & -5 & | & 7 \end{array}\right]$

Then, subtract 2 times row 1 by row 2.

$\left[\begin{array}{cc} 1 & 1 & -2 & | & 4 \\ 0 & -2 & -1 & | & -3 \\ 0 & 1 & 1 & | & 1 \end{array}\right]$

Next, add row 2 to 2 times row 3.

$\left[\begin{array}{cc} 1 & 1 & -2 & | & 4 \\ 0 & -2 & -1 & | & -3 \\ 0 & 0 & -1 & | & -1 \end{array}\right]$

Now, we have a solution. Since -1 is denoting the $x_3$ coefficient, the last row can be rewritten as $-x_3 = -1$, therefore $x_3 = 1$.

Row 2 can be rewritten as $-2x_2 - x_3 = -3$, so if we substitute in $x_3 = 1$, we get $-2x_2 -1 = -3$, meaning $x_2 = 1$.

Finally, row 3 can be rewritten as $x_1 + x_2 - 2x_3 = 4$, so if we substitute, we get $x_1 + 1 -2 = 4$, meaning $x_1 = 5$.

This gives us a final solution of $\left[\begin{array}{cc} 5 \\ 1 \\ 1 \end{array}\right]$. You can see that this method is rather effective for finding system solutions. Rather than having to create and track two new equations, we simply manipulate what is inside the matrix, only needing to rewrite the matrix each time.

We refer to the final product of the row reduction as a matrix in row echelon form. Row echelon form in general has the following properties.

  1. When all entries in a row are 0, this row appears below all rows containing non zero entries
  2. When two non zero rows are compared, the first non zero entry on the top equation is to the left of the leading entry of the lower row.

This creates a structure that looks like this:

$\left[\begin{array}{cc} a_{11} & a_{12} & a_{13} \\ 0 & a_{22} & a_{23} \\ 0 & 0 & a_{33} \end{array}\right]$

Using the matrix representation of a linear system, we will be able to find some interesting manipulations to solve linear systems quickly and effectively. These sorts of solutions are often used by computer systems that need to implement algorithms to solve linear systems.