Linear Algebra

Linear Systems
Summary

Vector Spaces
Summary

Maps Between Spaces
Summary

Determinants
Summary

Similarity
Summary

Linear Systems

Solving Linear Systems
Summary

Linear Geometry of n-Space
Summary

Reduced Echelon Form
Summary

Topics about Linear Systems
Summary

Vector Spaces

Content

Maps Between Spaces

Content

Determinants

Content

Similarity

Content

Solving Linear Systems

Systems of linear equations are common in science and mathematics. These two examples from high school science (O'Nan 1990) 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.

Linalg balance 1.pngLinalg balance 2.png

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.

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

20ad415c0f6aa0885ffb9a572d1c7ee6.png

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

87e80184d4d73c0bb49cebfba14e3edf.png

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 shows how to solve any such system.

Gauss' Method
Summary

Describing the Solution Set
Summary

General = Particular + Homogenous
Summary

Comparing Set Descriptions
Summary

Automation
Summary

Linear Geometry of n-Space

Content

Reduced Echelon Form

Content

Topics about Linear Systems

Computer Algebra Systems
Summary

Input-Output Analysis
Summary

Accuracy of Computations
Summary

Analyzing Networks
Summary

Speed of Gauss' Method
Summary

Computer Algebra Systems

Content

Input-Output Analysis

Content

Accuracy of Computations

Content

Analyzing Networks

Content

Speed of Gauss' Method

Content

Gauss' Method

Definition 1.1

A linear equation in variables x1 , x2 , ... , xn has the form

a_1x_1+a_2x_2+a_3x_3+cdots+a_nx_n=d

where the numbers a1 , a2 , ... , an ∈ ℜ are the equation's coefficients and d ∈ ℜ is the constant. An n-tuple (s1 , s2 , ... , sn) ∈ ℜ is a solution of, or satisfies, that equation if substituting the numbers s1 , ... , sn for the variables gives a true statement:

a_1s_1+a_2s_2+ldots+a_ns_n=d

A system of linear equations

begin{array}{*{4}{rc}r} a_{1,1}x_1 &+ &a_{1,2}x_2 &+ &cdots &+ &a_{1,n}x_n &= &d_1 a_{2,1}x_1 &+ &a_{2,2}x_2 &+ &cdots &+ &a_{2,n}x_n &= &d_2 & & & & & & &vdots a_{m,1}x_1 &+ &a_{m,2}x_2 &+ &cdots &+ &a_{m,n}x_n &= &d_m end{array}

has the solution (s1 , s2 , ... , sn) if that n-tuple is a solution of all of the equations in the system.


Example 1.2

The ordered pair (-1 , 5) is a solution of this system

begin{array}{*{2}{rc}r} 3x_1 &+ &2x_2 &= &7 -x_1 &+ &x_2 &= &6 end{array}

In contrast, (5 , -1) is not a solution.


Finding the set of all solutions is solving the system. No guesswork or good fortune is needed to solve a linear system. There is an algorithm that always works. The next example introduces that algorithm, called Gauss' method. It transforms the system, step by step, into one with a form that is easily solved.

Example 1.3

To solve this system

begin{array}{*{3}{rc}r} & & & &3x_3 &= &9 x_1 &+ &5x_2 &- &2x_3 &= &2 frac{1}{3}x_1 &+ &2x_2 & & &= &3 end{array}

we repeatedly transform it until it is in a form that is easy to solve.

begin{array}{rcl} quad &xrightarrow[]{ text{swap row 1 with row 3} } &begin{array}{*{3}{rc}r} frac{1}{3}x_1 &+ &2x_2 & & &= &3 x_1 &+ &5x_2 &- &2x_3 &= &2 & & & &3x_3 &= &9 end{array} &xrightarrow[]{ text{multiply row 1 by 3} } &begin{array}{*{3}{rc}r} x_1 &+ &6x_2 & & &= &9 x_1 &+ &5x_2 &- &2x_3 &= &2 & & & &3x_3 &= &9 end{array} &xrightarrow[]{ text{add }-1text{ times row 1 to row 2} } &begin{array}{*{3}{rc}r} x_1 &+ &6x_2 & & &= &9 & &-x_2 &- &2x_3 &= &-7 & & & &3x_3 &= &9 end{array} end{array}

The third step is the only nontrivial one. We've mentally multiplied both sides of the first row by -1, mentally added that to the old second row, and written the result in as the new second row.

Now we can find the value of each variable. The bottom equation shows that x3 = 3. Substituting 3 for x3 in the middle equation shows that x2 = 1. Substituting those two into the top equation gives that x1 = 3 and so the system has a unique solution: the solution set is { ( 3 , 1 , 3 ) }.


Most of this subsection and the next one consists of examples of solving linear systems by Gauss' method. We will use it throughout this book. It is fast and easy. But, before we get to those examples, we will first show that this method is also safe in that it never loses solutions or picks up extraneous solutions.


Theorem 1.4 (Gauss' method)

If a linear system is changed to another by one of these operations

  1. an equation is swapped with another
  2. an equation has both sides multiplied by a nonzero constant
  3. an equation is replaced by the sum of itself and a multiple of another

then the two systems have the same set of solutions.


Each of those three operations has a restriction. Multiplying a row by 0 is not allowed because obviously that can change the solution set of the system. Similarly, adding a multiple of a row to itself is not allowed because adding -1 times the row to itself has the effect of multiplying the row by 0. Finally, swapping a row with itself is disallowed to make some results in the fourth chapter easier to state and remember (and besides, self-swapping doesn't accomplish anything).


Proof

We will cover the equation swap operation here and save the other two cases for Problem 14.

Consider this swap of row i with row j

begin{array}{*{4}{rc}r} a_{1,1}x_1 &+ &a_{1,2}x_2 &+ &cdots &&a_{1,n}x_n &= &d_1 & & & & & & &vdots a_{i,1}x_1 &+ &a_{i,2}x_2 &+ &cdots &&a_{i,n}x_n &= &d_i & & & & & & &vdots a_{j,1}x_1 &+ &a_{j,2}x_2 &+ &cdots &&a_{j,n}x_n &= &d_j & & & & & & &vdots a_{m,1}x_1 &+ &a_{m,2}x_2 &+ &cdots &&a_{m,n}x_n &= &d_m end{array} xrightarrow[]{} begin{array}{*{4}{rc}r} a_{1,1}x_1 &+ &a_{1,2}x_2 &+ &cdots &&a_{1,n}x_n &= &d_1 & & & & & & &vdots a_{j,1}x_1 &+ &a_{j,2}x_2 &+ &cdots &&a_{j,n}x_n &= &d_j & & & & & & &vdots a_{i,1}x_1 &+ &a_{i,2}x_2 &+ &cdots &&a_{i,n}x_n &= &d_i & & & & & & &vdots a_{m,1}x_1 &+ &a_{m,2}x_2 &+ &cdots &&a_{m,n}x_n &= &d_m end{array}

The n-tuple (s1, s2, ... , sn) satisfies the system before the swap if and only if substituting the values, the s's, for the variables, the x's, gives true statements:

a_{1,1}s_1+a_{1,2}s_2+cdots+a_{1,n}s_n=d_1

and ...

a_{i,1}s_1+a_{i,2}s_2+cdots+a_{i,n}s_n=d_i

and ...

a_{j,1}s_1+a_{j,2}s_2+cdots+a_{j,n}s_n=d_j

and ...

a_{m,1}s_1+a_{m,2}s_2+cdots+a_{m,n}s_n=d_m

This is exactly the requirement that (s1 , s2 , ... , sn) solves the system after the row swap.


Definition 1.5

The three operations from Theorem 1.4 are the elementary reduction operations, or row operations, or Gaussian operations. They are swapping, multiplying by a scalar or rescaling, and pivoting.


When writing out the calculations, we will abbreviate "row i" by "ρi". For instance, we will denote a pivot operation by kρi + ρj, with the row that is changed written second. We will also, to save writing, often list pivot steps together when they use the same ρi.



Title
Summary

Describing the Solution Set

Content

General = Particular + Homogenous

Content

Comparing Set Descriptions

Content

Automation

Content

Title

Content