Using Matrices to Solve Linear Systems

A linear system can be solved using matrices. Each row in the matrix represents one linear equation. Each column in the matrix represents a variable in the linear equations.

Transforming a Linear System to a Matrix

Start with the linear system

a11*x+a12*y+a13*z=a14; a21*x+a22*y+a23*z=a24; a31*x+a32*y+a33*z=a34

where amn is a coefficient. Organize the linear system by variable for columns and equations for rows:

blank,x-coefficient,y-coefficient,z-coefficient,value;a11*x,+a12*y,+a13*z,=a14; a21*x,+a22*y,+a23*z,=a24; a31*x,+a32*y,+a33*z,=a34

Now drop the variables and operators and draw matrix brackets around the values:

matrix, row 1: a11,a12,a13,a14; row 2: a21,a22,a23,a24; row 3: a31,a32,a33,a34

Example: Start with the linear system

x-2z=-5; -2x-3y-3z=-12; 2x+2y=2.
Now organize it into rows and columns.
blank, x-coefficient, y-coefficient, z-coefficient, value; row 1: 1x,+0y,+-2z,-5; row 2: -2x,+-3y,+-3z,-12; row 3: 2x,+2y,+0z,2.
Now put the system into matrix notation.
matrix row 1: 1,0,-2,-5; row 2: -2,-3,-3,-12; row 3: 2,2,0,2.

Row Operations

There are row operations that can be done on a matrix that, if done correctly, will help transform the matrix into a solution to the linear system represented by the matrix. These operations are:

  • Scalar multiplication of a row: Any row can be multiplied by any non-zero real number.
  • Row addition: Any row can be added to any other row and the sum be used to replace either row.
  • Trading rows: Any two rows can be swapped.

Scalar Multiplication of a Row

Scalar multiplication of a row is like scalar multiplication of the entire matrix, but it is done to only one row. In the following example, row 1 is multiplied by 2.

matrix row 1: 1,0,-2,-5; row 2: -2,-3,-3,-12; row 3: 2,2,0,2; arrow indicating row 1 times 2; matrix row 1: 2,0,-4,-10; row 2: -2,-3,-3,-12; row 3: 2,2,0,2.
When multiplying rows, it is usually best to use whole numbers whenever possible. This makes later steps in solving the linear system much easier.

Addition of Rows

When adding rows, corresponding elements of each row are added together. The results are placed into either of the rows being added. In the following example, row 1 is added to row 2 and the result placed into row 2.

matrix row 1: 2,0,-4,-10; row 2: -2,-3,-3,-12; row 3: 2,2,0,2; arrow indicating row 1 plus 2 goes into row 2; matrix row 1: 2,0,-4,-10; row 2: 0,-3,-7,-22; row 3: 2,2,0,2.
Note that the first entry in row 2 is now zero. As you will see as you follow this algorithm, this was the goal of the first operations on this matrix.

Swapping Rows

Any two rows in the matrix can be swapped without changing the linear system represented by the matrix. While row swapping is not necessary for solving this sample system, it is demonstrated here by swapping rows 2 and 3.

matrix row 1: 2,0,-4,-10; row 2: -2,-3,-3,-12; row 3: 2,2,0,2; arrow indicating row 1 plus 2 goes into row 2; matrix row 1: 2,0,-4,-10; row 2: 0,-3,-7,-22; row 3: 2,2,0,2.
Row swapping to solve linear system is usually used to move a row with leading zeros into a more convenient spot in the matrix.

Combining Operations

Any of the operations can be combined into a single transformation of the matrix. Be careful though, the more complicated combinations of transformations can lead to errors. Any error will give false results. In the next example, row 1 is multiplied by negative 1 and added to row 2.

matrix row 1: 2,0,-4,-10; row 2: 0,-3,-7,-22; row 3: 2,2,0,2 arrow indicating row 1 times -1 is added to row 2, which goes into row 2; matrix row 1: 2,0,-4,-10; row 2: 0,-3,-7,-22; row 3: 2,2,0,2.

The Algorithm

Each of the steps in this algorithm are completed using the row operations of scalar multiplication of rows, addition of rows, and swapping rows.

The first step in solving a linear equation using a matrix is to get all zeros below the diagonal. The order in which these are conventionally done is illustrated here:

Matrix row 1: a_11,a_12,a_13,a_14; row 2: (1),a_22,a_23,a_24; row 3: (2),(3),a_33,a_34.

The second step is to transform the matrix so that the coefficients in the diagonal are all ones. This is illustrated by the following matrix.

Matrix row 1: 1,a_12,a_13,a_14; row 2: 0,1,a_23,a_24; row 3: 0,0,1,a_34.
This is called row-echelon form. A matrix representing a linear system that is in row-eschelon form can be solved the rest of the way by using back substitution. Solving a matrix this way is called Gaussian elimination.

The third step is to transform the matrix so entries above the diagonal are all zeros. The following matrix illustrates this step.

Matrix row 1: 1,0,0,a_14; row 2: 0,1,0,a_24; row 3: 0,0,1,a_34.
Once the matrix is in this form, called reduced row-echelon form, the solution can be read off the matrix:
Matrix row 1: 1,0,0,a_14; row 2: 0,1,0,a_24; row 3: 0,0,1,a_34 implies x=a14;y=a24;z=a34.
Solving a matrix this way is called Gauss-Jordan elimination.

Example (continued)

Divide both row 1 and row 2 by 2. This makes them easier to work with.

Matrix row 1: 2,0,-4,-10; row 2: 0,2,4,12; row 3: 0,-3,-7,-22 transformed row 1 divide by 2, row 2 divided by 2 gives Matrix row 1: 1,0,-2,-5; row 2: 0,1,2,6; row 3: 0,-3,-7,-22.

Multiply row 2 by 3 and add it to row 3.

Matrix row 1: 1,0,-2,-5; row 2: 0,1,2,6; row 3: 0,-3,-7,-22 transformed row 2 time 3 plus row 3 into row 3 gives Matrix row 1: 1,0,-2,-5; row 2: 0,1,2,6; row 3: 0,0,-1,-4.

Multiply row 3 by -1.

Matrix row 1: 1,0,-2,-5; row 2: 0,1,2,6; row 3: 0,0,-1,-4 transformed row 3 times -1 gives Matrix row 1: 1,0,-2,-5; row 2: 0,1,2,6; row 3: 0,0,1,4.

Multiply row 3 by -2 and add it to row 2 with the result in row 2.

Matrix row 1: 1,0,-2,-5; row 2: 0,1,2,6; row 3: 0,0,1,4 transformed row 3 times -1 gives Matrix row 1: 1,0,-2,-5; row 2: 0,1,0,-2; row 3: 0,0,1,4.

Multiply row 3 by 2 and add it to row 1 with the result in row 1.

Matrix row 1: 1,0,-2,-5; row 2: 0,1,0,-2; row 3: 0,0,1,4 transformed row 3 times -1 gives Matrix row 1: 1,0,0,3; row 2: 0,1,0,-2; row 3: 0,0,1,4.

Read the solution from the matrix.

Matrix row 1: 1,0,0,3; row 2: 0,1,0,-2; row 3: 0,0,1,4  gives x=3,y=-2,z=4.

Classes of Solutions

Exactly one solution: A linear system with exactly one solution will have a diagonal of ones, and the rest zeros except for the rightmost column:

Matrix row 1: 1,0,0,3; row 2: 0,1,0,-2; row 3: 0,0,1,4  gives x=3,y=-2,z=4.

Infinite solutions: A linear system with infinite solutions will have a row of all zeros, and can not be reduced to reduced eschelon form:

Matrix row 1: 1,0,1,3; row 2: 0,1,0,-3; row 3: 0,0,0,0  gives x+z=3,y=-3.

No solution: A linear system with no solution will have a row with all zeros except for the last entry. This is the mathematical statement 0=7, which is impossible. So there is no solution.

Matrix row 1: 1,0,1,3; row 2: 0,1,0,-3; row 3: 0,0,0,7  No solution.

Cite this article as:


Using Matrices to Solve Linear Systems. 2008-12-23. All Math Words Encyclopedia. Life is a Story Problem LLC. http://www.allmathwords.org/en/m/matrixlinearsystem.html.

Translations

Image Credits

Revision History


2008-12-23: Corrected spelling (McAdams, David.)
2008-12-16: Initial version (McAdams, David.)

All Math Words Encyclopedia is a service of Life is a Story Problem LLC.
Copyright © 2005-2011 Life is a Story Problem LLC. All rights reserved.
Creative Commons License This work is licensed under a Creative Commons Attribution-Noncommercial-Share Alike 3.0 License