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 \begin{bmatrix} s_1 \\ s_2 \\ … \\ s_n \end{bmatrix}

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 \begin{bmatrix} 13 \\ 5 \\ 7 \end{bmatrix}

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:

\begin{bmatrix} a_{11} & \dots & a_{1n} & |&  b_1 \\  \dots &  \dots &  \dots & | &  \dots \\ a_{m1} &  \dots & a_{mn} & | & b_m \end{bmatrix}

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.

\begin{bmatrix} 1 & 1 & -2 & | & 4 \\ 1 & 3 & -1 & | & 7 \\ 2 & 1 & -5 & | & 7 \end{bmatrix}

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

\begin{bmatrix} 1 & 1 & -2 & | & 4 \\ 0 & -2 & -1 & | & -3 \\ 2 & 1 & -5 & | & 7 \end{bmatrix}

Then, subtract 2 times row 1 by row 2.

\begin{bmatrix} 1 & 1 & -2 & | & 4 \\ 0 & -2 & -1 & | & -3 \\ 0 & 1 & 1 & | & 1 \end{bmatrix}

Next, add row 2 to 2 times row 3.

\begin{bmatrix} 1 & 1 & -2 & | & 4 \\ 0 & -2 & -1 & | & -3 \\ 0 & 0 & -1 & | & -1 \end{bmatrix}

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 \begin{bmatrix} 5 \\ 1 \\ 1 \end{bmatrix}. 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:

\begin{bmatrix} a_{11} & a_{12} & a_{13} \\ 0 & a_{22} & a_{23} \\ 0 & 0 & a_{33} \end{bmatrix}

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.

One Reply to “Matrix Representations of Systems”

Leave a Reply

Your email address will not be published. Required fields are marked *