Linear Algebra: With Sci-lab

Linear Algebra With Sci-lab

References

Digeteo (2009). Scilab [Software]. Available at http:// www.scilab.org/ Erwin Kreyszig, “Advanced Engineering Mathmatics”, 8th Edition, Copyright © 2003 John Wiley & Sons, Peter V. O’Neil, “Advanced Engineering Mathematics”, Copyright © 2007, Nelson, ad division of Thomson Canada Ltd. Strang, Gilbert. (Spring 2005). MIT OpenCourseWare. Linear Algebra. Video Lectured retrieved from http://ocw.mit.edu/OcwWeb/Mathematics/18-06Spring-2005/VideoLec Williams, Gareth. “Linear Algebra with applications”. 3rd Edition. Copyright © 1996. Times mirror Higher education Group, Inc.

Basic Concepts Matrix Addition Scalar Multiplication

Definition A matrix is a rectangular array of numbers (or functions) enclosed in brackets. These numbers (or functions) are called entries or elements of the matrix

Matrix and Its Transpose  a11 a12 a a 21 22  A = [a jk ] =     am1 am 2  a11 a21 a a 12 22 T  A = [akj ] =     a1n a2 n

 a1n    a2 n      amn   am1    am 2      amn 

Vectors Row Vector = matrix with one row

vrow = [ a1

a2  an ]

vrow = [ 4 0 1]

Column Vector = matrix with on 8 column  b1  vcolumn

b  2 2  = vcolumn =     3     19 bm 

Matrices Symmetric matrices

A =A T

Skew-symmetric matrices

A = −A T

Definition of Equality of Matrix Two matrices are equal if and only if they have the same size and the corresponding entries are equal.

Matrix Operation Size of Matrix, m x n is the numbers of row, m and the numbers of column, n . Only Matrices of the same size can be added. Scalar Multiplication of Matrix is that each entry is multiplied by a constant scalar value.

Matrix Multiplication

Matrix Multiplication The product C=AB (in this order) of an m x n matrix A=[ajk] and an n x p matrix B=[bjk] is defined as the m x p matrix C=[cjk] with entries n

c jk = ∑ a jl blk =a j1b1k + a j 2b2 k +  + a jnbnk l =1

where

j = 1,  , m k = 1,  , p

AB≠ BA

Cautions AB≠ BA  9 3 1 − 4  15 − 21 1 − 4  9 3 17 3  − 2 0  2 5  =  − 2 8  ≠  2 5   − 2 0 =  8 6           AB=0 does not mean A=0, B=0, BA=0

1 1   − 1 1   0 0   − 1 1  1 1   1 1  2 2  1 − 1 = 0 0,  1 − 1 2 2 = − 1 − 1  AC=AD   does  not  mean   C=D for   A ≠ 0  1 1  2 1  4 3 1 1  3 0 2 1  3 0 2 2 2 2 = 8 6 = 2 2 1 3, 2 2 ≠ 1 3            

Special Matrix Upper Triangular

Lower Triangular

Identity I 

Scilab term eye

1 2 9  0 4 2    0 0 5

1 0 0 Diagonal 4 0  5

1 0 0   6 4 0   4 9 6

4 0 0  4 0    4

1 0 0  1 0    1

Scalar

Products ( AB ) = B A Transpose of a Product Inner Product of Vectors T

a • b = [ a1

a2

T

T

 b1  b  n  an ]  2  = ∑ al bl =a1b1 + a2b2 +  + anbn    l =1   bn 

Process, Powers of a Matrix Suppose that the 1998 state of land use is a city of 50 square miles of (nonvacant) area is 0.3  I (Residentially used) 30%    II (Commercially used) 20% x = 0.2  II (Industrially used) 50%

0.5

Find the states in 2003, 2008, and 2013, assuming probabilities for 5-year intervals are given by the matrix To I To II To III 0.8 0.1 0.1

From I

0.8

0.1

0.1

From II

0.1

0.7

0.2

0.1

0.9

From III 0

  A =  0 .1 0 .7 0 .2  0.0 0.1 0.9

Definitions A square matrix with nonnegative entries and row sums all to 1 is called a stochastic matrix A stochastic process for which the probability of entering a certain state depends only on the last state occupied (and o the matrix governing the process) is called a Markov Process

Linear Systems of Equation Gauss Elimination

System of Equations x ++ a

a11

1

Matrix A

x = b1

1n n

a21 x1 +  + a2 n xn = b1  am1 x1 +  + amn xn = bm Matrix Equation

Ax = b

 a11 a12 a a A =  21 22      am1 am 2

 a1n   b1  b   a2 n  , b=  2         am n   bm 

Augment Aa  a11 a12  a21 a22  Aa =      am1 am 2

 a1n b1    a2 n b2       am n bm 

Gauss Elimination Equations

2 x1 + 5 x2 = 2 4 x1 + 3 x2 = 18 2 x1 + 5 x2 = 2 0 x1 − 7 x2 = 14

Matrix

2 5 2  Aa =   4 3 18 2 5 2  Aa =   0 − 7 14

Elementary Operation Equation  



Interchange of two equations Addition of a constant multiple of one equation to another Multiplication of an equation by a nonzero constant c

Matrix  



Interchange of two rows Addition of a constant multiple of one row to another Multiplication of a row by a nonzero constant c

Infinitely many solution 3 2 2 −5 8    1.5 − 5.4 2.7  .6 1.5 1.2 − 0.3 − .03 2.4 2.1 3 2 2 −5 8    0 1 . 1 1 . 1 − 4 . 4 1 . 1   0 − 1.1 − 1.1 4.4 − 1.1 3 2 2 −5 8    0 1.1 1.1 − 4.4 1.1 0 0 0 0 0 

Unique solution − 1  3 − 1 − 1  0  0 − 1  0  0

1 2 2  − 1 1 6 3 4 4 1 2 2  2 7 12 2 2 2  1 2 2   2 7 12  0 − 5 − 10

No solution 3  2 6 3  0 0 

2 1 3  1 1 0 2 4 8 2 1 − 3 −2

3 2  1 0 − 3 0 0 

1 3  1 − 2 3  0 2  1 3  1 − 2 3  12 0 

Reduced Row Echelon Matrix A matrix is in reduced row echelon form if it satisfies the following conditions: 1. 2.

3.

4.

The leading entry of any nonzero row is 1. If any row has its leading entry is column j, then all other elements of the column j are zero. If row I is a nonzero row and row k is a zero, then i < k’ If the leading entry of row r1 is in column c1, and the leading entry of row r2 is in column c2, and if r1 < r2, then c1 < c2.

A matrix in reduced row echelon form is said to be in reduced form, or to be a reduced matrix.

Example 1 0  0 0  0  0

0 1 3 0  − 4 1 0   , 0 0 0 1  ,  0 0 1 0 0 0 0 1 2 0 0 1 0 0 3   0 0 1 0  0 1 0 − 2 , 0 0 0 0  0 0 1 0   0 0 0 0  0 0 0 0

1  4 1  0

Vector Space

Definition n-vector 

( x1

If n is a positive integer, an n-vector is an n-tuple (x1, x2, … xn), wotj eacj cpprdonate xj a real number. The set of all n-vectors is denoted Rn. Vector Space is Rn.

n x 2 Algebra  xn ) + ( y 1ofy R 2  y n ) = ( x1 + y 1 x 2 + y 2  x n + y n )

α ( x1 x 2  x n ) = ( α x1 α x 2  α x n )

O = ( 0 0  0)

Theorem Let F, G, and H be in Rn, and let α and β be real numbers. Then 1 F+G =G +F 2 F + (G + H) = (F + G) + H 3 F+O = F 4 (α + β )F = αF + βF 5 (α β)F = α ( βF) 6 α ( F + G ) = αF + αG 7 αO = O 2 2 2 Magnitude of F isF = x1 + x2 +  xn

Definition

The Dot Product of n-Vector ( x1 x 2  x n ) and ( y1 y 2  y n ) is defined by

( x1

x 2  x n ) • ( y 1 y 2  y n ) = ( x1 y 1 x 2 y 2  x n y n )

Theorem 

     

Let F, G, and H be in Rn, and let α and β be real numbers. Then 1 F •G = G •F 2 (F + G) • H = F • H + G • H 3 α(F • G ) =2 (αF) • G = F • (αG ) 4 F •F = F 5 F • F = 0 2 iff F = 02 2 α F + βF = α 2 F + 2αβF • G + β 2 G 6

Cauchy-Schwarz Inequality in Rn Let F and G be in Rn. ThenF • G ≤ F G Angle between two vectors  0 ( F • G) cos(θ ) =   F G

if F or G equals the zero vector if F ≠ 0 and G ≠ 0

Unit Vectors

e 1 = (1 0  0 ) ( x x  x ) = x e + x e +  + x e 1 2 n 1 1 2 2 n n e 2 = ( 0 1  0) n = ∑ x je j  e n = ( 0 0  1)

j =1

Definition A set of n-vector is a subspace of Rn if: 1. 2. 3.

O is in S The sum of any vectors in S is in S The product of any vector in S with any real number is also in S

Definition A linear combinations of k vectors F1 , … , Fk in Rn is a sum α 1F1+…+ α kFk in which each α j is a real number. Let F1 , … , Fk be vectors in a subspace of Rn. Then F1 , … , Fk form a spanning set for S if every vector in S is a linear combination of F1 , … , Fk. In this case we say that S is spanned by F1 , … , Fk, or that F1 , … , Fk span S.

Definition Let F1 , … , Fk be vectors in a subspace of Rn. 1.

2.

F1 , … , Fk are linearly dependent if and only if one of these vectors is a linear combinations of the others. F1 , … , Fk are linearly independent if and only if they are not linearly dependent

Theorem Let F1 , … , Fk be vectors in a subspace of Rn. Then 1. F1 , … , Fk are linearly dependent if and only if there are real numbers α 1, … α k, not all zero, such that α 1F1+ α 2F2+ …+ α kFk=0 2. F1 , … , Fk are linearly independent if and only if an equation α 1F1+ α 2F2+ …+ α kFk=0 can hold only if α 1=α 2 = … = α k=0

Example Determine whether (1,0,3,1), (0,1,-6,-1) and (0,2,1,0) in R4 are linearly independent. c1(1,0,3,1)+c2 (0,1,-6,-1)+c3 (0,2,1,0)=(0,0,0,0) In terms of system of equations c1 + 0 + 0 = 0 0 + c2 + 2c3 = 0 3 c1 - 6c2 + c3 = 0 c1 - c2 + 0 = 0 Solving for c1, c2, and c3, we have c1= c2=c3 = 0

Lemma Let F1 , … , Fk be vectors in a subspace of Rn. Suppose each Fj has a nonzero element in some component where each of the other Fi’s has a zero component. Then F1 , F1 = … (0,4, ,0F,k0,are 2), Flinearly 0,−5), F3 = (0,0,0,−4,12) 2 = (0,0,6,independent.

αF1 + βF2 + γF3 = (0,0,0,0,0) ( 0,4α ,6β ,−4γ ,2α − 5β + 12γ ) = (0,0,0,0,0) α = 0, β = 0, γ = 0

Theorem Let F1 , … , Fk be mutually orthogonal nonzero vectors in Rn. Then are linearly independent F1 , … , Fk.

Definition Let V be a subspace of Rn. A set of vectors F1 , … , Fk in V form a basis for V if F1 , … , Fk are linearly independent also span V. The dimension of a subspace of Rn is the number of vectors in any basis for the subspace.

Linear Independence Rank of a Matrix

Linear Independence and Dependence of Vector

c1a(1) + + cm a( m ) 1a(1) +  + cm a( m ) = 0

Linear Combination Linear Equation c 



c ,  , c2

Independent if all scalars be zero to satisfy above equation 1 Otherwise dependent

must

Rank of a Matrix 



The maximum number of linearly independent row vectors of a matrix A=[ajk ] is called of the rank of A and is denoted by rank A The rank of a matrix A is the number of nonzero rows in reduced row echelon form of A

Solution of Linear Systems: Existence, Uniqueness, General Form

Fundamental Theorem for Linear Systems Existence.  A linear system of m equations in n unknowns x1 ,..., xn

a11 x1 + a12 x2 +  + a1n xn = b1

(1)

a21 x1 + a22 x2 +  + a2 n xn = b2  am1 x1 + am 2 x2 +  + amn xn = bm

has solutions if and only if the coefficient matrix A and the augmented matrix Aa have the same  a11 a12  a1n b1  a12  a1n  rank.  a11 Here,

a A =  21    am1

a22  am 2

   a2 n  a21  and Aa =        amn  am1

a22  am 2

  a2 n b2       amn bm 

Fundamental Theorem for Linear Systems Uniqueness 

The system (1) has precisely one solution if and only if this common rank r of A and Aa equals n.

Infinitely many solutions. 

If this rank r is less than n, the system (1) has infinitely many solutions. All of these are obtained by determining r suitable unknowns (whose sub matrix of coefficients must have rand r) in terms of the remaining n-4 unknowns, to which arbitrary values can be assigned.

Gauss elimination 

If solutions exist, they can all be obtained by the Gauss elimination.

Unique solution − 1 1 2 2 − 1 1 2 2  − 1 1 2 2         3 − 1 1 6 →  0 2 7 12 →  0 2 7 12  − 1 3 4 4  0 2 2 2   0 0 − 5 − 10 − 1 1 2 2  − 1 1 2      rank  0 2 7  = rank  0 2 7 12  = 3  0 0 − 5 − 10  0 0 − 5

Infinitely many solution 3 2 2 − 5 8  3 2 2 −5 8      1.5 − 5.4 2.7  → 0 1.1 1.1 − 4.4 1.1  →  .6 1 .5 1.2 − 0.3 − .03 2.4 2.1 0 − 1.1 − 1.1 4.4 − 1.1 3 2 2 −5 8    0 1.1 1.1 − 4.4 1.1 0 0 0 0 0  3 2 2 −5  2 −5 8  3 2     rank 0 1.1 1.1 − 4.4 = rank 0 1.1 1.1 − 4.4 1.1 = 2 0 0 0 0 0 0  0 0 0  arbitrary

No solution  3 2 1 3  3 2 1     2 1 1 0  → 0 − 3 6 2 4 8 0 − 2  3 2  1 rank 0 − 3 0 0  2

1 3  3 2   1 1 − 2  → 0 − 3 3 2 0  0 0 3 2 1 3  1   1 1 1 < rank 0 − − 2  3 3 3 0 0 0 12  0   < 3

1 3  1 − 2 3 0 12 

Theorem

A homogeneous linear system

a11 x1 + a12 x2 +  + a1n xn = 0 (4)

a21 x1 + a22 x2 +  + a2 n xn = 0

 am1trivial x1 + amsolution always has the 2 x2 +  + amn xn = 0

. Nontrivial solutions exist if and only if rankxA=<0,..., n. x If rank A = r < n, these 1 n =0 solutions, together with x=0, form a vector space of dimension nr, called the solution space of (4). In particular, if x(1) and x(2) are solutions vectors of (4), then x=c1x(1) + c2x(2) with any scalars c1 and c2 is a solution vector of (4). The term solution space called null space is used for homogeneous systems only. The dimension of null space is nullity of A rank a + nullity A = n

Equations

0 = x1 − 3 x2 + x3 − 7 x4 + 4 x5 0 = x1 + 2 x2 − 3x3 = 0 0 = x2 − 4 x3 + x5 = 0 35 13 0 = x1 − x4 + x5 16 16 28 20 0 = x2 + x4 − x5 16 16 7 9 0 = x3 + x4 − x5 16 16 x4 = α , x5 = β 35 13 x1 = + α − β 16 16 28 20 x2 = − α + β 16 16 7 9 x3 = − α + β 16 16

Matrix 1 − 3 1 − 7 4  A = 1 2 − 3 0 0 0 1 − 4 0 1  35 13   1 0 0 −  16 16   28 20  AR = 0 1 0 −  16 16   7 9 0 0 1 −  16 16  13   35  16 α − 16 β   35  − 13  28 − 28  20  20  α − α + β      γ = 16 16   16     X= = γ + δ , − 7 9 − 7 α + 9 β      δ= β  16 16   16   0  16   α  0   16    β  

Theorem A homogeneous linear system with fewer equations than unknowns always has nontrivial solutions If a nonhomogeneous linear system of equation of the form

a11 x1 + a12 x2 +  + a1n xn = b1 a21 x1 + a22 x2 +  + a2 n xn = b2  am1 x1 + am 2 x2 +  + amn xn = bm has solutions, then all these solutions are of the form x = x0 + xh where x0 is any fixed solution and xh runs through all the solutions of the corresponding homogeneous system.

a11 x1 + a12 x2 +  + a1n xn = 0

a21 x1 + a22 x2 +  + a2 n xn = 0  am1 x1 + am 2 x2 +  + amn xn = 0

Equations − 3 = x1 − x3 + 2 x4 + x5 + 6 x6 1 = x2 + x3 + 3 x4 + 2 x5 + 4 x6 0 = x1 − 4 x2 + 3 x3 + x4 + 2 x6 27 15 60 17 x4 − x5 − x6 − 8 8 8 8 13 9 20 1 x2 = − x4 − x5 − x6 − 8 8 8 8 11 7 12 7 x3 = − x4 − x5 − x6 − 8 8 8 8 x1 = −

1 [ A B] = 0  1

Matrix 0

−1

2

1

1

1

3

2

−4

3

1

0

6 − 3  4 1  2 0  

1 0 0 17 / 8 15 / 8 60 / 8 −17 / 8 [ A B] R = 0 1 0 13 / 8 9 / 8 20 / 8 1 / 8   0 0 1 11 / 8 7 / 8 12 / 8 7 / 8   − 27 / 8 x4 −15 / 8 x5 − 60 / 8 x6 −17 / 8  −13 / 8 x − 9 / 8 x − 20 / 8 x −1 / 8  α = x4 4 5 6   8  −11 / 8 x4 − 7 / 8 x5 −12 / 8 x6 − 7 / 8  x5 X = , β =  x 8 4   x5  γ = x6   8 x    6  − 27  −15  − 60  −17 / 8  −13   −9  − 20   −1 / 8           −11   −7  −12   − 7 / 8  X = α + β + γ     +  8 0 0 0          0   8   0   0          0 0 8 0                

Determinants Cramer’s Rule

Second Order Determinants a11 D = det A = a21

Definition Cramer’s Rule

a12 = a11a22 − a12 a21 a22

a11 x1 +a12 x2 =b1 a11 a22 x1 +a12 a22 x2 =b1a22 → a21 x1 +a22 x2 =b2 a12 a21 x1 +a12 a22 x2 =b2 a12

(a11 a22

−a12 a21 ) x1 =b1a22 −b2 a12 b1

a12

b2 a22 b1a22 −b2 a12 x1 = = D D a11 x1 +a12 x2 =b1 a11 a21 x1 +a12 a21 x2 =b1a21 → a21 x1 +a22 x2 =b2 a11 a21 x1 +a11 a22 x2 =b2 a11

(a11 a22 x2 =

−a12 a21 ) x1 =b2 a11 −b1a21

b1a22 −b2 a12 = D

a11 a21

b1 b2 D

Third-Order Determinants Definition a11

a12

a13

D = a21

a22

a23 = a11

a31

a32

a33

a22

a23

a32

a33

− a21

a12

a13

a32

a33

+ a31

a12

a13

a22

a23

Cramer’s Rule a11 x1 + a12 x2 + a13 x3 = b1 D3 D1 D2 a21 x1 + a22 x2 + a23 x3 = b2 → x1 = , x2 = , x3 = D D D a31 x1 + a32 x2 + a33 x3 = b3 b1 D1 = b2 b3

a12 a22 a32

a13 a11 b1 a23 , D2 = a21 b2 a33 a31 b3

a13 a11 a23 , D3 = a21 a33 a31

a12 a22 a32

b1 b3 b3

n Definition D = det A =

a11 a21

a12  a1n a22  a2 n

 an1

   an 2  ann

D = a j1C j1 + a j1C j 2 +  + a j1C jn , ( j = 1, 2,  , or n) D = a1k C1k + a1k C2 k +  + a1k Cnk , (k = 1, 2,  , or n) C jk = ( − 1)

j+k

M jk where M jk is determinant of order n − 1

C jk is the cofactor of a jk and M jk is the minor of a jk . n

D = ∑ ( − 1)

j+k

a jk M jk

( j = 1, 2,  , or n)

j+k

a jk M jk

(k = 1, 2,  , or n)

k =1 n

D = ∑ ( − 1) j =1

General Properties Interchange of two rows multiplies the value of the determinant by –1. Addition of a multiple of a row to another row does not alter the value of the determinant. Multiplication of a row by c multiplies the value of the determinant by c. Transposition leaves the value of a determinant unaltered. A zero row or column renders the value of determinant zero. Proportional rows or columns render the value of determinant zero.

Theorem An m x n matrix A=[ajk ] has r ≥ 1 if and only if A has an r x r submatrix with nonzero determinant, whereas the determinant of every square submatrix with r + 1 or more rows that A has (or does not have!) is zero. In particular, if A is square, n x n, it has rank n if and only if det A ≠ 0

Cramer’s Theorem If a linear system of n equations is the same number of unknowns

x1 ,  , xn

(12)

a11 x1 + a12 x2 +  + a1n xn = b1 a21 x1 + a22 x2 +  + a2 n xn = b2  an1 x1 + an 2 x2 +  + ann xn = bn

has a nonzero coefficient determinant D = det A, the system has precisely one solution. This solution is given by the formulas

Dn D1 D2 x1 = , x2 = ,  xn = D D D where Dn is the determinant obtained from D by replacing in D the kth column by the column with the entries b1 , , bn Hence, if the system (12) is homogeneous and D≠ 0, it has only the trivial solution . If D = 0, the homogeneous x = 0 ,  , x = 0 system also has1nontrivial nsolutions.

Inverse of a Matrix Gaus-Jordan Elimination

Definition The inverse of an n x n matrix A =[ajk ] is denoted by A-1 and is n x n matrix such that −1

−1

AA = A A = I where I is the n x n unit matrix. If A has an inverse, the inverse is unique 

If B and C are inverses of A, the AB=I and CA=I, so that we obtain the uniqueness form B=IB=(CA)B=C(AB)=CI=C

Theorem The inverse A-1 of an n x n matrix A exists if and only if rank A = n, hence if and only if det A 0. Hence A is nonsingular if ran A = n, and is singular if rank A < n

Theorem The inverse of a nonsingular n x n matrix A=[ajk ] is given by

[ ]

1 A = A jk det A −1

T

 A11 A 1  21 = det A     An1

A12  A1n   A22  A2 n      An 2  Ann 

where Ajk is the cofactor of ajk in det A.

A jk = ( − 1)

j+k

M jk , where M jk is minor of a jk

Thank you very much.