Linear Algebra/Systems of Linear Equations: Wikis

Note: Many of our articles have direct quotes from sources you can cite, within the Wikipedia article! This article doesn't yet, but we're working on it! See more info or our list of citable articles.

Wikibooks

Up to date as of January 23, 2010

Systems of Linear Equations

An important problem in Linear Algebra is in solving the system of m linear equations of n variables in a field F:

a11x1 + a12x2 + ... + a1nxn = b1
a21x1 + a22x2 + ... + a2nxn = b2
...
am1x1 + am2x2 + ... + amnxn = bm.

Where all aij are elements of a field.

An example of a system of linear equations is: Linear system (2):

2x1x2 + 1.5x3 = 8
x1 − 4x3 = − 7

A solution of the system is a list $\left(s_1,s_2,...,s_n\right)$ of numbers that makes each equation true, when the values s1,s2,... sn are substituted for x1,...,xn respectively. For example, $\left(5,6.5,3\right)$ is a solution to the system (2) because, when these values are substituted in (2) for x1,x2,x 3 respectively, the equations simplify to 8 = 8 and − 7 = − 7.

The set of all possible solutions is called the solution set of the linear system. Two linear systems are called equivalent if they have the same solution set. That is, each solution of the first system is a solution to the second system, and vice versa.

Finding the solution set of a system ot two linear equations in two variables is easy because it is the same as finding the intersection point of two lines. A typical problem is

x1 − 3x2 = − 1
x1 + 4x2 = 3

The graphs of these lines, which we denote by l1 and l2. A pair of numbers $\left(x_1,x_2\right)$ statisfies both equations in the system if and only if the point $\left(x_1,x_2\right)$ lies on both l1 and l2. In the system above, the solution is the single point $\left(5,2\right)$, as you easily can see on Figure 1.

Figure 1: Exactly one solution

Of course, two lines do not have to intersect in a single point, they could be parallel, or they could coincide and "intersect" at every point on the line. Figure 2 and Figure 3 shows graphs to visualize this.

Figure 2: No solution
Figure 3: Infinitely many solutions

A system of linear equations is said to be consistent if it has either one solution or infinitely many solutions, and a systems is said to be inconsistent if it has no solution.

In Linear Algebra, we are concerned with three problems:

1. Is a system of linear equations consistent or not?
2. If so, how many elements are in the solution set?
3. What is the solution set?

Motivation

Systems of linear equations are common in science and mathematics. These two examples from high school science [1] give a sense of how they arise.

The first example is from Physics. Suppose that we are given three objects, one with a mass known to be 2 kg, and are asked to find the unknown masses. Suppose further that experimentation with a meter stick produces these two balances.

Since the sum of moments on the left of each balance equals the sum of moments on the right (the moment of an object is its mass times its distance from the balance point), the two balances give this system of two equations.

40h + 15c = 100
25c = 50 + 50h

The second example of a linear system is from Chemistry. We can mix, under controlled conditions, toluene C7H8 and nitric acid HNO3 to produce trinitrotoluene C7H5O6N3 along with the byproduct water (conditions have to be controlled very well, indeed— trinitrotoluene is better known as TNT). In what proportion should those components be mixed? The number of atoms of each element present before the reaction

$x\,{\rm C}_7{\rm H}_8\ +\ y\,{\rm H}{\rm N}{\rm O}_3 \longrightarrow z\,{\rm C}_7{\rm H}_5{\rm O}_6{\rm N}_3\ +\ w\,{\rm H}_2{\rm O}$

must equal the number present afterward. Applying that principle to the elements C, H, N, and O in turn gives this system.

$\begin{matrix} 7x = 7z \ 8x +1y = 5z+2w \ 1y = 3z \ 3y = 6z+1w \end{matrix}$

To finish each of these examples requires solving a system of equations. In each, the equations involve only the first power of the variables. This chapter gives an introduction to systems of linear equations. We will solve them later.

Matrix Notation

The essential information of a linear system can be described in a rectangular array called a matrix. Given the system

3x1 + 5x2 + 2x3 = 0
x1 − 8x2 = 10
− 2x2 + x3 = − 8

with the coefficients of each variable aligned in columns, we make a matrix called the coefficient matrix (or matrix of coeffients) of the system. The coefficient matrix looks like this

$\begin{bmatrix}3 && 5 && 2 \\ 1 && -8 && 0 \\ 0 && -2 && 1\end{bmatrix}$

Which make sense if you look at the definition of a linear equation (1). The second row contains a zero because the second equation could be written as x1 − 8x2 + 0x3 = 10

We also have a matrix called the augmented matrix which for the same system looks like this

$\begin{bmatrix}3 && 5 && 2 && 0\\ 1 && -8 && 0 && 10\\ 0 && -2 && 1 && -8\end{bmatrix}$

An augmented matrix of a system consists of the coefficient matrix with an added column containing the constants from the right sides of the equation. Again look at the linear equation definition (1), if it does not make sense.

The size of a matrix tells us how many rows and columns it has. The augmented matrix above has 3 rows and 4 columns, therefore it is called a 3x4 (read "3 by 4") matrix. m and n are positive integers, an m x n matrix is a rectangular array of numbers with m rows and n columns. Matrix notation will simplify the calculations of a linear system.

Elementary Row Operations

There are three elementary row operations:

1. Replacement
2. Interchanging
3. Scaling

The following are an explanation and examples of the three different operations. In the chapter Systems of Linear Equations we have used all of these operations, except Scaling.

An important thing to remember is that all operations can be used on all matrices, not just on matrices derived from linear systems.

Replacement

Replace one row by the sum of itself and a multiple of another row. A more common paraphrase of row replacement is "Add to one row a multiple of another row."

An example is, we are given the linear system:

x1 + 4x2 = 3
2x1 + 2x2 = 4

Which can be written in matrix notation, as an augmented matrix, like this

$\begin{bmatrix}1 && 4 && 3 \\ 2 && 2 && 4\end{bmatrix}$

Now we have decided to eliminate the x1 term in equation 2, this can be done by adding -2 times equation 1 to equation 2

$\begin{matrix}-2*[equation\ 1]: & -2x_1-8x_2=-6 \\ \underline{+[equation\ 2]:} & \underline{2x_1+2x_2=4} \\ \left[new\ equation\ 2\right]: & -6x_2=-2\end{matrix}$

Which gives us the matrix

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

Interchanging

Interchange two rows.

An example is, we are given the matrix

$\begin{bmatrix}1 && 2 && 3 \\ 2 && 3 && 1\end{bmatrix}$

Here we have performed an interchange operation on the two rows

$\begin{bmatrix}2 && 3 && 1 \\ 1 && 2 && 3\end{bmatrix}$

This is a useful operation when you are trying to solve a linear system, and can see that it will be easier to solve it by interchanging two rows. It is a widely used operation, even though it seems odd and not very usable.

Scaling

Multiply all entries in a row by a nonzero constant.

An example is, we are given the matrix

$\begin{bmatrix}1 && 2 && 3 \\ 2 && 3 && 1\end{bmatrix}$

Now a scaling operation has been performed on the first row, by multiplying by -2

$\begin{bmatrix}-2 && -4 && -6 \\ 2 && 3 && 1\end{bmatrix}$

Solving a Linear System

The basic strategy for solving a linear systems is to replace one system with an equivalent system (i.e. another system with the same solution set) that is easier to solve. This is done by using x1 term from the first equation to eliminate the x1 terms in the other equations, use the x2 term from the second equation to eliminate the x2 terms in the other equations, and so forth, until you get a very simple equivalent system of equations. There are three operations that are used to simplify a system. You can replace one equation by the sum of itself and a multiple of another equation, we can interchange two equations, and multiply all the terms in an equation with a nonzero constant. During this example, we can see why these operations do not change the solution set of a system.

Example 1: Solve this linear system

x1 − 2x2 + x3 = 0
2x2 − 8x3 = 8
− 4x1 + 5x2 + 9x3 = − 9

The augmented matrix for this system is

$\begin{bmatrix}1 && -2 && 1 && 0 \\ 0 && 2 && -8 && 8 \\ -4 && 5 && 9 && -9\end{bmatrix}$

The first thing we want is keep x1 in the first equation and eliminate it from the other equations.

To achieve this, we add 4 times equation 1 to equation 3.

$\begin{matrix}4*[equation\ 1]: & 4x_1-8x_2+4x_3=0 \\ \underline{+ [equation\ 3]:} & \underline{-4x_1+5x_2+9x_3=-9} \\ \left[new\ equation\ 3\right]: & -3x_2+13x_3=-9 \end{matrix}$

The result of this calculation is written in place of the original equation 3

$\begin{matrix}x_1-2x_2+x_3=0 \\ 2x_2-8x_3=8 \\ -3x_2+13x_3=-9\end{matrix} \qquad \begin{bmatrix}1 && -2 && 1 && 0 \\ 0 && 2 && -8 && 8 \\ 0 && -3 && 13 && -9\end{bmatrix}$

Next thing we want to do is to multiply equation 2 with $\frac{1}{2}$ to obtain 1 as the coefficient for x2, which will simplify arithmetic in the next step

$\begin{matrix}x_1-2x_2+x_3=0 \\ x_2-4x_3=4 \\ -3x_2+13x_3=-9\end{matrix} \qquad \begin{bmatrix}1 && -2 && 1 && 0 \\ 0 && 1 && -4 && 4 \\ 0 && -3 && 13 && -9\end{bmatrix}$

Now, we use x2 in equation 2 to eliminate the − 3x2 in equation 3

$\begin{matrix}3*[equation\ 2]: & 3x_2-12x_3=12 \\ \underline{+ [equation\ 3]:} & \underline{-3x_2+13x_3=-9} \\ \left[new\ equation\ 3\right]: & x_3=3\end{matrix}$

The new linear system has a triangular form, which is called echelon form, and looks like this

$\begin{matrix}x_1-2x_2+x_3=0 \\ x_2-4x_3=4 \\ x_3=3\end{matrix} \qquad \begin{bmatrix}1 && -2 && 1 && 0 \\ 0 && 1 && -4 && 4 \\ 0 && 0 && 1 && 3\end{bmatrix}$

The next step is to use x3 in equation 3 to eliminate the x3 and − 4x3 in equation 1 and 2.

$\begin{matrix}-1*[equation\ 3]: & -x_3=-3 \\ \underline{+[equation\ 1]:} & \underline{x_1-2x_2+x_3=0} \\ \left[new\ equation\ 1\right]: & x_1-2x_2=-3\end{matrix} \qquad \qquad \begin{matrix}4*[equation\ 3]: & 4x_3=12 \\ \underline{+[equation\ 2]:} & \underline{x_2-4x_3=4} \\ \left[new\ equation\ 2\right]: & x_2=16\end{matrix}$

The system now looks like this

$\begin{matrix}x_1-2x_2=-3 \\ x_2=16 \\ x_3=3\end{matrix} \qquad \begin{bmatrix}1 && -2 && 0 && -3 \\ 0 && 1 && 0 && 16 \\ 0 && 0 && 1 && 3\end{bmatrix}$

Now we are just one step away from obtaining the solution of the linear system. The last step is to add 2 times equation 2 to equation 1. When doing so we obtain the linear system, which has a reduced echelon form

$\begin{matrix}x_1 = 29 \\ x_2=16 \\ x_3=3\end{matrix} \qquad \begin{bmatrix}1 && 0 && 0 && 29 \\ 0 && 1 && 0 && 16 \\ 0 && 0 && 1 && 3\end{bmatrix}$

Now that the linear system is solved, it shows that the only solution of the original system is (29,16,3). However, because of the many calculations involved, it is a good practice to check you work. This is done by substituting the solution into the original system

(29) − 2(16) + (3) = 29 − 32 + 3 = 0
2(16) − 8(3) = 32 − 24 = 8
− 4(29) + 5(16) + 9(3) = − 116 + 80 + 27 = − 9

This shows us that the solution we found is right, and therefore is a solution of the original linear system.

References

1. Onan, Linear Algebra