Systems of Lnear Equations

> restart:with(linalg):with(plots):

Warning, new definition for norm

Warning, new definition for trace

Linear Equations/Systems

Linear Equations

Definition : Any equation in the n variables , ... that can be written in the form + ... + where the 's are (Real) constants is called a linear equation.

e.g. the following are all linear equations:

> 2*x[1]+3*x[2]=1;x-3*y+z=14;y-3=0;y+w=x-1/3*z;

e.g. the following are not linear equations:

> x+y^2=1;3*x+y^(-1)=2;x+sqrt(y)+z=0;x*y+z=-1;sin(x)+cos(y)=1;

Definition : A solution of linear equation + ... + is any sequence of numbers ,..., such that + ... + is a true statement .

> e1:=9*x-3*y=2;

> S:=solve(e1);

> seq(subs(x=t,S),t=-1..3);

It should be clear that a solution to e1 is any point on the line . The solution set of e1 (or any linear equation is the set of all possible solutions . Hence, for e1, the solution set consists of all the points on the line pictured below.

> implicitplot(e1,x=-1..1,y=-1..1);

aside: an equivalent way of writing the solution to e1, and one more in keeping with one of the ways we will be writing solutions would be as below. Can you see it is equivalent??

> x=1/3*t+2/9;y=t;

Definition : A system of linear equations (a "linear system") is a finite set of linear equations. A solution to a linear system is any sequence of numbers that satisfies all the equations in the system.

e.g. show that (2,1) is a solution to the linear system:

> e1:=x-y=1;e2:=2*x+y=5;

> subs({x=2,y=1},{e1,e2});

e.g. Show that is a solution to the system {eq1,eq2}for every possible value of t :

> eq1:=8*x+y+4*z=-1;eq2:=-2*x+5*y+2*z=1;

> subs({x = -1/7-3*t/7, y = 1/7-4*t/7, z = t},{eq1,eq2});

> P1:=implicitplot3d(eq1,x=-2..2,y=-2..2,z=-2..2,colour=red):

> P2:=implicitplot3d(eq2,x=-2..2,y=-2..2,z=-2..2,axes=framed,colour=grey):

> display({P1,P2},title=`Two planes will intersect along a line.`);

Straight Line Systems

> e1;e2;

> implicitplot({e1,e2},x=-1..3,y=-2..2);solve({e1,e2});

Note: the system {e1,e2} has exactly one solution and (geometrically) it consists of the intersection point between the two lines.

> e3:=x+y=1;e4:=x+y=3;e5:=x-y=1;

> implicitplot({e3,e4,e5},x=-1..3,y=-2..2,colour=black,thickness=2);

Note: the system {e3,e4,e5} has no solution since, as the plots above show, there is no one point that is common to all three equations.

> e6:=x-y=-1;e7:=3*x-3*y=-3;

> implicitplot({e6,e7},x=-2..2,y=-2..2,thickness=2);

Note: the system {e6,e7} has infinitely many solutions and geometrically consists of two lines with the same slope and intercepts.

The preceeding three examples motivate the following

Important Generalization : Every linear system has either no solution, exactly one solution or infinitely many solutions. We will prove this statement later in the course. A LS with not solution is called " inconsistent. "

Solving a Linear System

Linear Systems can be solved many different ways. Our first method will involve working with what we can call the augmented matrix associated with the system. As an example, consider the LS of three equations in three unknowns below.

> eq1:=4*x+5*y+6*z=24;eq2:=3*x+y-2*z=4;eq3:=x+2*y+3*z=9;

> A:=genmatrix([eq1,eq2,eq3],[x,y,z],flag);

The rectangular array called 'A' above is the augmented matrix of the system. It should be obvious how to extend this notion to any LS of equations. The only rule that the Rulers of the Universe insist on is that when writing out the augmented matrix of a system all the equations are written in the same way : the variables in the same order left to right with the constant terms isolated on the right hand side of the equals sign. In this way there can be no confusion as to what the augmented matrix of a given system should be.

The main idea behind solving a given LS is to replace the given LS by another one which has the same solution set as the original one but is trivial to solve.

The manner in which we will produce equivalent LS's (ones with the same solution set) will be through using elementary row operations (ERO's) on the augmented matrix. It should be borne in mind that ERO's are really elementary equation operations since the rows of an augmented matrix each correspond in a one-to-one fashion with the equations on the LS.

Below are the three allowed ERO's (and there are no more!):

1) Multiply a row (equation) by a nonzero constant

2) Interchange two rows (equations)

3) Add a multiple of one row (equation) to another row (equation)

Warning: The third ERO above does not read "Add a multiple of one row (equation) to a multiple of another row (equation)." Make sure you understand the difference. This incorrect version really involves two ERO's in sequence.

Gauss and Gauss-Jordan elimination

A matrix is in reduced row echelon form (RREF) if:

1) The first nonzero entry in any row is a one (called a "leading 1" -- columns that contain a leading 1 identify the "leading variables")

2) "Zero rows" (rows consisting only of zeros) are all at the bottom of the matrix

3) In any two successive nonzero rows, the leading 1 in the lower row is further to the right than the leading 1 in the higher row.

4) Each column that contains a leading 1 has zeros above the leading 1.

If only the first three criteria are satisfied then the matrix is in row echelon form (REF).

Below are the augmented matrices of 4 LS's in RREF. Translate each back into a system of linear equations.

> M1:=matrix(4,4,[1,2,-1,1,0,0,1,3,0,0,0,0,0,0,0,0]);M2:=matrix(2,3,[1,0,1,0,1,2]);M3:=matrix(2,2,[0,0,0,0]);M4:=matrix(3,4,[1,2,0,0,0,0,1,0,0,0,0,1]);

Each column (except the last) with a leading 1 in an augmented matrix represents a leading variable and each (except the last) without a leading 1 represents a nonleading variable which becomes a (free) parameter in the solution. Identify the leading and nonleading variables in the above systems.

In Gauss-Jordan Elimination the augmented matrix of the given LS is transformed by a sequence of ERO's into a matrix in RREF from which the solution can be read off.

Solev the system below by Gauss-Jordan elimination:

> e1:=x+y+2*z=9;e2:=2*x+4*y-3*z=1;e3:=3*x+6*y-5*z=0;

> A:=genmatrix([e1,e2,e3],[x,y,z],flag);

> A1:=addrow(A,1,2,-2); # add -2*R1 to R2

> A2:=addrow(A1,1,3,-3); # add -3*R1 to R3

> A3:=addrow(A2,2,3,-1);A4:=swaprow(A3,2,3);

> A5:=pivot(A4,2,2); # "pivot" is a shortcut Maple command for using ERO's to make the entries above and below the (2,2) entry zeros.

> A6:=pivot(A5,3,3);

From A6 it should be clear that the solution is x = 1, y = 2, z = 3.

> solve({e1,e2,e3});

As a shortcut we could have used the following Maple command:

> gaussjord(A);

e.g. Solve the LS represented by the following augmented matrix A

Write out the LS represented by A, find the general solution and atleast three particular solutions.

> A:=matrix(3,4,[1,2,-1,2,2,5,2,-1,7,17,5,-1]);gaussjord(A);

> solution:=[12+9*t,-5-4*t,t];

solution: x = 12 +9t, y = -5 - 4t, z = t

To get particular solutions we just choose different values for t . Below we get the solutions for t = 0, 1, 2:

> seq(solution,t=0..2);

e.g. Solve the LS

> e1:=x+y+z=1;e2:=-x+y+z=-1;e3:=2*x+3*y+3*z=1;

> B:=genmatrix([e1,e2,e3],[x,y,z],flag);

> gaussjord(B);

> solve({e1,e2,e3});

Solution: None! Note that the last row above "says" that 0x + 0y + 0z = 1 and that can never be true. The LS is inconsistent .

e.g. A box of money

A box contains pennies, nickels and dimes for a total of 83 cents and 13 coins. Use the techniques of the course to determine the number of each.

> eq1:=x+y+z=13;eq2:=x+5*y+10*z=83;

> C:=genmatrix([eq1,eq2],[x,y,z],flag);

> gaussjord(C);

> sols:=[-9/2+5/4*t,35/2-9/4*t,t];

> seq(sols,t=1..13);

We can see that the only sensible solution occurs for t = 6 which yields 3 pennies, 4 nickels and 6 dimes.

> solve({eq1,eq2});

Gauss Elimination

In the technique called Gauss Elimination the augmented matrix of the LS is put into REF . The correspondng equations are then written out and the solution arrived at using "back substitution." See your text for an explanation.