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

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

Systems of Linear Equations

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

Systems of Linear Equations

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

Systems of Linear Equations

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

Systems of Linear Equations

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

Systems of Linear Equations

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

Systems of Linear Equations

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

Systems of Linear Equations

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

Systems of Linear Equations

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

Systems of Linear Equations

Gaussian Elimination

Gaussian Elimination

Linear Algebra

Systems of Linear Equations

Gaussian Elimination

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

row­echelon formnot row­echelon form

2

53

932

=

=+

=+−

z

zy

zyx

Linear Algebra

Systems of Linear Equations

Gaussian Elimination

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

Systems of Linear Equations

Gaussian Elimination

Gaussian Elimination

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

Systems of Linear Equations

Gaussian Elimination

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 back­substitution , we havex = 1, y = ­1, z = 2.

Linear Algebra

Systems of Linear Equations

Gaussian Elimination

An mxn Matrix

mnmm

n

n

aaa

aaa

aaa

L

MOMM

L

L

21

22221

11211

m rows

n columns

1st row

2nd row

m­st row

1st column n­st column

Linear Algebra

Systems of Linear Equations

Gaussian Elimination

Represent a Linear System by a Matrix

1752

43

932

=+

−=+−

=+−

zx

yx

zyx

−

−

502031321

−−

−

175024031

9321

system

coefficient matrix

augmented matrix

Linear Algebra

Systems of Linear Equations

Gaussian Elimination

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

Systems of Linear Equations

Gaussian Elimination

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

Systems of Linear Equations

Gaussian Elimination

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

Systems of Linear Equations

Gaussian Elimination

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

Systems of Linear Equations

Gaussian Elimination

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

Systems of Linear Equations

Gaussian Elimination

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

Systems of Linear Equations

Gaussian Elimination

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

Systems of Linear Equations

Gaussian Elimination

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

Systems of Linear Equations

Gauss-Jordan Elimination

Gauss-Jordan Elimination

Linear Algebra

Systems of Linear Equations

Gauss-Jordan Elimination

Gauss-Jordan Elimination

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

Systems of Linear Equations

Gauss-Jordan Elimination

Example

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

Linear Algebra

Systems of Linear Equations

Gauss-Jordan Elimination

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

Systems of Linear Equations

Gauss-Jordan Elimination

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

Systems of Linear Equations

Gauss-Jordan Elimination

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

Systems of Linear Equations

Gauss-Jordan Elimination

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

Systems of Linear Equations

Applications of Linear Systems

Applications of Linear Systems

Linear Algebra

Systems of Linear Equations

Applications of Linear Systems

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

Systems of Linear Equations

Applications of Linear Systems

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

Systems of Linear Equations

Applications of Linear Systems

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

Systems of Linear Equations

Applications of Linear Systems

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