Linear Algebra (2009 Fall) Chapter 1 Matrices and Systems of Equationsyi/Courses/LinearAlgebra/LectureNotes... · Linear Algebra Systems of Linear Equations Linear Systems Solutions

Linear Algebra

Linear Algebra (2009 Fall)Chapter 1 Matrices and Systems of Equations

Chih-Wei Yi

Dept. of Computer ScienceNational Chiao Tung University

October 29, 2009

Linear Algebra

Systems of Linear Equations

Linear Systems

Linear Systems

Linear Algebra


Linear Systems

Linear Equations

De�nition (Linear Equations)

A linear equation in n unknowns (variables) x1, x2, ..., xn:

a1x1 + a2x2 + � � �+ anxn = b.

x1, x2, � � � , xn: variables (x1: leading varialbes)a1, a2, � � � , an: constants and called coe¢ cients (a1: leadingcoe¢ cient)

b: constant term

Example

2x + 3y = 6 is a linear equation in 2 unknowns, but y = sin x andxy = 1 are not linear equations.

Linear Algebra


Linear Systems

Examples

Which are linear equations?

2x � 3y = 43x � 4xy = 01x �

2y = 3

x2 + y2 = 1

2 sin x + y = 4

(sin 2) x + y = 10

2x1 + e3x2 = log 5

x2 + 3x + 2 = 0

Linear Algebra


Linear Systems

Solutions of Linear Equations

De�nition (Solutions)

Assume s1, s2, . . . , sn are n real numbers.x1 = s1, x2 = s2, . . . , xn = sn is called a solution of linear equationa1x1 + a2x2 + � � �+ anxn = b if a1s1 + a2s2 + � � �+ ansn = b issatis�ed.

Example

Consider the linear equation: 2x1 + x2 = 4.

x1 = 1 and x2 = 2 is a solution.

For any real number t, x1 = t and x2 = 4� 2t is a solution.(Here t is called a parameter.)

Linear Algebra


Linear Systems

Exercise

Problem

Assume u = (u1, u2, ..., un) and v = (v1, v2, ..., vn) are twosolutions of a1x1 + a2x2 + ...+ anxn = b. Prove that for any realnumber c, u + c(u � v) is a solution ofa1x1 + a2x2 + ...+ anxn = b.

Solution (Hints)

Show that (u � v) is a solution ofa1x1 + a2x2 + ...+ anxn = 0.

Then, you can prove u + c(u � v) is a solution ofa1x1 + a2x2 + ...+ anxn = b.

Linear Algebra


Linear Systems

Linear Systems

De�nition (Linear Systems)

A linear system of m equations in n unknows is a collection of mlinear equations in n common unknowns.8>>><>>>:

a11x1 + a12x2 +...+ a1nxn = b1a21x1 + a22x2 +...+ a2nxn = b2

...am1x1 + am2x2 +...+ amnxn = bm

.

It is called an m� n system. A solution to an m� n system is anordered n-tuple of real numbers (x1, x2, � � � , xn) 1 that satis�es allm equations of the system. The set of all solutions to a linearsystem is called the solution set of the system.

1Here an (ordered) n-tuple of real numbers (x1, x2, � � � , xn) is the same as avector in Rn space.

Linear Algebra


Linear Systems

Example

(1, 0) is a solution of�x1 + 3x2 = 4x1 + x2 = 3

. f(1, 0)g is the solutionsset of the linear system.

Example

(0, 0, 3), (1, 0, 2), and (4, 0,�1) are solutions of�x1 +x2 +x3 = 3x1 +x3 = 3

. Actually, this system has in�nite

solution, and its solution set is f(3� t, 0, t) j t 2 Rg.

Example

The system

8<:x1 +x2 = 32x1 +x2 = 33x1 +x2 = 4

has no solution, so its solution set

is ?.

Linear Algebra


Linear Systems

The Number of Solutions of A Linear System

1 2 3

3

2

1

1

−=−

=+

13

yxyx

=+

=+

6223

yxyx

1 2 3

3

2

1

1

=+

=+

13

yxyx

1 2 3

3

2

1

1

Linear Algebra


Linear Systems

Problem

Prove the number of solutions of a linear system must be one ofthe following cases

1 Exactly 1 solution

2 In�nite number of solutions

3 No solution

(Hint: If u = (u1, u2, � � � , un) and v = (v1, v2, � � � , vn) aresolutions of a linear system in n variables, then for any c 2 R,u+ c (u� v) is also a solution of the system.)

De�nition (Consistent and Inconsistent)

A linear system is inconsistent if its solution set is empty, otherwiseit is consistent.2

2Note: A consistent linear system has either exactly one solution orotherwise in�nite solutions.

Linear Algebra


Gaussian Elimination


Linear Algebra



Row-Echelon Systems

De�nition (Row-Echelon Form)

A system is in row-echelon form if it follows a stair-step patternand has leading coe¢ cients of 1.

1 All variables are aligned.

2 In an equation, the leading coe¢ cient is the coe¢ cient of the�rst variables.

Example

1 7552

43

932

=+−

−=+−

=+−

zyx

yx

zyx

rowechelon formnot rowechelon form

2

53

932

=

=+

=+−

z

zy

zyx

Linear Algebra



Solve a Row-Echelon System

A row-echelon system can be solved by back-substitution.

x � 2y + 3z = 9y + 3z = 5

z = 2row-echelon system

z = 2y = 5� 3z = 5� 3� 2 = �1x = 9+ 2y � 3z = 9+ 2� (�1)� 3� 2 = 1

back-substitution

Linear Algebra




De�nition (Equivalent Systems)

Two systems of linear equations are called equivalent if they haveprecisely the same solution set.

Operations producing equivalent systems

1 Interchange two equations.2 Multiply an equation by a nonzero constant.3 Add a multiple of an equation to another equation.

Gaussian elimination: rewrite a system to an equivalentrow-echelon system by a sequence of these three operations.

Linear Algebra



Solve a System of Linear Equations

17552

43

932

=+−

−=+−

=+−

zyx

yx

zyx

17552

53

932

=+−

=+

=+−

zyx

zy

zyx

1

53

932

−=−−

=+

=+−

zy

zy

zyx

42

53

932

=

=+

=+−

z

zy

zyx

2

53

932

=

=+

=+−

z

zy

zyx After applying backsubstitution , we havex = 1, y = 1, z = 2.

Linear Algebra



An mxn Matrix

mnmm

n

n

aaa

aaa

aaa

L

MOMM

L

L

21

22221

11211

m rows

n columns

1st row

2nd row

mst row

1st column nst column

Linear Algebra



Represent a Linear System by a Matrix

1752

43

932

=+

−=+−

=+−

zx

yx

zyx

−

−

502031321

−−

−

175024031

9321

system

coefficient matrix

augmented matrix

Linear Algebra



Elementary Row Operations

Interchange two rows.

Multiply a row by a nonzero constant.

Add a multiple of a row to another row.

Remark: Note the elementary row operation performed in eachstep.

Linear Algebra



Example

21

Notation

RR ↔

−−

−

17552

4031

9321

−

−−

17552

9321

4031

( ) 3312

Notation

RRR ↔+−

−−

−

17552

4031

9321

−−

−−

−

1190

4031

9321

( ) 112

Notation

RR →−

−−

−−−

17552

4031

18642

−−

−

17552

4031

9321

Linear Algebra



Row-Echelon Form

Row-echelon form

1 All rows consisting entirely of zeros occur at the bottom of thematrix.

2 For each row that does not consist entirely of zeros, the �rstnonzero entry is 1 (called a leading 1).

3 For two successive (nonzero) rows, the leading 1 in the higherrow is farther to the left than the leading 1 in the lower row.

Reduced row-echelon form

Every column that has a leading 1 has zeros in every positionexcepting the leading 1.

Linear Algebra



Gaussian Elimination with Back-Substitution

x �2y +3z = 9�x +3y = �42x �5y +5z = 17

24 1 �2 3 9�1 3 0 �42 �5 5 17

35x �2y +3z = 9

y +3z = 5�y �z = �1

24 1 �2 3 90 1 3 50 �1 �1 �1

35 R2 + R1 ! R2R3 � 2R1 ! R3

x �2y +3z = 9y +3z = 5

2z = 4

24 1 �2 3 90 1 3 50 0 2 4

35 R3 + R2 ! R3

Linear Algebra



Gaussian Elimination with Back-Substitution

x �2y +3z = 9y +3z = 5

z = 2

24 1 �2 3 90 1 3 50 0 1 2

35 12R3 ! R3

z = 2y = 5� 3z = 5� 3x2 = �1x = 9+ 2y � 3z = 9+ 2x(�1)� 3x2 = 1

9=;Back-Substitution

Linear Algebra



Practice

y + z � 2w = �3x + 2y � z = 22x + 4y + z � 3w = �2x � 4y � 7z � w = �19

26640 1 1 �2 �31 2 �1 0 22 4 1 �3 �21 �4 �7 �1 �19

3775Hint: Exchange the 1st and 2nd equations.

Linear Algebra



Solution26640 1 1 �2 �31 2 �1 0 22 4 1 �3 �21 �4 �1 �7 �19

3775 !26641 2 �1 0 20 1 1 �2 �32 4 1 �3 �21 �4 �1 �7 �19

3775 !26641 2 �1 0 20 1 1 �2 �30 0 3 �3 �60 �6 �6 �1 �21

3775 !26641 2 �1 0 20 1 1 �2 �30 0 3 �3 �60 0 0 �13 �39

3775 !26641 2 �1 0 20 1 1 �2 �30 0 1 �1 �20 0 0 �13 �39

3775 !26641 2 �1 0 20 1 1 �2 �30 0 1 �1 �20 0 0 1 3

3775

Linear Algebra



The Number of Solutions

Inconsistent system: a row with zeros except for the last entry(example)

Consistent system: not inconsistent systems

1 One solution: the number of not-zero rows is equal to thenumber of variables

2 In�nite solutions: the number of not-zero rows is less than thenumber of variables

Quiz: Homogeneous systems in which each of the constantterm is zero are consistent.

Linear Algebra


Gauss-Jordan Elimination


Linear Algebra




Continues the procedure of Gaussian elimination until areduced row-echelon form is obtained. For example,

x �2y +3z = 9�x +3y = �42x �5y +5z = 1724 1 �2 3 9

�1 3 0 �42 �5 5 17

35!24 1 �2 3 90 1 3 50 �1 �1 �1

35!24 1 �2 3 90 1 3 50 0 2 4

35!24 1 �2 3 90 1 3 50 0 1 2

35!24 1 �2 0 30 1 0 �10 0 1 2

35!24 1 0 0 10 1 0 �10 0 1 2

35

Linear Algebra



Example

y + z � 2w = �3x + 2y � z = 22x + 4y + z � 3w = �2x � 4y � 7z � w = �19

Linear Algebra



Solution26640 1 1 �2 �31 2 �1 0 22 4 1 �3 �21 �4 �7 �1 �19

3775! � � � !

26641 2 �1 0 20 1 1 �2 �30 0 1 �1 �20 0 0 1 3

3775

!

26641 2 �1 0 20 1 1 0 30 0 1 0 10 0 0 1 3

3775!26641 2 0 0 30 1 0 0 20 0 1 0 10 0 0 1 3

3775

!

26641 0 0 0 �10 1 0 0 20 0 1 0 10 0 0 1 3

3775

Linear Algebra



More Examples

72332

2342

22

32

=+−+

−=−++

=−+

−=−+

wzyx

wzyx

zyx

wzy

twx

twy

twz

tw

−=−=

+−=+−=

+−=+−=

=

−−

−−→

−−

−−

−

→

−−

−−

−

→

−−

−−

−

→

−−

−−

−−

−

→

−

−−

−−

−

→

−

−−

−

−−

22

11

22

Then,.Let

00000

21100

11010

21001

00000

21100

11010

01021

00000

21100

32110

20121

00000

63300

32110

20121

32110

63300

32110

20121

72332

23142

32110

20121

72332

23142

20121

32110

+−

+−

−

=

t

t

t

t

w

z

y

x

2

1

2

:Ans

Linear Algebra



Example

x + 2y � z = 22x + 4y + z � 6w = �2

Solution�1 2 �1 0 22 4 1 �6 �2

�! ...!

�1 2 0 �2 00 0 1 �2 �2

�Let y = s and w = t, then,

z = �2+ 2w = �2+ 2tx = �2y + 2w = �2s + 2t

Ans:

2664xyzw

3775 =2664�2s + 2t

s�2+ 2t

t

3775

Linear Algebra



Algorithm for Gaussian Elimination

Input an mxn matrix Ai = 1; j = 1;while i < m and j < nif all entries A(i , j),A(i + 1, j), � � � ,A(m, j) are zerothen j = j + 1 and continue

elseif A(i , j) = 0then 9k > i s.t. A(k, j) 6= 0 and switch row(i) and row(k)

//Here we have A(i , j) 6= 0divide row(i) by A(i , j)for k = i + 1 to mif A(k, j) 6= 0then minus A(k, j) times of row(i) from row(k)

i = i + 1; j = j + 1;

Linear Algebra


Applications of Linear Systems


Linear Algebra



Polynomial Curve Fitting

Given n points:(x1, y1), (x2, y2), � � � , (xn, yn).Find a polynomial equationp(x) =a0 + a1x + ...+ an�1xn�1

passing through all n points.

FFF n points give nequations and therefore cansolve n variables,a0, a1, � � � , an�1.

Insert Figure.

Linear Algebra



Example

Find the polynomial p(x) = a0 + a1x + a2x2 that passes throughthe points (1, 4), (2, 0), and (3, 12).

Solution

From (1, 4), we have a0 + a1 + a2 = 4.From (1, 4), we have a0 + a1 + a2 = 4.From (3, 12), we have a0 + 3a1 + 9a2 = 12.24 1 1 1 41 2 4 01 3 9 12

35 ! ...!

24 1 0 0 240 1 0 �280 0 1 8

35Answer: p(x) = 24� 28x + 8x2.

Linear Algebra



Exercise

1 Find the polynomial p(x) = a0 + a1x + a2x2 + a3x3 + a4x4

passing through the points (�2, 3), (�1, 5), (0, 1), (1, 4),(2, 10). 266664

1 �2 (�2)2 (�2)3 (�2)4 31 �1 (�1)2 (�1)3 (�1)4 51 0 02 03 04 11 1 12 13 14 41 2 22 23 24 10

3777752 Find a polynomial p(x) = a0 + a1x + a2x2 + a3x3 passingthrough the points (0, 1), (1, 2), (�1, 0), (2, 3).

Linear Algebra



Unit Review

Linear equations and systems of linear equations

1 Solutions2 Number of solutions

Gaussian elimination

1 Equivalent systems

elementary row operation

2 Row-echelon form3 Back-substitution

Gauss-Jordan elimination

Reduced row-echelon form

Parametric solutions

Matrix representation

Documents

Linear Algebra (2009 Fall) Chapter 1 Matrices and Systems of Equationsyi/Courses/LinearAlgebra/LectureNotes... · Linear Algebra Systems of Linear Equations Linear Systems Solutions