Page 1
1 1 COMPLEX NUMBER AND FIELD Unit Structure: 1.0 Objectives 1.1 Introduction 1.2 Basic concepts of Complex Number 1.2.1 Complex number: Definition and examples 1.2.2 Algebra of complex numbers 1.2.3 Conjugate, Modulus and Argument of a complex number 1.2.4 Graphical representation of a complex number 1.2.5 Representation of a Complex number 1.2.6 Square root of a complex number 1.3 Numbers in python 1.4 Abstracting over Field 1.5 Playing with GF(2) 1.6 Summary 1.7 Reference for further reading 1.0 OBJECTIVES After going to this chapter, you will be able to: • Understand the extension of real number system • Define i • Identify real and imaginary parts of a complex number • Evaluate square root of a complex number • Define Field. 1.1 INTRODUCTION The concept of extension of the set of real numbers to the complex numbers was first necessitated by solution of such algebraic equations whose solutions could not be found in the set of real numbers and also to evaluate square root of a negative number. Complex numbers were introduced by Italian mathematician Gerolamo Cardano in 1545. Leonhard Euler was first to introduce the symbol ‘i‘ (iota) for the square root of ‘-1’ with the property i2 = -1. munotes.in
Page 2
2 Linear algebra using python 1.2 BASIC CONCEPTS OF COMPLEX NUMBER 1.2.1 Complex number: Definition and examples Def: A number is in the form of ‘a+ib’ is called a complex number, where a and b are real numbers and i =√−1. ex. 2+3i, √2+7𝑖,9−√11 i Usually a complex number is denoted by Z. If Z = a+ib, then ‘a’ is called real part and ‘b’ is called imaginary part of the complex number Z and are denoted by Re(Z) and Im(Z) respectively. A complex number whose real part is equal to 0 is called an imaginary number. 1.2.2 Algebra of complex numbers i.) Equality of two complex numbers: Two complex numbers Z1 = a1+ ib1 and Z2 = a2 + ib2 are equal iff a1 = a2 and b1 = b2. i.e Re(Z1) = Re(Z2) and Im(Z1) = Im(Z2) ii.) Addition of two complex numbers: Let Z1 = a1 + ib1 and Z2 = a2 + ib2 are two complex numbers. Addition of Z1 and Z2 is denoted as Z1+Z2 and defined as Z1 + Z2 = (a1+a2) + i (b1+b2). Example: Z1= 7+2i and Z2= 2+5i then Z1+Z2= (7+2i) + (2+5i)=(7+2) +i(2+5) = 9+7i iii.) Subtraction of two complex numbers: Let Z1 = a1+ib1 and Z2 = a2+ib2 are two complex number. Subtraction of Z1 and Z2 is denoted as Z1-Z2 and is defined as Z1 - Z2 = (a1-a2) + i (b1-b2). Example: Z1= 7+2i and Z2= 2+5i then Z1 - Z2= (7+2i) - (2+5i) = (7-2) +i(2-5) = 5+(-3)i iv.) Multiplication of two complex numbers: Let Z1 = a1+ib1 and Z2 = a2+ib2 are two complex number. Multiplication of Z1 and Z2 is denoted as Z1.Z2 and is defined as Z1 . Z2 = .( a1+ib1).(a2+ib2) = (a1a2c+ ia1b2 + ib1a2 + i2b1b2) = (a1a2 + ia1b2 + ib1a2 + (-1)b1b2) (since i2=-1) = (a1a2 - b1b2) + (a1b2 + b1a2)i munotes.in
Page 3
3
Complex Number and Field Multiplicative Inverse of a complex number Z = a +ib Z−1 or 1/Z is called the multiplicative inverse of a non-zero complex number Z if ZZ−1= 1. ⇒Z−1 = 1a+𝑖b = 1a+𝑖b * a−𝑖ba−𝑖b = a−𝑖ba2−b2 v.) Division of two complex numbers: Let Z1 = a1+ib1 and Z2 = a2+ib2 are two complex number. Division of Z1 and Z2 is denoted as Z1/Z2 and is defined as Z1Z2= Z1*1Z2 = a1a2+b1b2a22+b22 + i a2b1−a1b2a22+b22 Example: Solve 1−2𝑖3+4𝑖. Sol. 1−2𝑖3+4𝑖 = 1+2𝑖3+4𝑖*3−4𝑖3−4𝑖 = 11−2𝑖25 1.2.3 Conjugate, Modulus and Argument of a complex number Let Z = a+ib is a complex number. Conjugate: Its conjugate is denoted by Z̅ and is defined 𝑧̅ = a-ib. Example: if Z= -2 +3i then Z̅ = -2 -3i. Modulus: The modulus(or Absolute value) of Z is denoted by |Z| and defined as |𝑧|=√𝑎2+𝑏2 Example: Z = 5+12i, |𝑧|=√𝑎2+𝑏2=√52+122=√25+144=√169 = 13 Note: Modulus can’t be negative. We always take only positive value of square root. Argument: The argument(or Amplitude) of Z is denoted by arg(Z) or amp(Z) or ‘𝜃’ and is defined as tan-1(𝑏𝑎). i.e. 𝜃 = tan-1(ba) , when a > 0 and tan-1(ba) + 𝜋, when a < 0. Example: Z = 1 + √3i, Then amp(Z) = tan-1(√31) = 𝜋3. Principal argument: The principal argument of a complex number Z is Arg(Z) is equal to Arg(Z) = arg(Z) - 2 𝜋n Hence, the value of the principal argument of the complex numbers lies in the interval (-𝜋, 𝜋). 1.2.4 Graphical representation of a complex number A complex number Z = a+ib can be represented in a co-ordinate system known as complex plane or argand plane. We consider real part of Z (i.e. munotes.in
Page 4
4 Linear algebra using python Re(Z)=a) on X-axis (real axis) and imaginary part of Z (i.e. Im(Z)=b) on Y-axis (Imaginary axis).
From the above diagram we have OAB is a triangle. OA= a units, AB= b units then OZ=r=√𝑎2+𝑏2 and ‘ 𝜃 ‘ is the angle between X-axis and OZ. Cos 𝜃 = 𝑎𝑟 , Sin 𝜃 = 𝑏𝑟 then tan 𝜃=sin𝜃cos𝜃 =(𝑏/𝑟)(𝑎/𝑟)= 𝑏𝑎 Then 𝜃 =tan-1⎸𝑏𝑎⎹ 1.2.5 Representation of a Complex number Cartesian form of a Complex number: Let Z = a+ib is a complex number. Then Z = (a, b) is the ordered pair representation or Cartesian form of complex number Z. Polar form of a complex number: Let Z = a+ib is a complex number. From the above diagram Cos 𝜃 = 𝑎𝑟 and Sin 𝜃 = 𝑏𝑟. a = r Cos𝜃 and b = rSin 𝜃 Substituting these values in Z, we get Z = a+ib= rCos𝜃 + irSin 𝜃 Z = r(Cos 𝜃+i Sin 𝜃) is called POLAR FORM of a complex number Z. Exponential Form of a complex number: Let Z = a+ib is a complex number. Then Z = r ⦁𝑒𝑖𝜃 is called exponential form of Z, where r is modulus of Z and 𝜃 is amplitude of Z or amp(Z). Example: Let Z = 1+i, Cartesian Form of Z is (1, 1) Polar form of Z is √2(cos 𝜋4 + isin 𝜋4), where r = √2 and 𝜃 = 𝜋4. Exponential form of Z is √2⦁𝑒𝑖𝜋4.
O
A
B
a
b munotes.in
Page 5
5
Complex Number and Field 1.2.6 Square root of a complex number To find the square root of a complex number Z = a+ib, the following steps should be followed: Step I: Let A+iB = √(a+𝑖b) Step II: Squaring both sides, (A+𝑖B)2= a+ib ⇒ (𝐴2−𝐵2) + 2AB i = a + ib Step III: Equating real and imaginary parts from both sides; (𝐴2−𝐵2) = a-----(i) and 2AB = b------(ii) Step IV: Solving equations (i) and (ii), get the value of A and B. Example: Find the square root of Z =3-4i Soln: Given Z = √3−4𝑖 Let √3−4𝑖 = (a + ib) . Squaring on both sides, (√3−4𝑖)2=( a + ib)2 . 3-4i = (a2-b2) + 2ab i Comparing real and imaginary parts on both the sides; a2-b2 = 3------(i) and 2ab = -4--------(ii) ⇒ b = −2𝑎 Put the value of b = −2𝑎 in a2-b2 = 3 we get, a2- ( −2𝑎)2 = 3 ⇒a2 – (4𝑎2 ) = 3 ⇒a4 – 4 = 3a2 ⇒a4-3a2 = 4 ⇒a4 – 4a2 + a2 -4 =0 ⇒a2(a2-4)+1(a2-4)=0 ⇒ (a2+1)(a2-4)=0 ⇒ (a2+1)=0 or (a2-4)=0 ⇒a2 = -1 or a2 = 4 ⇒a = ± i(Rejected, since a must be a real number) or a=±2 if a = 2 then b= −2𝑎 = −22 = -1 and if a= -2 then b= −2𝑎 = −2−2 = 1. Therefore √3−4𝑖 = 2-1i or -2+1i munotes.in
Page 6
6 Linear algebra using python 1.3 NUMBERS IN PYTHON In Python, there are three types of numeric. 1. Int: Int is a whole number, positive or negative, without decimals, of unlimited length. 2. Float: Float is a number, positive or negative, containing one or more decimals. 3. Complex Number: Any complex number a + ib is written as a + bj in python. Variables of numeric types can be created by assigning a value to them. Example: x = 1 #int y = 2.8 #float Z = 2 + 1j # complex number To verify the type of any object in Python, use the type() function. 1.4 ABSTRACTING OVER FIELD Binary Operation: A binary operation ‘*’ is defined as a function of the product set AxA to A where for all a, b∈ A, (a*b) ∈ A. Field: Let F is nonempty set equipped with two binary operations called addition ‘+’ and multiplication ‘ ● '. Then the algebraic structure (F,+, ●) is a field if it satisfies the following postulates: 1. Closure Law: a + b ∈ F , for all a,b ∈ F 2. Associative Law: (a + b) + c = a + (b + c) , for all a, b, c ∈ F 3. Existence of identity: There exists an element е in F such that a + e = e + a = a. 4. Existence of Inverse: For each a ∈ F, there exists -a ∈ F such that a +(-a) = (-a) + a = е 5. Commutative Law: a +b = b + a for all a, b∈ F 6. Multiplication is distributive with respect to addition i.e. for all a, b ,c ∈ F a●(b+c) = a ● b + a ● c ( left distributive law) and (b+c) ● a= b ● a + b ● c ( right distributive law) 7. Multiplication composition is also commutative. i.e. a●b = b●a for all a, b∈ F 8. There exists an element ‘1’ in F such that 1● a = a = a ● 1 for all a ∈ F 9. Each none-Zero element possesses multiplicative inverse. Example: The set R of real numbers is a field. munotes.in
Page 7
7
Complex Number and Field 1.5 PLAYING WITH GF(2): Galois Field also known as GF(2) is the smallest field consisting only two elements 0 and 1 being the additive and multiplicative identity respectively. The field addition in GF(2) is the logical XOR operation defined as And, the field multiplication in GF(2) is the logical AND operation defined as Example: 1●1+0●1+1●0+0●0+1●0 = 1 + 0 + 0 + 0 = 1 And 1●0 + 0●1 + 1●1 + 1●1 = 0 + 0 + 1 + 1 = 0 1.6 SUMMARY: From the definition of complex number, it is clear that any imaginary number is a complex number. We can also conclude that any real number is also a complex number. In Mathematics, Complex numbers are used to find the solutions of those equations whose roots cannot be found in real number set. Algebraic operations on complex numbers are given by addition, subtraction, multiplication and division. To plot a complex number, we use complex plane that consists a coordinate system in which horizontal axis represents real component and the vertical axis represents imaginary component. The square root of a complex number is also a complex number. 1.7 REFERENCE FOR FURTHER READING: Linear algebra and its applications, Gilbert Strang, Cengage Learning, 4th edition, 2007. Exercise 1. If Z1 = 5 - 12i and Z2 = 8 + 6i, Find the values of Z1 + Z2, Z1 - Z2, Z1 * Z2, and Z1 / Z2. 2. Find the conjugate, modulus and argument of the following complex numbers: i.) 8 - 6i ii.) 5 + 12i iii.) 2i + 0 1 0 0 1 1 1 0 ● 0 1 0 0 0 1 0 1 munotes.in
Page 8
8 Linear algebra using python 3. Solve the following: i.) (1 + 7i)(2 - 3i) ii.) (√3 + 2i)( -2i -1) iii.) 4+3𝑖2−3𝑖 4. Find the square roots of the following Complex numbers: i.) 7-24i ii.) 5+12i iii.) 4-3i 5. Solve in GF(2): i.) 1+1+0+1+1 ii.) 1.1.1+0.1.1+1.1.1+0.0.0 6. Check whether the set of rational numbers and set of integers are Field or not. munotes.in
Page 9
9 2 VECTORS Unit Structure: 2.0 Objectives 2.1 Introduction 2.2 Vectors are Functions 2.3 Vector Addition and Scalar Multiplication 2.3.1 Vector Addition 2.3.2 Scalar-vector multiplication 2.3.3 Combining vector addition and scalar multiplication 2.4 Dictionary based representation of vectors 2.5 Dot Product 2.6 Solving a triangular system of linear equations 2.6.1 Lower Triangular System 2.6.2 Upper Triangular System 2.7 Linear Combination 2.8 Span 2.9 Geometry of set of vectors 2.10 Vector Spaces 2.11 Linear Systems-Homogeneous and otherwise 2.12 Summary 2.13 Reference for further reading 2.0 OBJECTIVES After going to this chapter, you will be able to: • Define a scalar and a vector. • Distinguish between scalar and vector. • Perform addition, subtraction, and multiplication by scalar on vectors. • Represent a vector. • Define homogeneous and non-homogeneous system of linear equations and predict nature of solution. • Explain vector space munotes.in
Page 10
10 Linear algebra using python 2.1 INTRODUCTION A scalar is a quantity that has only magnitude. A vector is a quantity that has both magnitude and direction. We can represent a vector with a directed line segment. The arrow indicates the direction and the length is the magnitude of the vector. 2.2 VECTORS ARE FUNCTIONS Vectors can be represented as a function. It is called a vector function. The domain of the vector function consists of one or more variables and returns a vector. A vector function of a single variable in R2 and R3 have the form, r(t) = and r(t) = respectively, where f(t), g(t) and h(t) are called the component functions. In general, a vector function of single variable in Rn has the form: v(t) = where f1(t), f2(t), f3(t), ….., fn(t) are n-components. The domain of a vector function is the subset of real numbers and set of all t’s for which all the component functions are defined. The range is a vector. 2.3 VECTOR ADDITION AND SCALAR MULTIPLICATION 2.3.1 Vector Addition: Vector addition is the operation of adding two or more vectors together. In Linear Algebra, vectors are given in their components form. Vector addition can be performed simply by adding the corresponding components of the vectors, so in Rn, if U and V are two vectors with n-components U = (uଵ,uଶ,……..,u୬) and V = (vଵ,vଶ,……..,v୬) then, U + V = (uଵ+ vଵ, uଶ + vଶ,……..,u୬ + v୬). Vector addition is possible if both the vectors have same number of components. 2.3.2 Scalar-vector Multiplication: When a vector V is multiplied by a scalar quantity k, its magnitude becomes k-times of the original vector but the direction depends on the sign of k. If k is positive, then kV has the same direction of V, but if k is negative, kV has the opposite direction of V. In linear Algebra, to multiply a vector V having components (vଵ,vଶ,……..,v୬) by a scalar k means to multiply each component of the given vector by the scalar k. ⇒ kV = k(vଵ,vଶ,……..,v୬) = (kvଵ, kvଶ,…….., kv୬) munotes.in
Page 11
11
Vectors 2.3.3 Combining vector addition and scalar multiplication: Vector addition and scalar multiplication simultaneously can be performed by following these steps: 1. Complete the scalar multiplication first by multiplying each component of the vector V by the scalar k. 2. Then, perform the vector addition by adding corresponding components of vectors that have been found after completing step 1. Example: If u = (2, 3, -1) and v = (6, -3, -2), then find (a.) (u + v)(b.) 2u + 3v (c.)(u – v) Solution: (a.) (u + v) = (2, 3, -1) + (6, -3, -2) = (2 + 6, 3 + (-3), (-1) + (-2)) = (8, 0, -3) (b.) 2u + 3v = 2 (2, 3, -1) + 3(6, -3, -2) = (4, 6, -2) + (18, -9, -6) = (4 + 18, 6 +(-9), (-2) + (-6)) = (22, -3, -8) (c.) (u – v) = (2, 3, -1) - (6, -3, -2) = (2 - 6, 3 - (-3), (-1) - (-2)) = (-4, 6, 1) 2.4 DICTIONARY BASED REPRESENTATION OF VECTORS A vector is a function from some domain D to a field. In Python, it can be represented by a dictionary. For this, define a Python class Vec with two variables f (the function represented by Python dictionary) and D(the domain of the function represented by a python set. class Vec: def__init__(self, labels, function): self.D = labels self.f = function can create >>> Vec({‘A’, ‘B’, ‘C’}, {‘A’: 1}) Can assign an instance to a variable and subsequently access the two fields of v, >>> v = Vec({‘A’, ‘B’, ‘C’}, {‘A’: 1}) >>> for d in v.D: … if d in v.f: … print(v.f[d]) … munotes.in
Page 12
12 Linear algebra using python 2.5 DOT PRODUCT The dot product of two vectors with n-components U = (uଵ,uଶ,……..,u୬) and V = (vଵ,vଶ,……..,v୬) is denoted as U.V and defined as U.V = (uଵ.vଵ + uଶ.vଶ + ……..+ u୬.v୬). U.V is a scalar quantity and it follows commutative law of multiplication. That is, U.V = V.U Example 1; Find dot product of (1, 2) and (3, 4). Solution: Let U = (1, 2), V = (3, 4), then U.V = (1, 2)⦁(3, 4) = (1*3 + 2*4) = 11 Example 2: The dot product of two vectors from Rଷ where u = (1, -1, 2) and v = (2, -3, 4). Solution: u . v = (1, -1, 2)⦁(2, -3, 4) = 1* 2 + (-1)*(-3) + 2*4 = 2 + 3 + 8 = 13 Example 3: Let u =11001 and v=10110 are two vectors over GF(2), find their dot product. Solution: u.v = (11001)⦁(10110) = (1*1 + 1*0 + 0*1 + 0*1 + 1*0) = (1 + 0 + 0 + 0 + 0) = 1. 2.6 SOLVING A TRIANGULAR SYSTEM OF LINEAR EQUATIONS Consider the system of n linear equations: a11x1 + a12x2 + ……….+ a1nxn = K1------------------------(i) a21x1 + a22x2 +……….+ a2nxn = K2------------------------(ii) an1x1 + an2x2 +……….+ annxn = Kn------------------------(nth) Containing the n unknowns x1, x2…, xn. It is called a linear system of equations. The leading unknown in all equations is x1 and the leading co-efficient of equations are a1, a2, …, an respectively. 2.6.1 Lower Triangular System: The linear system of equations is called lower triangular system of equations if leading unknown in all equations is x1 and the leading co-efficient of equation (i) is a11, leading co-efficient of equation(ii) is a21 and so on i.e the general form of triangular system of n linear equation having n unknown is aଵଵ xଵ = K1 a21 x1 + a22x2 = K2 . . . an1 x1 + an2 x2 +……….+ ann xn = Kn munotes.in
Page 13
13
Vectors The lower triangular system of equations can be solved by forward substitution method i.e First we have to calculate value of 𝑥ଵ by 1st equation. ⇒aଵଵ x୬=Kଵ ⇒xଵ = kଵaଵଵ Then the value of xଶ is obtained by putting the value of xଵ in 2nd equation and then solving it. So, we proceed up to last equation where we can get value of x୬ by substituting the values of xଵ,xଶ,..........x୬ିଵ. 2.6.2 Upper Triangular System: The linear system of equations is called upper triangular system of equations if leading unknown in the first equation is x1 , leading unknown in the second equation is x2, that of the third equation isx3,……..and so on .And the leading co-efficient of equation (i) is a11, leading co-efficient of equation(ii) is a22 and so on i.e the general form of triangular system of n linear equation having n unknown is 𝑎ଵଵ𝑥ଵ+ 𝑎ଵଶ𝑥ଶ+ 𝑎ଵଷ𝑥ଷ+……..+ 𝑎ଵ𝑥=K1 a22x2+a23x3 +……….+a2nxn=K2 a33x3 +……….+a3nxn=K3 an n x n= K n The upper triangular system of equations can be solved by backward substitution method i.e First we have to calculate value of x୬ by n୲୦ equation. ⇒a୬୬ x୬=k୬ ⇒x୬ = ୩ୟ Then the value of x୬ିଵ is obtained by putting the value of x୬ in 2nd last equation and then solving it. So, we proceed up to first equation where we can get value of xଵ by substituting the values of xଶ,xଷ,..........x୬ିଵ, x୬. Example 1: 5 xଵ = 15, 4xଵ + 2xଶ = 10, 3xଵ+ 5xଶ + 2xଷ =18 Solution: The given system is lower triangular system of linear equations having 3 unknowns. Hence by forward substitution method; 5 xଵ = 15⇒x1 = ଵହହ = 3 munotes.in
Page 14
14 Linear algebra using python By substituting value of x1 in equation (ii), 4*3 + 2x2 = 10 ⇒ x2 = -1 Now replacing values of x1 and x2 in equation (iii), 3*3 + 5*(-1) + 2x3 = 18⇒x3 = 7 Example 2: xଵ+ 2xଶ + xଷ = 8 3xଶ + 4xଷ = 18 7 xଷ = 21 Solution: The given system is upper triangular system of linear equations having 3 unknowns. Hence by backward substitution method; 7 xଷ = 21 ⇒ xଷ= 3 Substitute the value of xଷ in second equation we get, 3xଶ + 4xଷ = 18 ⇒ xଶ = 2 Substituting xଶ and xଷ in first equation we get, xଵ+ 2xଶ + xଷ = 8 ⇒ xଵ= 1 2.7 LINEAR COMBINATION Let vଵ,vଶ,……..,v୬ are n vectors, then the combination (∝ଵvଵ + ∝ଶvଶ +……….+ ∝୬v୬) is called a linear combination of the vectors vଵ , vଶ,…….., v୬ where ∝ଵ,∝ଶ,……..,∝୬ ∈ F. It can be geometrically interpreted as the vectors vଵ , vଶ,…….., v୬ will be added with each other after scaling by ∝ଵ,∝ଶ,……..,∝୬ times respectively. Example 1: Express W = (6, -2, 5) as a linear combination of vଵ=(−2,1,3) and vଶ = (3, 1, -1) and vଷ = (-1, -2, 1). Solution: (6, -2, 5) = aଵ(-2, 1, 3) + aଶ (3, 1, -1) + aଷ(-1, -2, 1) = (-2 aଵ, aଵ, 3aଵ) + (3aଶ ,aଶ ,−aଶ) + (−aଷ ,−2aଷ ,aଷ) = -2 aଵ + 3aଶ–aଷ , aଵ + aଶ−2aଷ, 3aଵ–aଶ + aଷ Comparing respective components of both sides, we get -2 aଵ + 3aଶ–aଷ= 6 ---------(i) aଵ + aଶ−2aଷ= -2 -----------(ii) 3aଵ–aଶ + aଷ= 5 ------------(iii) Solving these equations by using Cramer’s rule or matrix method, we get aଵ= 9/5, aଶ= 23/5 and aଷ = 21/5 ⇒ (6, -2, 5) = 9/5(-2, 1, 3) + 23/5 (3, 1, -1) + 21/5 (-1, 2, 1). munotes.in
Page 15
15
Vectors Example 2: Express W=(4, 3) as a linear combination of vଵ=(2, 3) and vଶ=(0,1). Solution: (4, 3) = a1(2, 3) + a2 (0, 1) ⇒ (4, 3) = (2a1, 3a1) + (0, a2) ⇒ (4, 3) = (2a1, 3a1+ a2) Comparing respective components of both sides, we get 2a1 = 4 ⇒a1 = 2 and 3a1+ a2 = 3 ⇒ -3 ⇒ (4, 3) = 2(2, 3) + (-3)(0, 1) 2.8 SPAN The set of all linear combinations of finite sets of elements of S is called Linear Span of S and is denoted by L(S) or [S] L(S) = { αଵvଵ+αଶvଶ+..............+α୬v୬∶vଵ ,vଶ ,......v୬ ∈S αଵ ,αଶ ,..........α୬∈ F} Example 1: Find the Span of a subset S= {(1, 0, 0), (0, 1, 1)} of vector space Vଷ. Solution: L(S)= { αଵ (1,0,0) + αଶ (0,1,1)} = { αଵ ,0,0) + (0,αଶ,αଶ )} ={ ( αଵ ,αଶ,αଶ)} ⇒ The linear span of the given subset of vଷ is the element of xyz-plane, whose y and z co-ordinates are same. Example 2: Find the span of subset S={ (1, 3), (0, 2) } of vector space Vଶ show that (2,8) belongs to span S. Solution: L(S) = { αଵ (1,3) + αଶ (0,2)} = { (αଵ ,3 αଵ) + (0, 2αଶ)} = { ( αଵ , 3 αଵ+ 2αଶ)} If (2, 8) ∈ L(S) then αଵ =2 and 3 αଵ+ 2αଶ = 8 ⇒ αଶ=1 ⇒(2, 8) = 2(1, 3) + 1(0, 2) Example 3: Show that the subset S = {(1, 0, 0), (0, 1, 0), (0, 0, 1)} of Vଷ spans the entire vector space Vଷ. Solution: Let (a, b, c) ∈ V then (a, b, c) = a(1, 0, 0) + b(0, 1, 0) + c(0, 0, 1) Thus (a, b, c) ∈ L(S). Hence the subset S span the entire vector space. munotes.in
Page 16
16 Linear algebra using python Example 4: vଵ= (1,0,1) ,vଶ =(2,1,4),vଷ = (1, 1, 3) do not span vector space. Solution: Let (a, b, c) ∈ V and ( αଵ ,αଶ ,αଷ)∈ F. And S = {(1, 0, 1), (2, 1, 4), (1, 1, 3)} (a, b, c) = αଵ (1,0,1) + αଶ (2,1,4) + αଷ(1,1,3) (a, b, c) = (αଵ, 0 , αଵ) + ( 2αଶ,,αଶ 4αଶ) + ( αଷ, αଷ ,3 αଷ) (a, b, c)= (αଵ+ 2αଶ+αଷ , αଶ+αଷ , αଵ+4αଶ+ 3αଷ) a = αଵ+ 2αଶ+αଷ –(i) b = αଶ+αଷ ---(ii) c = αଵ+4αଶ+ 3αଷ---(iii) Solving (i) and (iii), αଶ+αଷ = ୡିୟଶ ⇒ ୡିୟଶ = b ⇒ c-a=2b ⇒ the set S does not span the entire vଷ, but it spans a subset of V whose co-ordinates (a, b, c) satisfy the relation a + 2b – c = 0. 2.9 GEOMETRY OF SET OF VECTORS In geometry, vectors are represented by an arrow. The head of the arrow indicates its direction and length describes the magnitude of the vector. If we multiply a vector u by a scalar ∝, then the length of the vector stretches by the factor ∝. If ∝ is negative, then the direction of the vector will be reversed. If the vector u is added to vector v, then their sum is the new vector (u + v) that paints from the tail of u to the tip of v as shown:
P Initial Point
Q Terminal Point munotes.in
Page 17
17
Vectors
The length or magnitude of an n-vector is defined as ||v|| = √v.v i.e if v = ( vଵ , vଶ,…….., v୬), then ||v|| = ඥvଵଶ+vଶଶ+v୬ଶ = ඥ∑v୧ଶ୬୧ୀଵ The angle 𝜃 between two n-vectors is determined by u . v = ||u|| ||v||. cos 𝜃 2.10 VECTOR SPACE Binary Composition: Binary composition is an operation of two elements of the set whose domains and co-domain are in the same set. The composition ‘*’ is called internal composition if a*b ∈ A, ∀a, b ∈ A and a*b is unique. The composition ‘o’ is called external If a o α ∈ V, for all a ∈ F and for all 𝛼∈ V and a o 𝛼 is unique. Vector Space: Let V is a non-empty set equipped with two binary operations ‘ .’ (external composition) defined as scalar multiplication and ‘+’ (internal composition) defined as addition of vectors. Then V is called a Vector space over a field F if it satisfies the following postulates: i.) Closure Law: (∝+𝛽)∈𝑉:𝑓𝑜𝑟 𝑎𝑙𝑙 ∝,𝛽𝜖𝑉 ii.) Associative Law: (∝+𝛽)+𝛾=∝+(𝛽+𝛾) iii.) Existence of Identity: There exists an element е𝜖 V such that ∝ + е = е + ∝ = ∝. iv.) Existence of Inverse: For each element ∝∈𝑉, there exist an element 𝛽 such that (∝+𝛽)=(𝛽+∝)= e v.) Commutative Law: (∝+𝛽)=(𝛽+∝) vi.) (Closure law with respect to scalar multiplication): a ∝∈V for all a ∈ F and for all ∝ ∈V vii.) a (∝+β)=a∝ +a β, for all a ∈ F and for all ∝ ,𝛽∈𝑉 viii.) (a + b) ∝ =a ∝ +b ∝ , for all a ∈ F and for all ∝ ∈𝑉 ix.) (ab)∝ =𝑎 (𝑏∝), for all a , b∈ F and for all ∝ ∈𝑉 x.) 1.∝ = ∝ ,for all ∝ ϵ V And 1 is the unity element of the field F.
munotes.in
Page 18
18 Linear algebra using python Example1: The set of complex numbers ‘C’ is a vector space over the field of real numbers R. Solution: Let X = a+ib ∈ C, Y = c+id ∈ C, Z = p+iq, where a, b, c, d, p, q ∈ R. i) Closure law: (X+Y) = (a+ib) + (c+id)=(a+c)+i(b+d) ∈C ii) Associative law: X+(Y+Z)=(X+Y)+Z L.H.S. = (a+ib) + ((c+id)+(p+iq)) = (a+ib)+((c+p)+i(d+q)) = (a+p+c) + i(b+d+q) = ((a+c)+p) + i ((b+d)+q) = ((a+c)+i(b+d)) + (p+iq) = ((a+ib) + (c+id)) + (p+iq) = (X+Y)+Z = R.H.S. iii) Existence of Identity: let X = a+ib ∈ C,∃ an element e = 0+0i ∈ C such that X + e = e+ X =X (a + ib) + (0 + 0i) = (0 + 0i) + (a + ib) = (a + ib) (a + 0) + i(b + 0) = (0 + a) + i(0+b) = (a + ib) iv) Existence of Inverse: Let X=(a+ib) ∈ C, ∃ an element Xᇱ = - (a + ib) ∈ C Such that X+𝑋ᇱ=𝑋ᇱ+X=e(where e =0+0i) (a + ib) + [-(a + ib)] = (-a + a) + i(-b + b) = 0+0i = e v) Commutative law: Let X=(a+ib)∈ C , Y = (c+id) ∈ C where a, b, c, d ∈ R. Consider X+Y=(a+ib)+(c+id) = (a+c)+i(b+d) = (c+a)+i(d+b) = (c+id)+(a+ib) = Y+X vi) Closure law w.r.t. scaler multiplication under vector addition: Let ∀ K ∈ R, ∀ X ∈ C, such that KX ∈ C, where K is any scaler value. Consider K X = K(a+ib) = (ka + ikb) = (𝑎ଵ+i𝑏ଵ)∈ C vii) Closure law w.r.to scalar multiplication under vector addition: K (X+Y) = K ((a+ib)+(c+id)) = K (a+ib) + K(c+id) =K X + KY viii.) Let ∀ kଵ,kଶ∈ R, X = (a+ib) ∈ C, Such that (kଵ+kଶ)X=(kଵ+kଶ)(a+ib) = kଵ(a+ib) +kଶ(a+ib) = kଵX +kଶX. munotes.in
Page 19
19
Vectors ix.) Let ∀ kଵ,kଶ∈ R, X = (a+ib) ∈ C, Such that (kଵ.kଶ) X = (kଵ.kଶ)(a+ib) = kଵ.(kଶ(a+ib) =kଵ.(kଶ(X)) x.) Multiplication with unity: ∀ X ∈ C, ∃1 ∈ R is the unity element such that 1.X=1.(a+ib) = (a+ib) = X Since, the set of complex numbers satisfies all postulates. Hence, the set of complex number ‘C’ is a vector space over the field of real number R. Example 2: Check whether the set of all pairs of real numbers of the form (1, x) with operation (1, y) + (1, yᇱ)=(1,y+yᇱ) and k(1, y)=(1, ky) is a vector space. Solution: Let (1,x) , ( 1, xᇱ) ∈Rଶ i.) Closure Property: Consider (1, xଵ) + (1,xଶ) = (1, xଵ+xଶ) = (1, xଵ+xଶ) ∈Rଶ as (xଵ+xଶ) ∈Rଶ ii.) Associative Property: Set of real numbers satisfies Associative Property. iii.) Existence of Identity: ∃(1, 0) ∈Rଶ and ∀(1, x) ∈Rଶ such that (1, 0) + (1, x) = (1, x) + (1, 0) = (1, x) iv.) Existence of Inverse: ∃(1,-x) ∈Rଶ, ∀(1,x) ∈Rଶ such that (1, x) + (1, -x) = (1, -x) + (1, x) = (1, 0) v.) Commutative Property: (1, x) , ( 1, xᇱ) ∈Rଶ such that (1,x) + (1, xᇱ)=(1, x+ xᇱ) = (1, x+ xᇱ) = (1, xᇱ+x) = (1, xᇱ) + (1, x) Hence commutative Property is satisfied vi.) Closure law w.r.t. scalar multiplication: k(1, y)=(1, ky), by the definition . vii.) Closure law w.r.to scalar multiplication under vector addition: a[(1, x) + (1, xᇱ)] = a[1, x+xᇱ] = [1, a(x+xᇱ)] ∈Rଶ, ∀a∈R ( by the definition of addition) viii.) (a + b)●(1, x) = [1, (a+b)x] (by the definition) and [1, (a + b) x] ∈Rଶ, ∀ a, b ∈Rଶ ix.) (a●b) [1, x] = [1, (a●b)x] ( by the definition ) = a(1, bx) = a (b[1, x]) x.) Multiplication with unity: 1●[1, x] = [1, 1●x] = [1, x] where 1∈R Since all the postulates for becoming the vector space satisfied and hence it is a vector space. munotes.in
Page 20
20 Linear algebra using python 2.11 LINEAR SYSTEMS-HOMOGENEOUS AND OTHERWISE Linear algebra is a systematic study of the theory and applications of linear system of equations. Consider the system of m linear equations 𝑎ଵଵ 𝑥ଵ + 𝑎ଵଶ 𝑥ଶ + - - - - - - + 𝑎ଵ 𝑥 = 𝑏ଵ 𝑎ଶଵ 𝑥ଵ + 𝑎ଶଶ 𝑥ଶ + - - - - - - + 𝑎ଶ 𝑥 = 𝑏ଶ ------------------------------------------------------- ------------------------------------------------------- 𝑎ଵ 𝑥ଵ + 𝑎ଶ 𝑥ଶ + - - - - - - + 𝑎 𝑥 = 𝑏 having n unknowns 𝑥ଵ , 𝑥ଶ , …… , 𝑥 . To determine whether the system has a solution or not, we check the ranks of the matrices, A = ⎝⎜⎜⎛ 𝑎ଵଵ 𝑎ଵଶ ....... 𝑎ଵ𝑎ଶଵ 𝑎ଶଶ ....... 𝑎ଶ........................................................................𝑎ଵ 𝑎ଶ ....... 𝑎⎠⎟⎟⎞ And B = ⎝⎜⎜⎛ 𝑎ଵଵ 𝑎ଵଶ ....... 𝑎ଵ 𝑏ଵ𝑎ଶଵ 𝑎ଶଶ ....... 𝑎ଶ 𝑏ଶ........................................................................𝑎ଵ 𝑎ଶ ....... 𝑎 𝑏⎠⎟⎟⎞ Where A is the coefficient matrix and B is the augmented matrix of the system of equations. Procedure to test the consistency of equations in n unknowns: Let the rank of A be r and rank of B be 𝑟ᇱ. 1.) If r ≠ 𝑟ᇱ , there is no solution of the system of equations. This implies that equations are inconsistent. 2.) If r = 𝑟ᇱ = n (number of unknowns), there is a unique solution. This implies that equations are consistent. 3.) If r = 𝑟ᇱ ˂ n, there is infinite number of solutions. This implies that equations are consistent. System of linear homogeneous equations: Consider the homogeneous linear equations munotes.in
Page 21
21
Vectors 𝑎ଵଵ 𝑥ଵ + 𝑎ଵଶ 𝑥ଶ + - - - - - - + 𝑎ଵ 𝑥 = 0 𝑎ଶଵ 𝑥ଵ + 𝑎ଶଶ 𝑥ଶ + - - - - - - + 𝑎ଶ 𝑥 = 0 ------------------------------------------------------- ------------------------------------------------------- 𝑎ଵ 𝑥ଵ + 𝑎ଶ 𝑥ଶ + - - - - - - + 𝑎 𝑥 = 0 To know the nature of the solutions of equation (ii), we check the rank of coefficient matrix A = ⎝⎜⎜⎛ 𝑎ଵଵ 𝑎ଵଶ ....... 𝑎ଵ𝑎ଶଵ 𝑎ଶଶ ....... 𝑎ଶ........................................................................𝑎ଵ 𝑎ଶ ....... 𝑎⎠⎟⎟⎞ Let rank (A) = r. 1.) If r = n, the equations (ii) have only trivial zero solution. This implies that 𝑥ଵ = 𝑥ଶ = ---- = 𝑥 = 0 2.) If r ˂ n, the equations (ii) have infinite number of solutions. We can conclude that for a homogeneous system of equations, if det (A) ≠ 0, there exists only a trivial zero solution otherwise infinitely many solutions will exist. Example 1 : Consider the following system of equations and Find the nature of solution without solving it. i.) x ଵ + xଶ = 6 and 2 x ଵ + 2xଶ = 12 ii.) x ଵ + xଶ = 5 and x ଵ - xଶ = 1 Solution: i.) The system of equations can be written in matrix form as ቀ1122ቁቀ୶భ୶మቁ = ൫ଵଶ൯ Coefficient matrix A = ቀ1122ቁ and Augmented matrix B = ቀ11 422 8ቁ Here det A = 0, rank A = 1 and rank B = 1, So r = rᇱ< n (number of variables) Hence there is infinite number of solutions for this system. ii.) Here A = ቂ111−1ቃ and B = ቀ11 51−1 1ቁ Since rank A = rank B = n(number of variables), r = rᇱ = n Hence there exists a unique solution of the system. munotes.in
Page 22
22 Linear algebra using python 2.12 SUMMARY In a very simple definition, vector can be assumed as an arrow that points in space. A vector that contains n elements is called n-vector. Vector addition satisfies algebraic properties like commutative and associativity. Scalar-vector multiplication stretches the direction of a vector and this process is called scaling. These properties of vectors give the data analyst a nice way to conceptualize many list of numbers in a visual way to be clear about patterns in data. 2.13 REFERENCE FOR FURTHER READING Linear algebra and its applications, Gilbert Strang, Cengage Learning, 4th edition, 2007. Exercise Q.1 For the given pairs of vectors ,find vector u + v, u – v , v – u ,2u + 3v , -2u – 7v (i) u = (2, 8) and v = (3, 1) (ii) u = (-1, 3) and v = (8, -2) (iii) u = (-3, 4) and v = (1, -2) (iv) u = (2, -9) and v = (-8, 1) Q.2 For each of the following pairs of vectors u and v, Evaluate their dot product u. v. (i)u = (2, 5) and v = (4, -1) (ii) u = (1, 2, -1) and v = (1,-1, 0) Q.3 Solve the following triangular system of linear equation : (i) 𝑥ଵ-3𝑥ଶ-2𝑥ଷ = 15 (ii) 2𝑥ଵ-3𝑥ଶ+5𝑥ଷ-2𝑥ସ =9 2𝑥ଶ+4𝑥ଷ = 8 5𝑥ଶ+𝑥ଷ-3𝑥ସ =9 10𝑥ଷ = 30 7𝑥ଷ-𝑥ସ =9 2𝑥ସ =8 Q.4 Determine whether the following set of vectors span vector space 𝑅ଷ (i)vଵ(2, 2, 2) , vଶ(0, 0, 3) , vଷ(0, 1, 1) (ii)vଵ(1,0,0) , vଶ(0,1,0) , vଷ(1,1,0) Q.5 Check whether the following sets are vector space or not: i.) {(x, y, z):x, y, z ∈ R, x + y + z = 0} ii.) All mxn matrices whose entries are real. munotes.in
Page 23
23 3 MATRIX Unit Structure: 3.0 Objectives 3.1 Introduction 3.2 Matrices 3.2.1 Definition 3.2.2 Column Space and Row Space 3.2.3 Transpose 3.2.4 Vectors 3.3 Multiplication in terms of vectors 3.3.1 Matrix-vector multiplication 3.3.2 Vector-matrix multiplication 3.4 Other concepts 3.4.1 Null Space 3.4.2 Computing sparse matrix-vector product 3.4.3 Linear Functions 3.4.4 Inner Product 3.4.5 Outer Product 3.4.6 From function inverse to matrix inverse 3.5 Summary 3.6 Exercise 3.7 References 3.0 OBJECTIVES After going through this chapter, students will able to learn To understand what are matrices To deal with various types of matrices using vectors To learn various concepts and applications of matrices using python munotes.in
Page 24
24 Linear algebra using python 3.1 INTRODUCTION This unit will take thorough out the concepts of matrices – some traditional while some are new in terms of vectors , various operations and other concepts. 3.2 MATRICES In this section definition of matrix will be reviewed and a new notation in terms of python list will be introduced. 3.2.1 Definition Traditionally matrices means some set of rows and columns with various entries like real numbers, complex number etc. For example : 101245−231൩ or ቂ1+𝑖−32+2𝑖3−1ቃ The first matrix is called as a 3x3 matrix over field F In first example above there are 3 rows and 3 columns. First row or Row 1 is [ 1 0 1] , similarly column 1 is 12−2൩ and so on. In general, a matrix with m rows and n columns is called mxn matrix. For a i,jth element is defined to the element in ith row and jth column . Traditionally if matrix is given by A, this element is written as Aij. Instead Python notation will be used throughout A[i,j]. So ,Row vector i will be : [ A[i, 0], A[i, 1], A[i, 2], · · ·, A[i,m − 1] ] and column vector j will be : [A[0, j], A[1, j], A[2, j], · · ·, A[n − 1, j] ] For example : if we consider same matrix 101245−231൩ then Row vector 1 will be : [[1,0,1] ] and column vector 1 will be [[1,2,-2]] Entire matrix can be represented as list of lists as : [[1,0,1], [2,4,5], [-2,3,1]] In general a matrix can be represented as list L : A[i, j] = L[i][j] for every 0 ≤ i < m and 0 ≤ j < n munotes.in
Page 25
25
Matrix 3.2.2 Column Space and Row Space Matrices can be viewed from various angles like pack of rows or pack of columns etc. There are two ways of interpreting a matrix in terms of vector space. Similarly, there are two vector spaces associated with any given matrix: Definition : For any matrix A : 1. Column space of A, written Col A, is the vector space spanned by the columns of M, 2. Row space of A, written Row A, is the vector space spanned by the rows of M. For example : if we consider same matrix 101245−231൩ then Col A will be span of [[1,2,-2], [0,4,3], [1,5,1]] And Row A will be span of [[ 1,0,1],[2,4,5], [-2,3,1]] 3.2.3 Transpose Transpose of a matrix means interchanging its rows and columns. Definition : The transpose of a matrix A, denoted by AT is defined by (AT)i,j = Aj,i for every i ,j . For example : transpose of matrix 101245−231൩ is 12−2043151൩ 3.2.4 Vectors Matrices can be represented as vectors . If AxB is a matrix over the field F then it can be represented as vector over F. Later it can be used to perform vector operations like addition of vectors, multiplication of scalar- vector. For example : if we consider matrices A = ቂ121215ቃ and B = ቂ0215−12ቃ then A + B = ቂ142707ቃ i.e corresponding elements get added. Note matrices should have same dimensions i.e number of rows and columns. Similarly, scalar matrix multiplication is : A = ቂ121215ቃ and scalar α = 3 then αA = ቂ3636315ቃ munotes.in
Page 26
26 Linear algebra using python 3.3 MULTIPLICATION IN TERMS OF VECTORS In this section the concept of matrix multiplication by vectors will be discussed. There are two ways in which this can be done : Matrix-Vector multiplication i.e multiply a matrix by vector. Vector- Matrix multiplication i.e multiply a vector by matrix. In the following section both these concepts will be discussed with two definitions for each : one in terms of dot products and another in terms linear combinations; both of which are equivalent. 3.3.1 Matrix-Vector Multiplication Definition : In terms of Linear Combination : Let M be RxC matrix over field F. Let be a vector of dimension C. Then M is the linear combination ∑𝑣 [𝑐](𝑐𝑜𝑙𝑢𝑚𝑛 𝑐 𝑜𝑓 𝑀) ∈ Note : 1) If M is R × C matrix but is not of dimension C i.e it is not a C-vector then the product M ∗ is illegal. 2) In the case of traditional-matrix, if M is m × n matrix over F then M ∗ is legal only if is n-vector over F i.e the number of columns of the matrix and the number of entries of the vector must be same. Example 1 : Suppose M = ቂ101213ቃ and = [1,−1,0] Then M ∗ can be computed since M is 2x3 and is 3x1 and result is : M ∗ = ∑𝑣 [𝑐](𝑐𝑜𝑙𝑢𝑚𝑛 𝑐 𝑜𝑓 𝑀) ∈ = 1[1,2] + (-1) [0,1] + 0[1,3] = [1,2] – [0,1] + [0,0] = [1,1] Example 2 : Suppose M = ቂ101213ቃ and = [1, 0] Then M ∗ cannot be computed since M is 2x3 and is 2x1 and result is not valid (by note 1) Definition : In terms of Dot Product: Let M be RxC matrix over field F. Let u be a vector of dimension C. Then Mu is the R-vector defined by u [𝑟] 𝑖.𝑒 𝑑𝑜𝑡 𝑝𝑟𝑜𝑑𝑢𝑐𝑡 𝑜𝑓 𝑢 𝑤𝑖𝑡ℎ 𝑟𝑜𝑤 𝑟 𝑜𝑓 𝑀 munotes.in
Page 27
27
Matrix 3.3.2 Vector -Matrix Multiplication In earlier section matrix-vector multiplication was discussed in terms of linear combinations of columns of a matrix. Next we see vector-matrix multiplication in terms of linear combinations of rows of a matrix. Definition : In terms of Linear Combination : Let M be RxC matrix over field F. Let w be a vector of dimension R . Then w M is the linear combination ∑𝑤 [𝑟](𝑟𝑜𝑤 𝑟 𝑜𝑓 𝑀) ∈ோ Note : If M is R × C matrix but w is not of dimension R i.e it is not a R-vector then the product w M is illegal. Example 3 : Suppose M = ቂ101213ቃ and w = [1,2] Then w M can be computed since M is 2x3 and is 1x2 and result is : w M = ∑𝑤 [𝑟](𝑟𝑜𝑤 𝑟 𝑜𝑓 𝑀) ∈ோ = 1[1, 0, 1] + 2[2 , 1, 3] = [1,0,1] + [4,2,6] = [5,2,7] Example 4 : Suppose M = ቂ101213ቃ and w = [1, 0,3] Then w M cannot be computed since M is 2x3 and is 1x3 and result is not valid (by note ) Next we will define vector- matrix multiplication in terms of dot product. Definition : In terms of Dot Product: Let M be RxC matrix over field F. Let u be a vector of dimension R. Then u*M is the C-vector defined by u [𝑐] 𝑖.𝑒 𝑑𝑜𝑡 𝑝𝑟𝑜𝑑𝑢𝑐𝑡 𝑜𝑓 𝑢 𝑤𝑖𝑡ℎ 𝑐𝑜𝑙𝑢𝑚𝑛 𝑐 𝑜𝑓 𝑀. Example 5 : Suppose M = 102132൩ and w = [2,−1] Then matrix- vector multiplication in terms of dot product is : 1st entry is dot product of row 1 [1,0] with w = [1,0].[2,-1] = 2-0 = 2 2nd entry is dot product of row 2 [2,1] with w = [2,1].[2,-1] = 4-1 = 3 3rd entry is dot product of row 3 [3,2] with w = [3,2].[2,-1] = 6-2 = 4 Hence finally M*w = [2, 3, 4] Similarly, vector-matrix multiplication in terms of dot product can be carried out. munotes.in
Page 28
28 Linear algebra using python 3.4 OTHER CONCEPTS In the following sections we will see some concepts related to matrices. 3.4.1 Null Space In earlier chapters we came across concept of homogeneous linear systems. It is the system where all values on right hand side of the equation are 0. We can define such a system as A*x = 0 i.e in the form of matrix-vector equation. In above equation right hand side of the equation is 0. Definition : The null space of the matrix A is defined by the set {v/ A*v = 0}. It is denoted by Null A From the above definition it can be seen that null A is basically set of all solutions of homogeneous linear system, hence it also forms a vector space. Example 6 : Suppose A = ቂ1012ቃ then null(A) is all vectors such that A*x = 0 i.e ቂ1012ቃ ∗ቂ𝑥ଵ𝑥ଶቃ=ቂ00ቃ which gives x1 = 0 and x1 + 2 x2 = 0 hence Null(A) = {(0,0)} Null(A) can also be computed easily using Row reduction form. 3.4.2 Computing Sparse Vector-Product Definition : Sparse matrix is defined as a matrix whose most of the elements are 0. In earlier sections we saw matrices in terms of vector and their products. For calculating product of matrices with vectors we can use either dot product or linear combinations definitions discussed earlier. But alone they cannot be conveniently used. Hence we combine both which leads to following definition : Definition : Let M be RxC matrix over field F. Let u be a vector of dimension C. Then M * u is the vector v of dimension R, such that for each r R, v[r] = ∑𝑀 [𝑟,𝑐]𝑢[𝑐] ∈ 3.4.3 Linear Functions Definition : Let U and V be vector spaces over a field F. Then a function f: U → V is called a linear function if following properties are satisfied : P1 : For any vector u Domain(f) and α F is any scalar then f(αu) = αf(u) P2 : For any vectors u,v Domain(f) then f(u+v) = f(u) + f(v) munotes.in
Page 29
29
Matrix Linear function are called as linear transformation. Let M be an R × C matrix over a field F, let f : FC → FR be defined by by f(x) = M ∗ x. Since the domain and co-domain are vector spaces, function f satisfies Properties P1 and P2. Thus f is a linear function. Example 7 : Let F be any field. Define function from F2 to F by (x, y) → x - y is a linear function. P1 : For any vector u = (x1,y1) F2 and α F be any scalar then consider f(αu) = f(α (x1,y1) ) = f( (αx1,αy1) ) = αx1 - αy1 = α (x1 - y1) = αf(u) P2 : For any vectors u =(x1,y1), v= (x2,y2) F2 then Consider f(u+v) = f ((x1,y1) + (x2,y2)) = f ((x1 + x2, y1+y2)) = (x1 + x2) – (y1+y2) = (x1 - y1) + (x2 – y2) = f ((x1,y1)) + f((x2,y2)) = f(u) + f(v) Hence from P1 and P2 f is a linear function. Result : Let U and V be vector spaces over a field F and f: U → V be a linear function, then f maps the zero vector of U to the zero vector of V Such functions is called kernel. Definition : Let U and V be vector spaces over a field F and f: U → V be a linear function then the set {v/f(v) = 0 } is called as kernel of f denoted by Ker f. The result of linear function can be extended to n number of vectors. 3.4.4 Inner Product Let u and v be two vectors of dimension D. Consider the “matrix-matrix product” uTv. The first matrix has one row and second matrix one column. By the dot-product definition of matrix-matrix multiplication, the product contains one single entry whose value is given by u.v Example 8 : Suppose A = [123] 123൩= [14] Since the final value of uTv is single entry it is called as inner product. 3.4.5 Outer Product Next suppose u and v be two vectors not necessary of same domain. Consider uTv : For each element of the domain u and each element of the domain of v, the s,t element of uTv is u[s]v[t]. Example 9 : Suppose A = ቈ𝑢𝑣𝑤[𝑥𝑦] = 𝑢𝑥𝑢𝑦𝑣𝑥𝑣𝑦𝑤𝑥𝑤𝑦൩ This type of product is called the outer product of vectors u and v. munotes.in
Page 30
30 Linear algebra using python 3.5 SUMMARY This chapter gives different concepts of matrices and their examples. It will create base for the next concept of basis. 3.6 EXERCISE 1. Compute the following matrix-vector products a. M = ቂ1−1201−2ቃ and = [2,−3,0] b. M = ቂ1−111ቃ and = [2,4] 2. For each of the following problems, answer whether the given matrix-matrix product is valid or not. If it is valid, give the number of rows and the number of columns of the resulting matrix (you need not provide the matrix itself). a. ቂ11001−2ቃ ቂ2−1210−1ቃ b. [110] ቂ24111−1ቃ T c. ቂ11001−2ቃ [10−1] T 3. Compute Matrix Matrix Multiplication : a. ቂ2243ቃ ቂ1−111ቃ b. [22−1] 32−261−1൩ 3.7 REFERENCES Coding the Matrix Linear Algebra through Applications to Computer Science Edition 1,PHILIP N. KLEIN, Newtonian Press (2013) Linear Algebra and Its Applications, Gilbert Strang, Cengage Learning, 4th Edition (2007). munotes.in
Page 31
31 4 BASIS Unit Structure: 4.0 Objectives 4.1 Introduction 4.2 Coordinate System 4.3 Two greedy algorithms for set of generators 4.4 Minimum Spanning Forest and GF(2) 4.5 Linear dependence 4.6 Basis 4.7 Dimension 4.7.1 Dimension and rank 4.7.2 Direct sum 4.7.3 Dimension and linear functions 4.8 The annihilator 4.9 Summary 4.10 Exercise 4.11 References 4.0 OBJECTIVES After going through this chapter, students will able to learn To understand spanning vectors To understand concept of Linear dependence and independence To learn concept of basis and dimension 4.1 INTRODUCTION After learning the concepts of vector space, linear function in earlier chapters in this chapter we will learn concept of basis. Basis has several properties which can be further used to justify concepts like linear dependence, independence, maximal linearly independent set etc. The basis also tells us about the smallest set of vectors needed to span a vector space. Thus it helps to give information about structure of a vector space. munotes.in
Page 32
32 Linear algebra using python 4.2 COORDINATE SYSTEM A coordinate system is defined as a method for recognizing the location of a point. Most of the coordinate systems use two numbers i.e. a coordinate to detect a point or a location. These numbers indicate the distance between the point and some fixed point of reference called the origin. For a vector space V in vector analysis, a coordinate system is indicated by a set of vectors a1,a2,…an of V such that every vector of the vector space can be written as linear combination of these vectors . That is there exists scalars or real numbers α1, α 2,… α n such that = α1a1 + α2a2 + … + αnan where V (any vector) From discussion above the vector can be represented by [α1,α2,… ,αn ] of coefficients. These coefficients are called coordinates and the vector [α1,α2,… ,αn ] is called the coordinate representation of in terms of a1,a2,…an.. Also, this representation of is unique. Example 1 : if we consider the vector [1, 3, 5, 2] it can be represented as : [1, 3, 5, 2] = 1 [1, 0, 0, 0] + 3 [0, 1, 1, 0] + 2 [0, 0, 1, 1] Hence the coordinate representation of in terms of [1, 0, 0, 0] , [0, 1, 1, 0] and [0, 0, 1, 1] is [1, 3, 5, 2] 4.3 TWO GREEDY ALGORITHMS FOR SET OF GENERATORS Suppose we want to answer this question : For a given vector space V, what is the minimum number of vectors whose linear span is V? To answer this, in this section we consider two algorithms 1. Grow algorithm def Grow(V) B = repeat while possible : Find a vector in V that is not in Span (B) and add it to B The algorithm halts when there is no more vector to add in B. By this time we can find the generating set. Example 2: Consider V = ℝ3. In first iteration we add vector [1, 0, 0] to B . Next since [0, 0, 1] does not belong to Span(B) we add it to B. thus B = { [1, 0, 0], [0, 0, 1]}. Similarly in 3rd iteration we add [0, 1, 0] to B as it does not belong to span of B. Next if we consider any vector in ℝ3 munotes.in
Page 33
33
Basis We can see it can be written as linear combination of either all or some of vectors of B. Hence there nr u o more vector to add to B, hence the algorithm stops. 2. Shrink algorithm Exactly opposite to grow as name says we remove an element in every step. def Shrink(V) B = some finite set of vectors in V such that span(B) = V repeat while possible : Find a vector in V such that Span (B- {v} ) = V and remove it from B The algorithm halts when there is no more vector to remove from B such that spanning property is still satisfied. By this time we can find the generating set. Example 2: Consider V = ℝ3 and B ={ [1, 0, 0], [0, 0, 1],[0, 1, 0], [3, 2, 0], [0, 3, 1]}. In first iteration we remove vector [3, 2, 0] from B since [3, 2, 0 ] = 3[1, 0, 0] +2 [0, 1, 0]. Next we remove [0, 3, 1] as it belong to Span(B). Thus B = {[1, 0, 0], [0, 0, 1], [0, 1, 0]} . Now the algorithm stops since there is no more vector to remove. 4.4 MINIMUM SPANNING FOREST AND GF(2) In this section we will see grow and shrink algorithm using graph theory that is minimum spanning problem. Suppose we are given a graph with weights as below:
Suppose vertices represent cities and edges represent distances to travel from one city to another. Our goal is to travel from one city to another in covering all cities with minimum distance
munotes.in
Page 34
34 Linear algebra using python To find minimum distance there are several algorithms but we will use grow and shrink algorithm Grow algorithm def Grow(G) B = Consider the edges in order from low to high For each edge e: If endpoint of e is not yet connected via edges add it to B For above graph weights in increasing order are : 8 7 4 3 3 2 1 The solution obtained is 8 7 4 2 Shrink algorithm def shrink(G) B = { all edges } Consider the edges in order from high to low For each edge e: If pair of nodes are connected via B – {e}: Remove e from B For above graph weights in increasing order are : 1 2 3 3 4 7 8 The solution obtained is 1 2 3 3 4 The Grow and Shrink algorithms for minimum spanning forest look like those algorithms used for finding a set of generators for a vector space. In this section, we describe how to model a graph by means of vectors over GF(2). Let C = {set of vertices of graph} = {0,1,2,3,4} be the set of nodes A subset of C is characterized by the vector with ones in the corresponding entries and zeroes elsewhere. A subset of C is represented by the vector with ones in the corresponding entries and zeroes elsewhere. munotes.in
Page 35
35
Basis Hence the vectors corresponding to all the edges in our graph are : Edge Vector 0 1 2 3 4 {0,4} 1 1 {0,3} 1 1 {1,3} 1 1 {3,4} 1 1 {1,2} 1 1 {2,3} 1 1 In general, a vector with 1’s in entries x and y is the sum of vectors corresponding to edges that form an x-to-y path in the graph. Thus, for these vectors, it is easy to tell whether one vector is in the span of some others. 4.5 LINEAR INDEPENDENCE Lemma (Superfluous-Vector Lemma): For any set S and any vector v ∈ S, if v can be written as a linear combination of the other vectors in S then Span (S−{v}) = Span S Definition: Let V be a vector space .Then vectors v1, . . . , vn in V are called as linearly dependent if the zero vector can be written as a nontrivial linear combination of these vectors. That is 0 = α1v1 + · · · + αnvn Here we denote the linear combination as a linear dependency in v1, . . . , vn. Example .3: The vectors [1, 0, 0], [0, 3, 0], and [3, 9, 0] are linearly dependent, as shown by the following equation: 3 [1, 0, 0] + 3 [0, 3, 0] − 1 [3, 9, 0] = [0, 0, 0] Thus 3 [1, 0, 0] + 3 [0, 3, 0] − 1 [3, 9, 0] is a linear dependency in [1, 0, 0], [0, 3, 0], and [3, 9, 0]. Example 4: The vectors [1, 0, 0], [0, 3, 0], and [0, 0, 5 ] are linearly independent. Since if we consider α1 [1, 0, 0] + α2 [0, 3, 0] + α3 [0, 0, 5] = [0, 0, 0] Then all scalars α1, α2, α3 all are 0. munotes.in
Page 36
36 Linear algebra using python Properties of linear (in)dependence 1. A subset of a linearly independent set is linearly independent. 2. Let v1, . . . , vn be vectors. A vector vi belongs to the span of the other vectors if and only if the zero vector can be written as a linear combination of v1, . . . , vn in which the coefficient of vi is nonzero. 3. The vectors obtained by the Grow algorithm are linearly independent. 4. The vectors obtained by the Shrink algorithm are linearly independent. 4.6 BASIS In earlier sections we saw the Grow algorithm and the Shrink algorithm where each of them finds a set of vectors spanning the vector space V. In addition in each case, the set of vectors found is linearly independent. Next we define basis of vector space one of the most important concept in linear algebra. Definition: Let V be a vector space. A basis for V is a linearly independent set of generators for V. In other words, a set B of vectors of V is a basis for V if B satisfies two properties: PB1 Span B = V, (Spanning) and PB2 B is linearly independent. (Independent) Example 5: Let V the vector space spanned by [1, 0, 0], [0, 1, 1], and [1, 1, 1]. Then the set {[1, 0, 0], [0, 1, 1], [1, 1, 1]} is not a basis for V because it is not linearly independent as [1, 1, 1] = [1, 0, 0] + [0, 1, 1] However, the set {[1, 0, 0], [0, 1, 1]} is a basis as it satisfies the above two properties. Lemma : The standard generators for FD form a basis. Lemma (Unique-Representation Lemma): Let V be a vector space and B be a basis of V, then every vector in V can be uniquely represented as linear combination of vectors of B. i.e Let B = {a1, . . . , an} be a basis for a vector space V. For any vector v ∈ V, there is exactly one representation of v in terms of the basis vectors. munotes.in
Page 37
37
Basis 4.7 DIMENSION After defining basis in earlier section lets now see the number of elements in any given basis. Before that let us see some results with respect to basis. Lemma (Morphing Lemma): Let V be a vector space. Suppose S is a set of generators for V, and B is a linearly independent set of vectors belonging to V. Then |S| ≥ |B|. Theorem (Basis Theorem): Let V be a vector space. All bases for V have the same size. Theorem : Let V be a vector space. Then a set of generators for V is a smallest set of generators for V if and only if the set is a basis for V. Definition : Let V be a vector space. Then the dimension of V is defined to be the size of a basis for V. The dimension of a vector space V is written dim V. If we consider example 5 then dim V = 2 since it has basis B containing 2 vectors i.e.[1, 0, 0] and [0, 1, 1 ] Example 6: One basis for ℝ3 is the standard basis: {[1, 0, 0], [0, 1, 0], [0, 0, 1]}. Hence the dimension of R3 is 3. 4.7.1 DIMENSION AND RANK Definition : Rank of a set S of vectors is defined as the dimension of Span S. We denote rank S for the rank of S. Proposition : For any set S of vectors, rank S ≤ |S|. Definition : For a matrix M, the row rank of M is defined as the rank of its rows, and the column rank of M is defined as the rank of its columns. Definition : For a matrix M, the row rank of M is the dimension of Row M, and the column rank of M is the dimension of Col M. Example 7 : Consider the matrix M = 100111൩ Here row vectors are {[1, 0], [0, 1], [1, 1]} which are linearly dependent .but if we remove [1, 1] then vectors become independent. Hence Row rank = 2 Similarly column vectors are {[1, 0, 1] ,[0,1,1]} which are linearly independent as discussed earlier. Hence column rank = 2 munotes.in
Page 38
38 Linear algebra using python In any case we have Row Rank = Column Rank Definition : The rank of a matrix is defined to be its common value of column rank which is equal to its row rank. Lemma (Superset-Basis Lemma): For any vector space V and any linearly independent set B of vectors, V has a basis that contains all of B. The Dimension Principle Using the Superset-Basis Lemma we can prove the following principle. Lemma (Dimension Principle): If V is a subspace of vector space W then PD1: dim V ≤ dim W, and PD2: if dim V = dim W then V = W. Example 8: Suppose W = Span {[1, 0], [1, 1]}. Clearly V is a subspace of ℝ2. However, the set {[1, 0], [1, 1]} is linearly independent, so dim V = 2. Since dim ℝ2 = 2, hence by PD2 V = ℝ2. 4.7.2 DIRECT SUM We are acquainted with the idea of adding vectors—now we study about adding of vector spaces. These ideas will be advantageous in proving a fundamental theorem in the next section—the Kernel-Image Theorem. Let U and V be two vector spaces consisting of D-vectors over a field F. Definition : If U and V have only the zero vector in common then we define the direct sum of U and V to be the set {u + v : u ∈ U, v ∈ V} We write direct sum of U and V as U ⊕V That is, U ⊕V is the set of all sums of a vector in U and a vector in V. Example 9 : Let U = span{[1,0]} i.e X-axis and V = span{[0,1]} i.e Y-axis Then U ⊕V = ℝ2 Result : The direct sum U ⊕V is a vector space. Lemma : The set of generators for V ⊕W is the union of a set of generators of V and a set of generators of W Lemma (Direct Sum Basis Lemma): The union of a basis of U and a basis of V is a basis of U ⊕V. Corollry :Any vector in U⊕V has a unique representation as u + v where u ∈ U, v ∈ V. Definition : U and V are said to be complementary subspaces of W, if U ⊕V = W munotes.in
Page 39
39
Basis 4.7.3 DIMENSION AND LINEAR FUNCTION In this section we will see how dimension can be related to linear functions studied in earlier sections. We will devise a criterion for invertibility of a linear function. That in turn will provide a criterion for matrix invertibility. These criteria will construct an important theorem, the Kernel-Image Theorem. We have studied earlier that linear function f : V →W is invertible if (i) f is one-to-one and (ii) f is onto. By the One-to-One Lemma, we know that f is one-to-one iff its kernel is trivial. Similarly there is a criterion for checking if a linear function is onto. Recall : image of f is Im f = {f(v) : v ∈ V}. Thus f is onto iff Im f = W. Also Im f is a subspace of W. By the Dimension Principle, f is onto iff dim Im f = dim W. Hence We can conclude: A linear function f : U → W is invertible if dim Ker f = 0 and dim Im f = dimW. The Kernel-Image Theorem For any linear function f : V →W, dim Ker f + dim Im f = dim V Theorem (Linear-Function Invertibility Theorem): Let f : V →W be a linear function. Then f is invertible if and only if dim Ker f = 0 and dim V = dim W. Theorem (Rank-Nullity Theorem): For any n-column matrix A, rank A + nullity A = n Example 10 Let T: ℙ1→ℝ be the linear transformation defined by T(p(x))=p(1) for all p(x)∈ ℙ1 . Find the kernel and image of T, Verify the kernel–Image theorem. We will first find the kernel of T : It consists of all polynomials in ℙ1 that have 1 for a root. ker(T)={p(x)∈ℙ1 | p(1)=0}={ax+b | a,b∈R and a+b=0}={ax−a | a∈R} Therefore a basis for ker(T) is {x−1} and dimension = 1 Notice that this is a subspace of ℙ1. munotes.in
Page 40
40 Linear algebra using python Now consider the image. It consists of all numbers which can be obtained by evaluating all polynomials in ℙ1 at 1. im(T)={p(1) | p(x)∈P1}={a+b | ax+b∈P1}={a+b | a,b∈R} = ℝ Therefore a basis for im(T) is {1} and dimension is 1 Dim(ℙ1) = 2 = 1+1 = dim(ker T) + Dim (im T) Hence Kernel-Image theorem verified. 4.8 THE ANNIHILATOR Definition : For a subspace V of Fn, the annihilator of V, denoted as Vo, is defined as Vo = {u ∈ Fn : u · v = 0 for every vector v ∈ V} Results : 1. Let a1, . . . , am be generators for V, and let A = [a1, a2,….,am]T Then Vo = Null A. 2. (Annihilator Dimension Theorem): Let V and Vo be subspaces of Fn, where F is a field , then dim V + dim Vo = n 3. (Annihilator Theorem): (Vo)o = V (The annihilator of the annihilator is the original space.) 4.9 SUMMARY In this chapter we studied about basis of a vector space, its dimension and their properties . 4.10 EXERCISE 1. Let V = Span {[0, 0, 1], [1, 0, 1], [2, 1, 1]}. For each of the following vectors, show it belongs to V by writing it as a linear combination of the generators of V. (a) [2, 1, 4] (b) [1, 1, 1] (c) [5, 4, 3] (d) [0, 1, 1] munotes.in
Page 41
41
Basis 2 Let V = Span {[0, 1, 0, 1], [0, 0, 1, 0], [1, 0, 0, 1], [1, 1, 1, 1]} where the vectors are over GF(2). For each of the following vectors over GF(2), show it belongs to V by writing it as a linear combination of the generators of V. (a) [1, 1, 0, 0] (b) [1, 0, 1, 0] (c) [1, 0, 0, 0] 3 For each of the set given below, show the given vectors over R are linearly dependent. (a) [1, 2, 0], [2, 4, 1], [0, 0, −1] (b) [2, 4, 0], [8, 16, 4], [0, 0, 7] (c) [0, 0, 5], [1, 34, 2], [123, 456, 789], [−3, −6, 0], [1, 2, 0.5] 4 For each of the following matrices, (a) give a basis for the row space (b) give a basis for the column space, and (c) verify that the row rank equals the column rank. Justify your answers. (a) 100111൩ (b) ቂ120021ቃ (c) 102011110൩ 5 Verify Rank – Nullity theorem (a) T : ℝ2 → ℝ2 defined by T(x, y) = x+y (b) T : ℝ2 → ℝ3 defined by T(x, y) = (x, x+y, y) 4.11 REFERENCES Coding the Matrix Linear Algebra through Applications to Computer Science Edition 1,PHILIP N. KLEIN, Newtonian Press (2013) Linear Algebra and Its Applications, Gilbert Strang, Cengage Learning, 4th Edition (2007). munotes.in
Page 42
42 Linear algebra using python 5 GAUSSIAN ELIMINATION Unit Structure: 5.0 Objectives 5.1 Introduction 5.2 Echelon Form 5.3 Gaussian Elimination over GF(2) 5.4 Solving a matrix-vector equation using Gaussian elimination 5.5 Finding a basis for the null space 5.6 Factoring Integers 5.7 Summary 5.8 References 5.0 OBJECTIVES After going to this chapter, you will be able to: i.) Solve a set of simultaneous linear equations using Gauss elimination, ii.) Perform elementary row operations to produce zeros below the diagonal of the coefficient matrix to reduce it to echelon form. iii.) Find basis for the null space. 5.1 INTRODUCTION Given a linear system expressed in matrix form AX = B, where A is coefficient matrix and X is variable matrix. Gaussian elimination method is used to solve a system of linear equations by performing elementary row operations. Elementary row operations are categorized as: a.) Interchange any two rows; b.) Multiply a row by a nonzero constant; c.) Add a multiple of one row to another row. This row reduction algorithm continues till we get 0s (i.e., zeros) on the lower left-hand corner of the matrix as much as possible. That means the obtained matrix should be an upper triangular matrix. 5.2 ECHELON FORM Pivot: A pivot is the first non-zero element in a row and leading coefficient in a column with all the rows below containing 0's. Echelon Form of a matrix: There are two types of Echelon form of a matrix: i.) Row Echelon form: A matrix is said to be in row echelon form (ref) when it satisfies the following conditions: The first non-zero element is 1. munotes.in
Page 43
43
Gaussian Elimination Each leading entry is in a column to the right of the leading entry in the previous row. Rows with all zero elements, if any, are below rows having a non-zero element. ii.) Reduced row Echelon form: A matrix is said to be in reduced row echelon form (ref) when it satisfies the following conditions: • The matrix is in its row echelon form. • The leading entry in each row is the only non-zero entry in its column. Uses of Echelon form: • If a matrix is in echelon form, the non-zero rows form a basis for the row space Example: A = ൦2310040100960000൪ then the rows [ 2 3 1 0], [0 4 0 1] and [ 0 0 9 6] are the basis of the row space. • If an echelon form of a matrix has neither pivots in all rows nor all columns, the given set of vectors are linearly dependent. let V = {(1, 1, 1), (1, 2, 3), (1, 4, 7)} we compute A = 111123147൩ ~ 111013000൩ since A has neither pivots in all rows nor in all columns, the set is linearly dependent. • The number of non-zero rows in row echelon form of a matrix is equal to rank of the matrix. Example A = 123234357൩ ~ 1230−1−2000൩ [by performing elementary row operations] The number of non-zero rows = 2, hence the rank of the matrix A = 2. 5.3 GAUSSIAN ELIMINATION OVER GF(2) Gaussian elimination is very simple process for matrices over GF(2). The required row operations consist only XOR of two rows and swapping of two rows. Solving linear systems over GF(2) is of particular interest in cryptography and crypto-analysis. munotes.in
Page 44
44 Linear algebra using python The Gaussian elimination over GF(2) on a matrix A requires elementary column operations rather than elementary row operations. Let us take an example: Let Q = {6, 42, 105, 20, 63} and P = {2, 3, 5, 7} We have, 6=2ଵ3ଵ57 42=2ଵ3ଵ57ଵ 105=23ଵ5ଵ7ଵ 20=2ଶ35ଵ7 63=23ଶ57ଵ We define A as A= ⎣⎢⎢⎢⎡11001101011120100201⎦⎥⎥⎥⎤ (mod 2) A= ⎣⎢⎢⎢⎡11001101011100100001⎦⎥⎥⎥⎤ Performing elementary column operations and mark each row which has a point Since Aଵଶ=1,and cଶ⟶cଶ+cଵ, we get ⎣⎢⎢⎢⎡10001001011100100001⎦⎥⎥⎥⎤ Again performing cଷ⟶cଷ+cଶ,and cସ⟶cସ+cଶ, we get ⎣⎢⎢⎢⎡10001001011100100001⎦⎥⎥⎥⎤ Now performing cଵ⟶cଵ+cସ, we get ⎣⎢⎢⎢⎡10001001010000101001⎦⎥⎥⎥⎤ munotes.in
Page 45
45
Gaussian Elimination Note that row 5 has not been used, since Aହଵ= Aହସ=1, row 5 and all rows for which A୧ଵ=1 and A୧ସ=1 are dependent. From the above matrix we see that rows 1, 2, and 5 are dependent. If we sum row1, row2, and row5 in GF(2), we obtain a zero row. i.e. 1 0 0 0 Row 1(Qଵ=6) 0 0 0 1 Row 2(Qଶ=42) 1 0 0 1 Row 5(Qହ=63) ______ 0 0 0 0 This implies that R={Qଵ,Qଶ,Qହ} and product QଵQଶQହ forms perfect square. QଵQଶQହ = 6*42*63 = 126ଶ 5.4 SOLVING A MATRIX-VECTOR EQUATION USING GAUSSIAN ELIMINATION Consider a system of linear equation of n unknowns and n equations as aଵଵxଵ + aଵଶxଶ + ............+ aଵ୬x୬ = bଵ aଶଵxଵ + aଶଶxଶ + ............+ aଶ୬x୬ = bଶ . . . a୬ଵxଵ + a୬ଶxଶ + ............+ a୬୬x୬ = b୬ Step 1: To eliminate 𝐱𝟏 from second, third,……𝐧𝐭𝐡 equations: Assuming 𝐚𝟏𝟏 ≠ 0, we eliminate xଵ from the second equation by subtracting 𝐚𝟐𝟏/𝐚𝟏𝟏 times the first equation from the second equation. Similarly we eliminate 𝐱𝟏 from the third equation by subtracting 𝐚𝟑𝟏/𝐚𝟏𝟏 times the first equation from the third equation. By proceeding in the similar way, we get the following new system of equations as, aଵଵxଵ + aଵଶxଶ + ............+ aଵ୬x୬ = bଵ aଶଶᇱ xଶ + ............+ aଶ୬ᇱx୬ = bଶᇱ . . . a୬ଶᇱ xଶ + ............+ a୬୬ᇱx୬ = b୬ᇱ munotes.in
Page 46
46 Linear algebra using python From the above it is clear that, the first equation is called pivotal equation and aଵ is called first pivot. Step 2: To eliminate 𝐱𝟐 from the third equation: Assuming aଵଶᇱ ≠ 0, we eliminate xଶ from third equation by subtracting (aଷଶᇱ/aଶଶᇱ) times the second equation from the third equation. Thus we get the following new system as, aଵଵxଵ + aଵଶxଶ + ............+ aଵ୬x୬ = bଵ aଶଶᇱ xଶ + ............+ aଶ୬ᇱx୬ = bଶᇱ . . . + …………………..+ a୬୬" x୬ = b୬" Step 3: To evaluate the unknowns: The values of unknowns xଵ ,xଶ ,.................x୬ are found from the above reduced system by back substitution. Gauss Elimination Method Example 1: Solve the following system of equations by Gaussian elimination method: 2x + y + z =10; 3x + 2y + 3z =18; x + 4y + 9z = 16 Solution: 2x + y + z =10 ------------------(i) 3x + 2y + 3z =18----------------(ii) x + 4y + 9z = 16------------------(iii) Multiplying equation (iii) by 2 2x + 8y + 18z = 32-------(v) Subtracting equation (i) from (iv) 7y + 17z = 22 Performing 7 * (ii) + (v) we get, 2x + y + z = 10----------(i) y + 3z = 6-----------(iv) 4z = 20 ------------(vi) from equation(vi), we get z = ଶସ = 5 using back substitution method, we get, y = -9 and x = 7. ∴ x = 7, y = -9 and z = 5 munotes.in
Page 47
47
Gaussian Elimination Example 2: Solve the following system of equations by Gaussian elimination method: y-z = 3: -2x + 4y – z =1: and -2x + 5y – 4z = -2 Solution: Consider -2x + 4y – z =1----------------(i) -2x + 5y – 4z = -2--------------(ii) y-z = 3----------------------------(iii) Subtracting equation (ii) from equation (i), we get -2x + 4y – z =1-----------------(i) -y + 3z = 3-----------------(iv) y – z = 3-----------------(iii) Adding equation (iii) and equation (iv), y-z+-y + 3z = 3+3 2z = 6 ⇒z = ଶ = 3 ⇒ z = 3 Substituting z =3 in equation (iv), -y + 3(3) = 3 ⇒ -y = 3 – 9 ⇒ -y = - 6 ⇒y =6 Substituting y = 6 and z = 3 in equation (i), ⇒ -2x + 4(6) – 3 = 1 ⇒ -2x = 1 – 24 + 3 ⇒ -2x = -20 ⇒ x = ିଶିଶ= 10 The solution of the given set of equations are x = 10, y = 6 and z = 3. Example 3: Solve the following system of equations by Gaussian Elimination method: 5x + 4y - z = 0; 10y – 3z = 11; z = 3; Solution: Given the system of equations are, 5x + 4y – z = 0------------------(i) 10y - 3z = 11--------------(ii) z =3----------------(iii) Performing back substitution, z = 3. Putting value of z in equation (ii), We get, 10y - 3(3) = 11 ⇒ 10y = 11 + 9 ⇒ 10y = 20 ⇒ y = ଶଵ = 2 Substituting values of y and z in equation (i), 5x + 4(2) – 3 = 0 ⇒ 5x = 3 – 8 ⇒ 5x = -5 ⇒ x = ିହହ = -1 ∴ x = -1, y = 2 and z = 3. munotes.in
Page 48
48 Linear algebra using python 5.5 FINDING A BASIS FOR THE NULL SPACE This topic explains you how to find the basis for the null space of a mxn matrix A using Gaussian Elimination method. We have A⦁X = 0, either the solution is unique and X = 0 is the only solution or there are infinitely many solutions, which can be parametrized by non-pivotal elements. The basis of a null space of a matrix A is defined as Null (A) ={V: A⦁V = O}. The dimension of the null space of A is called nullity of A. To find basis for the null space, we convert the coefficient matrix into row echelon form. Example 1: Let A= ቂ−4−1−3−2040−1ቃ. Find basis for the null space of A. Solution: Let X= {(xଵ,xଶ,xଷ,xସ): A⦁X=O} is a basis for the null space of A. Then ቂ−4−1−3−2040−1ቃ.൦xଵxଶxଷxସ൪ =O Matrix A is in row echelon form: Hence -4xଵ−xଶ−3xଷ−2xସ=0−−−−−−−−−−−−(i) and 4xଶ−xସ=0−−−−−−−−−−−−−−−−(ii) ⇒xସ=4xଶ Substituting xସ equation (i), we get -4xଵ−9xଶ−3xଷ=0 ⇒3xଷ=−4xଵ−9xଶ Writing vector components xଵ,xଶ,xଷ and xସ in the following manner, xଵ=1xଵ+0xଶxଶ=0xଵ+1xଶxଷ=ିସଷxଵ+ିଽଷxଶxସ=0xଵ+4xଶ = xଵ⎣⎢⎢⎡10ିସଷ0⎦⎥⎥⎤ + xଶ⎣⎢⎢⎡01ିଽଷ4⎦⎥⎥⎤ Since xଵ and xଶ are arbitrary, the basis of null space of A is span of {(1, 0, ିସଷ, 0), (0, 1, ିଽଷ, 4)}. 5.6 FACTORING INTEGERS The unique factorization theorem: Every positive integer a>1 can be expressed uniquely as a product of positive primes. munotes.in
Page 49
49
Gaussian Elimination To find a nontrivial factor of a composite number n is the main concern. The simplest factoring algorithm is the trial division method which tries all the possible divisors of n to complete prime factorization: n = pଵpଶ.....p୰ Algorithm for factoring integer n by trial divisions: [1] Input n and set r 0, k 2. [2] If n = 1, go to step [5]. [3] q n/k and t n (m0d k). If t ≠ 0. Go to [4]. rr+1, p୰k, nq, go to [2]. [4] If q > k, then kk+1, and go to [3]. rr+1, p୰n. [5] Exit; terminate the algorithm. An improvement of algorithm is to make use of an auxiliary sequence of trial divisors: 2 = d< dଵ1. Then by unique factorization theorem, n can be expressed as product of positive primes. Let n = pଵభpଶమ..........p୰౨where 1
Page 50
50 Linear algebra using python Euclidian Algorithm: Euclidian algorithm enables us to find the actual value of the greatest common divisor d of two given integers a and b and also to find integers x and y such that d = x⦁a+y⦁b Example: Find (26,118) and express it in the form 26x+118y, where x and y ∈Z. Solution: We have, 118 = 26*4+14 ⇒26 = 14*1+12 ⇒14 = 12*1+2 ⇒12 = 2*6+0 Hence the last non-zero remainder is 2 = (26, 118). From the last we get, 2 = 14-12*1 = 14-12 ⇒ 2 = 14 - (26 - 14) = 2*14 – 26 ⇒ 14 = 118 - (26)*4 ⇒2 = 2[118 - (26)*4] – 26 ⇒2 *118 – 9*26-------------------(i) Hence (26, 118) = 2 Equation(i) is in the form of 26x+118y, by comparison, we get, x = 9 and y = 2 Example 2: Find the number of distinct positive integral divisors and their sum for the integers 56700. Solution: Expressing 56700 as a product of prime integers as, 56700=2ଶ∗3ସ∗5ଶ∗7 Here pଵ=2,pଶ=3,pଷ=5,pସ=7,αଵ=2,αଶ=4,αଷ=2,αସ=1 Then, number of distinct positive integral divisors of 56700 is T(56700) = (2+1) (4+1) (2+1) (1+1) = 90 And the sum of all distinct positive integral divisors σ(56700)=ଶమశభିଵଶିଵ∗ଷరషభିଵଷିଵ∗ହమశభିଵହିଵ∗భశభିଵିଵ =7*121*31*8 = 210056. munotes.in
Page 51
51
Gaussian Elimination 5.7 SUMMARY Any matrix can be transformed to reduced row echelon form by using Gaussian elimination method. This is particularly useful for solving systems of linear equations. The echelon form of a matrix isn’t unique, which means there are infinite answers possible after performing row reduction. But the reduced row echelon form is unique, which means row-reduction on a matrix will produce the same answer no matter how you perform the same row operations. The method can be applied even if the coefficient matrix is singular matrix or rectangular matrix. Gaussian elimination is also needed to determine the rank of a matrix. 5.8 REFERENCES Linear Algebra and its Applications, David C Lay, Pearson Education India; 3rd Edition, 2002. Exercise Q.1: Solve the following system of linear equations by Gaussian-Elimination method: i.) x + y = 3 and 3x – 2y = 4 ii.) x + y + z = 3; 2x + 3y + 4z = 9; x – 2y + 3z = 2 iii.) x + y – z = 9; -x – 2z = 2; y + 3z = 3 Q. 2: Find the basis for null spaces of the following matrices: i.) 103022000 246 146 ൩ ii.)0004−118−23 −1−1−1൩ munotes.in
Page 52
52 Linear algebra using python 6 INNER PRODUCT AND ORTHOGONALITY Unit Structure: 6.0 Objectives 6.1 Inner Product 6.1.1 Norm of a Vector 6.1.2 Norm of distance of two vectors 6.2 Orthogonality 6.3 Projection 6.4 Orthogonal set of generators 6.5 Orthogonal Complement 6.6 Summary 6.7 Reference 6.0 OBJECTIVES: After going to this chapter, you will be able to: • Find inner product of two vectors. • Determine whether the given vectors are orthogonal to each other or not. • Construct orthogonal set of generators. • Find orthogonal complement of any vector v. 6.1 INNER PRODUCT: Let u = ( uଵ ,uଶ,…………….,u୬ ) and v = ( vଵ ,vଶ,…………….,v୬ ) are two n-vectors of a real vector space. The inner product of u and v is given by the sum of the products of the coordinates with same index. It is also defined as the dot product of corresponding components of u and v. It is denoted as . = uଵvଵ+ uଶvଶ+………+ u୬v୬. The inner product of two vectors satisfies the following properties: i. < u, u > ≥ 0 ⇒ < u,u > = 0 iff u = 0 ii. < u, v > = < v, u > (symmetry) iii. < u + w, v > = < u, v > + (linearity) iv. < u, w + v > = + (linearity) v. < 𝛼u, v > = 𝛼 < u, v> (homogeneity) munotes.in
Page 53
53
Inner Product and
Orthogonality Any linear space that satisfies the above postulates is called inner product space. 6.1.1 Norm of a Vector: The norm of a vector v ∈ V is defined as the positive square root of the inner product of the vector with itself. The norm of a vector v is written as ||v||. || v || = √ = ඥvଵଶ+ vଶଶ+⋯+ v୬ଶ 6.1.2 Norm of distance of two vectors: Norm of distance between two vectors u and v is defined as d(u, v) = || u-v || = < u-v, u-v > = ඥ(u−v)⦁(u−v) = ඥ(uଵ− vଵ)ଶ+(uଶ− vଶ)ଶ+⋯+ (u୬− v୬)ଶ Example 1: If u = (1, -3, 5) and v = (3, 1, -4), find the inner product of u and v. Also find norm of u, norm of v, and norm of distance between u and v. Solution: Inner product of u and v = = 1*3 + (-3)*1 + 5*(-4) = 3 – 3 – 20 = -20 Norm of u = ඥ1ଶ+(−3)ଶ+5ଶ = √35 Norm of v = ඥ3ଶ+1ଶ+(−4)ଶ = √26 Norm of distance between u and v = ඥ(1−3)ଶ+(−3−1)ଶ+(5−(−4))ଶ = √4+16+81 = √101 Theorem 1: Cauchy-Schwartz inequality: For any vectors u,v in an inner product space v, ଶ ≤ or || ≤ ||u|| ||v||. Proof: Let y = y(t) = , t∈R = + (by linearity) = + 2 t + tଶ It is a quadratic equation. ⇒ + 2 t + tଶ = 0 It has at most one solution as y(t) ≥ 0. This implies that its discriminant must be less or equal to zero. i.e. [2]ଶ−4 ≤0 ⇒ 4()ଶ≤4 ⇒ ()ଶ≤ or ||≤ห|u|ห ||v|| Hence proved. munotes.in
Page 54
54 Linear algebra using python Note: For non-zero vector u,v ∈ V , the Cauchy-Schwartz inequality implies that −𝟏 ≤ ழ𝐮,𝐯வห|𝐮|หห|𝐯|ห<𝟏 The angle 𝛉 between u and v is defined by 𝐜𝐨𝐬 𝛉 = ழ𝐮,𝐯வห|𝐮|หห|𝐯|ห the angle is unique. 6.2 ORTHOGONALITY: The two vectors u and v are orthogonal, if they are perpendicular to each other. In other words, the two vectors are said to be orthogonal to each other if angle between them is 90°. In terms of inner product, we can define that two vectors are orthogonal if their inner product is equal to zero. Orthogonal sets: A set S = {uଵ,uଶ,…,u୬} of non-zero vectors of V is called an orthogonal set if every pair of vectors are orthogonal to each other. i.e. < u୧,u୨> =0 , 1≤i = 1 for all i ≤n. Theorem 2 : Pythagorean Theorem: Let vଵ,vଶ,…,v୬ be mutually orthogonal vectors. Then, ||vଵ+vଶ+,…+v୬||ଶ= ||vଵ||ଶ+||vଶ||ଶ+⋯+||v୬||ଶ Proof: Let n=2, If u and v are orthogonal, then = 0 ⇒ ||u+v||ଶ = = + + + = + 2 + (by symmetry) = + (u and v are orthogonal) =||u||ଶ+||v||ଶ Similarly we can prove that ||vଵ+vଶ+,…+v୬||ଶ= ||vଵ||ଶ+||vଶ||ଶ+⋯+||v୬||ଶ. Example 1: Determine if u = (3, 2, 0, -5) and v = (-4, 1, 6, -2) are orthogonal. Solution: If = 0, the two vectors u and v are orthogonal. <(3, 2, 0, -5), (-4, 1, 6, -2)> = 3*(-4) + 2*1 + 0*6 + (-5)*(-2) = 0. munotes.in
Page 55
55
Inner Product and
Orthogonality Hence, vectors u and v are orthogonal. Example 2: Verify Pythagorean theorem for u = (1, 0, 2, -4) and v = (0, 3, 4, 2) Solution: Pythagorean theorem for u and v is ||u+v||ଶ= ||u||ଶ+||v||ଶ Consider, L.H.S:||u+v||ଶ = < u + v, u + v> we have u+v = (1, 0, 2, -4) + (0, 3, 4, 2) = (1, 3, 6, -2) ||u+v||ଶ = <(1, 3, 6, -2), (1, 3, 6, -2)> = 1 + 9 + 36 + 4 = 50 consider R.H.S: ||u||ଶ+||v||ଶ = + = <(1,0,2,-4),(1,0,2,-4)> + <(0,3,4,2),(0,3,4,2)> =21+29 =50 ∴L.H.S = R.H.S Hence Proved. Example 3: Find inner product, angle, orthogonality for p = -5+2x-xଶ and q = 2+3xଶ. Solution: Let u = (-5, 2, -1) and v = (2, 0, 3) Inner product of p and q is = -5*2 + 2*0 + (-1)*3 = -10 + 0 - 3= -13 ||u|| = ඥ(−5)ଶ+2ଶ+(−1)ଶ = √30 ||v|| = √2ଶ+0+3ଶ = √13 Angle between p and q is cos θ = ழ𝐮,𝐯வห|𝐮|หห|𝐯|ห = ି𝟏𝟑√𝟑𝟎 √𝟏𝟑 u and v are orthogonal to each other, if = 0 but here we got = -13 It shows that u and v are not orthogonal to each other. Theorem 3: If u and v are orthogonal vectors then for α,β any scalar we have ||α u+ β v||ଶ= αଶ||u||ଶ+βଶ||v||ଶ Proof: ||α u+ β v||ଶ = << α u+ β v ,α u+ β v> = < αu ,α u+ β v>+ <βv ,α u+ β v> (linearity) = < αu,αu>+<αu,β v>+<β v,αu>+<β v,β v> = αଶ+αβ+βα+βଶ = αଶ||u||ଶ+2αβ+βଶ||v||ଶ (symmetricity) = αଶ||u||ଶ+βଶ||v||ଶ (orthogonality) ∴ ||α u+ β v||ଶ= αଶ||u||ଶ+βଶ||v||ଶ Hence proved. munotes.in
Page 56
56 Linear algebra using python Properties of Orthogonality: i. Let u, v are orthogonal vectors, then < αu,αv> = 0, for any scalar α∈R. ii. If u and v are orthogonal to w then u+v is orthogonal to w. Proof: i. Since u and v are orthogonal to each other. ⇒ = 0. Multiplying αଶ both sides, < αu,αv> = 0, for any scalar α∈R. ii. Given that u and v are orthogonal to w, then = 0 and = 0. We have to show that = 0 Consider L.H.S: = + = 0+0 = 0 (by linearity) Parallel and Perpendicular Vectors: Two vectors u and v are parallel to each other if = 1 and If two vectors are perpendicular to each other if = 0 Example 1: Find the vector orthogonal to both u = (-6, 4, 2) and v = (3, 1, 5). Solution: Let x = (xଵ,xଶ,xଷ) is orthogonal to both u and v. x⦁u = (xଵ,xଶ,xଷ)⦁(−6,4,2) = 0 ⇒ -6xଵ+4xଶ+2xଷ = 0----------------(i) similarly x⦁v = (xଵ,xଶ,xଷ)⦁(3,1,5)=0 ⇒ 3xଵ+xଶ+5xଷ = 0-----------------(ii) Multiplying equation(ii) with 2 and then add it in equation (i), we get 6xଶ+12xଷ = 0 ⇒ xଶ= −2xଷ-------(iii) Substituting value of xଶ in equation (ii), we get, xଵ= −xଷ ⇒x = xଵxଶxଷ൩= −xଷ−2xଷxଷ൩ = xଷ−1−21൩ Hence, the vector orthogonal to both u and v is {x: x(-1, -2, 1), x∈R} munotes.in
Page 57
57
Inner Product and
Orthogonality 6.3 PROJECTION Let v be a non-zero vector of a vector space V. Let W be a subspace of V. If w ∈ W is a vector such that it is closest to v, then w is called projection of v. Now decomposing an arbitrary vector x into the form x = αv + z where z ∈Vୄ since z ⊥v then = <αv,v> = α . It implies that α= ழ୴,୶வழ୴,୴வ. The vector proj୴(୶) = ழ୴,୶வழ୴,୴வ v is called the orthogonal projection of x along v. Let u be the subspace spanned by uଵ,uଶ,……u୬ . Then any vector v can be written as the sum of vectors in w and a vector orthogonal to W as proj୳భ,୳మ,……୳୴= v⦁uଵuଵ⦁uଵ uଵା v⦁uଶuଶ⦁uଶ uଶ +⋯+ v⦁u୬u୬⦁u୬ u୬ proj୳భ,୳మ,……୳୴ is called closest point to v in the subspace spanned by uଵ,uଶ,……u୬. The distance between the vectors v and u is c = ழ୴ , ୳భவழ୳భ ,୳భவ . The point in span {u} closest to v is v||୳ =cu. Example 1: Find the projection of v(4, 2, 1) on the vector u(5, -3, 3). Solution: Projection of v along u = ழ୳,୴வழ୳,୳வ Since = 17 and √ = √43 Projection = ଵ√ସଷ. Example 2: Let a = (3, 0), b = (2, 1) find vector in span {a} that is closest to be is b||ୟ and distance ||bୄୟ||. Solution: Distance ||bୄୟ|| = ழୠ,ୟவழୟ,ୟவ = ழ(ଶ,ଵ),(ଷ,)வழଷ,வ,(ଷ,)வ= ଽ= ଶଷ b||ୟ= ழୠ,ୟவழୟ,ୟவ a= ଶଷ*(3,0) = (2,0). 6.4 ORTHOGONAL SET OF GENERATORS Let B = {vଵ,vଶ,…..,v୬ } be a basis of a subspace W of an inner product space V. An orthogonal Basis B’ = {wଵ,wଶ,…..,w୬} may be constructed as follows: wଵ= vଵ, wଵ=span{wଵ} wଶ= vଶ− proj୵భ୴మ , wଶ=span{wଵ,wଶ} ⋮ w୩= v୩− proj୵ౡషభ(୴ౡ) munotes.in
Page 58
58 Linear algebra using python This can be written as wଵ= vଵ wଶ= vଶ− wଵ wଷ= vଷ− wଵ− wଶ ⋮ w୩= v୩− wଵ− wଶ−⋯− w୩ିଵ The method of constructing the orthogonal vector wଵ,wଶ,…..,w୩ is known as the Gram-Schmidt Orthogonalization process. Clearly, the vector wଵ,wଶ,…..,w୩ are linear combinations of vଵ,vଶ,…..,v୩. Conversely, the vectors vଵ,vଶ,…..,v୩ are also linear combination of wଵ,wଶ,…..,w୩. Hence the basis { wଵ,wଶ,…..,w୩} constructed by Gram Schmidt process is an orthogonal basis of W. Example 1: Find the orthonormal basis for subspace Rସ whose generators are vଵ=(1,1,1,1) vଶ=(1,2,4,5), and vଷ = (1,-3,-4,-2) using Gram-Schmidt orthogonalization method. Solution: wଵ= vଵ =(1,1,1,1) wଶ= vଶ− ழ୵భ,୴మவழ୵భ,୵భவ wଵ = (1, 2, 4, 5) - ழ(ଵ,ଵ,ଵ,ଵ),(ଵ,ଶ,ସ,ହ)வழ(ଵ,ଵ,ଵ,ଵ),(ଵ,ଵ,,ଵ,ଵ)வ(1,1,1,1) = (1, 2, 4, 5) - ଵଶସ (1,1,1,1) = (1, 2, 4, 5) - (3, 3, 3, 3) = (-2, -1, 1, 2) wଷ= vଷ− wଵ− wଶ = (1,-3,-4,-2)- ழ(ଵ,ଵ,ଵ,ଵ),(ଵ,ିଷ,ିସ,ିଶ)வழ(ଵ,ଵ,ଵ,ଵ,),(ଵ,ଵ,ଵ,ଵ)வ (1,1,1,1) - ழ(ିଶ,ିଵ,ଵ,ଶ),(ଵ,ିଷ,ିସ,ିଶ)வழ(ିଶ,ିଵ,ଵ,ଶ),(ିଶ,ିଵ,ଵ,ଶ)வ (−2,−1,1,2) = (1,-3,-4,-2)- (-2,-2,-2,-2) + ଵ (−2,−1,1,2) = (ିଵହ,ିଵଵ,ିଵଷଵ,ହ) munotes.in
Page 59
59
Inner Product and
Orthogonality Example 2: Construct an orthonormal basis of Rଶ by Gram-Schmidt process S = {(3,1),(4,2)} Solution: Let the orthonormal basis set is {wଵ, wଶ} wଵ= vଵ= (3,1) wଶ= vଶ− wଵ =(4,2) - ழ(ଷ,ଵ)⦁(ସ,ଶ)வழ(ଷ,ଵ)⦁(ଷ,ଵ)வ ⦁ (3,1) = (4, 2) – ଵସଵ (3,1) =( ିଵହ ,ିଷହ) 6.5 ORTHOGONAL COMPLEMENT Let W⊆ R୬ be a subspace. If a vector v is orthogonal to every vector w ∈W, we say that v is orthogonal to W. The orthogonal Complement of W is the collection of all vectors orthogonal to W. It is denoted by Wୄ. i.e. Wୄ={ v ∈ R୬:v⦁w=0 for all w∈W}. Theorem 4: Let W be a subset of vector space V. Prove that Wୄ is a subspace of R୬. Proof: Wୄ is non-empty, since 0 ∈Wୄ for all w∈Wୄ,<0,w> =0. Let wଵ,wଶ∈Wୄ. =< wଵ,w>+<−wଶ,𝑤 > (linearity) = < wଵ,w>− = 0 – 0 = 0 Hence we can say that wଵ,wଶ∈Wୄ. And by the axiom of subspace we can say that Wୄ is a subspace. Theorem 5: If { wଵ,wଶ,….,w୩} forms a basis of W.then x ∈ Wୄ if and only if x⦁w୧=0 for all integers 1≤i ≤k. Proof: Let x⦁w୧=0. Let w ∈ W, then W can be written as a linear combination of wଵ,wଶ,….w୩ as W = αଵwଵ+αଶwଶ+⋯+α୩w୩. then x⦁W= W = αଵxwଵ+αଶxwଶ+⋯+α୩xw୩ (by linearity) = 0 + 0 +….+ 0 = 0 x ∈Wୄ. munotes.in
Page 60
60 Linear algebra using python Let x ∈Wୄ. Then by definition of orthogonality x⦁w୧=0 , ∀ w୧ ∈W. Hence proved. Theorem 6: Wୄ is the Orthogonal Complement of W where W is a subspace of V . Then V = W⨁ Wୄ and W ∩ Wୄ={0}. Proof: We have W⊆V and also Wୄ⊆ V then W⨁ Wୄ ⊆V----(i). Now for any b ∈V,b=b"s + bୄS, where b” ∈W and bୄ∈Wୄ. ∴b∈ W⨁ Wୄ ⇒ V⊆ W⨁ Wୄ-------(ii) From equation (i) and equation (ii), we get V = W⨁ Wୄ. Now, Wୄ = { v∈V: = 0,∀ w∈W}. Since W⊆V ⇒ = 0 ⇒w = 0. ∴W∩ Wୄ={0}. Hence Proved. Example 1: Find the orthogonal Complement of W = span{wଵ,wଶ}, where wଵ = (3, 0, 1, 1) and wଶ = (0, 2, 5, 1). Let x = (xଵ,xଶ,xଷ,xସ) ∈Rସ such that x⦁wଵ=x⦁wଶ= 0 ⇒ (xଵ,xଶ,xଷ,xସ) ⦁ (3, 0, 1, 1) = 0 and (xଵ,xଶ,xଷ,xସ)⦁(0, 2, 5, 1) = 0 ⇒ 3xଵ+0xଶ+xଷ+xସ=0 and 0xଵ+2xଶ+5xଷ+xସ=0. We can write (xଵ,xଶ,xଷ,xସ) in the following manner: xଵ= −xଷ−xସ xଶ= −5xଷ−xସ xଷ= 1xଷ+0xସ xସ= 0xଷ+1xସ ⇒൦xଵxଶxଷxସ൪=xଷ൦−1−510൪ + xସ൦−1−101൪ ⇒ The orthogonal complement of W is {xଷ(-1, -5, 1, 0) + xସ(-1, -1, 0, 1): xଷ, xସ ∈ R}. munotes.in
Page 61
61
Inner Product and
Orthogonality 6.6 SUMMARY The standard inner product of a vector v with itself gives the Euclidian length and the standard inner product of two vectors gives the angle between them. The orthogonal projection of vector w onto vector v can be assumed as shadow of w on the line spanned by v if the direction of the sun’s rays were exactly perpendicular to the line. 6.7 REFERENCE 1. Linear Algebra and Probability for Computer Science Applications, Ernest Davis, A K Peters/CRC Press (2012). 2. Linear Algebra and Its Applications, Gilbert Strang, Cengage Learning, 4th Edition (2007). EXERCISE Q1. Find the inner product of u and v, also show that <3u-2v, w> = 3 -2 . i. u=(1, -1, 2, 3) , v = (1, 0, 3, 7) and w = (2, 5, 1, 9) ii. u = (7, 3, -9, 1), v = (2, 5, 3, 0) and w = (-1, 3, 5, 7) iii. u = (1, 2, 3, 4), v = (2, 3, 4, 5) and w = (4, 5, 6, 7) iv. u = (1, 9, 11, 0), v = (3, -1, 5, 7) and w = (11, 11, 5, 0) Q2. Find the projection of vector u along vector v where u and v are, i. u = (1, 1) and v = (1, 0) ii. u = (0, 1) and v = (√ଶଶ ,√ଶଶ) iii. u = (-1, 3) and v = (3, 4) iv. u = (-11, 10) and v = ( 6, 8) Q3. Find the orthonormal basis for subspace of 𝑅ସ generated by the following: i. (1, 2, 1, 0) and (1, 2, 3, 1) (1, 1, 0, 0), (1, -1, 1, 1) and (-1, 0, 2, 1) munotes.in
Page 62
62 Linear algebra using python 7 EIGEN VECTORS Unit Structure: 7.0 Objectives 7.1 Modelling Discrete Dynamic Processes 7.2 Eigen Values and Eigen Vectors 7.3 Diagonalization 7.3.1 Similar Matrix 7.3.2 Calculation of powers of a matrix 7.3.3 Diagonalization of the Fibonacci Matrix 7.4 Coordinate representation in terms of Eigen vectors 7.5 The Internet Worm 7.6 Existence of Eigen Values 7.7 Markov Chains 7.7.1 Transition Matrix 7.7.2 Graphical Representation 7.7.3 Regular Transition Matrices 7.7.4 Steady State 7.8 Modelling a web surfer: PageRank 7.8.1 Page Rank algorithm as a Markov Process: 7.8.2 Basic Page Rank Algorithm Model: 7.8.3 Random web surfer Model: 7.8.4 Google matrix 7.9 Summary 7.10 References 7.0 OBJECTIVES After going to this chapter, you will be able to: • Define discrete dynamic process • Find eigenvalues and eigenvectors of a square matrix • Understand Diagonalization of a matrix and its importance • Explain Markov process, Markov Chain and Steady state • Define Internet worm and Page rank munotes.in
Page 63
63
Eigen Vectors 7.1 MODELLING DISCRETE DYNAMIC PROCESSES A matrix equation is called a discrete dynamical system if it is in the form 𝑥ାଵሬሬሬሬሬሬሬሬሬ⃗=𝐴 ⦁ 𝑥ሬሬሬሬ⃗ or equivalently, it is 𝑥ାଵሬሬሬሬሬሬሬሬሬ⃗=𝐴ାଵ ⦁ 𝑥ሬሬሬሬ⃗ where A is an mxm matrix and for each integer n, 𝑥ሬሬሬሬ⃗ is an m-demensional vector. In order to better understand the behaviour of discrete dynamical systems, we need a method of easily computing the product of matrices and vectors. Let A = ቂ4−310 ቃ ,vଵ= ቂ11ቃ ,vଶ= ቂ31ቃ (a) we are finding A(vଵ) and A(vଶ). A(vଵ)= ቂ4−310 ቃ ቂ11ቃ = ቂ11ቃ = vଵ A(vଶ)= ቂ4−310 ቃ ቂ31ቃ= ቂ93ቃ=3ቂ31ቃ=3vଶ (b) we are finding Aଶvଵ and Aଶvଶ. Aଶvଵ = ቂ4−310 ቃଶቂ31ቃ = ቂ4−310 ቃቂ4−310 ቃቂ31ቃ = ቂ4−310 ቃ 3 ቂ31ቃ = 3 ቂ4−310 ቃቂ31ቃ = 3 (3 ቂ31ቃ)) = 3ଶvଶ Similarly we can find A୬vଵ and A୬vଶ. Based on the above procedure we can conclude that A୬vଵ= vଵand A୬vଶ= 3୬vଶ. (c) Use the fact that ቂ71ቃ = −2vଵ+ 3vଶ to find a formula for A୬ቂ71ቃ. We have ቂ71ቃ = −2vଵ+ 3vଶ Multiplying both sides with A୬, we get, A୬(ቂ71ቃ) = A୬(−2vଵ+ 3vଶ) munotes.in
Page 64
64 Linear algebra using python A୬(ቂ71ቃ) = A୬(−2vଵ) + A୬ (3vଶ) A୬(ቂ71ቃ) = −2A୬(vଵ) + 3A୬ (vଶ) A୬(ቂ71ቃ) = -2 vଵ + 3(3୬vଶ) A୬(ቂ71ቃ) = -2 ቂ11ቃ + 3x 3୬ቂ31ቃ A୬(ቂ71ቃ) = ቂ−2−2ቃ + ቂ3x3୬ାଵ3x3୬ቃ A୬(ቂ71ቃ)= −2+3x3୬ାଵ−2+3x3୬൨ A୬(ቂ71ቃ)= −2+3୬ାଶ−2+3୬ାଵ൨ ----------(I) It is a formula that allows us to directly compute a value by simply putting a value of n and directly getting an output. If we want value of Aଵ(ቂ71ቃ), we can simply take n=100 in the above eqn(I) instead of multiplying A by 100 times. It allows us to compute a very large matrix multiplication very quickly and efficiently. 7.2 EIGEN VALUES AND EIGEN VECTORS Characteristic Equation: Let A be a Square matrix, I be the unit matrix of same order that of A, and 𝜆 is a number. Then the polynomial equation det(A-𝜆I) = 0 in the variable 𝜆 for the given square matrix A is called the characteristic equation of the matrix A. Eigen Values: The roots of the characteristic equation det(A-𝜆I) = 0 is called characteristics roots or eigenvalues or latent roots of the matrix A. Eigen Vectors: An eigen vector of A is a non-zero vector v such that Av=𝜆v , for some scalar 𝜆. Where 𝜆 is an eigen value of A. To find the eigenvectors of A corresponding to each eigenvalue 𝜆, we must solve the matrix equation (A-𝜆I)v = 0, for each eigen value 𝜆. Example 1: Find the characteristic equation and hence eigenvalues for A= ቂ1−3−45ቃ. Solution: Given A= ቂ1−3−45ቃ. Consider the characteristic equation as | A-λI|=0 munotes.in
Page 65
65
Eigen Vectors ⇒ቂ1−3−45ቃ−λቂ1001ቃ=0 ⇒ቂ1−λ−3−45−λቃ=0 ⇒λଶ- 6 λ -7 = 0 ⇒(λ-7)( λ+1) = 0 Hence λ=−1,7 are the eigen values for the given matrix. Example 2: Find the characteristic equation and hence eigenvalues for A= ቂ1243ቃ. Solution: Given A= ቂ1243ቃ. Consider the characteristic equation as | A-λI| = 0, ⇒ቂ1243ቃ−λቂ1001ቃ=0 ⇒ቂ1−λ243−λቃ=0 ⇒λଶ-4λ-5 = 0 ⇒(λ-5)( λ+1)=0 Hence λ=−1,5 are the eigen values for the given matrix A. Example 3: Find eigenvalues of matrix A= 113151311൩. Solution: Given A= 113151311൩. Consider the characteristic equation of A is | A-λI| = 0. ⇒1−λ1315−λ1311−λ൩=0 ⇒λଷ-7λଶ+36 = 0 ⇒(λ-6)( λ-3) ( λ+2) = 0 ⇒λ = -2, 3, and 6 are the eigen values for the given matrix A. Example 4. Find eigenvalues and given vectors of A=8−8−24−3−23−41൩. munotes.in
Page 66
66 Linear algebra using python Solution: Here, A = 8−8−24−3−23−41൩ The characteristic equations is |A-λI| = 0. ⇒ |8−8−24−3−23−41൩ - λ|8−8−24−3−23−41൩|=0 ⇒ 8−λ−8−24−3−λ−23−41−λ൩ = 0 ⇒λଷ - 6λଶ + 11 λ - 6 = 0 ⇒(λ-1)( λ-2) ( λ-3) = 0 ⇒λ=1,2,3. Case 1: Eigen vector corresponding to eigenvalue λ = 1; Consider (A-1I) v = O; ⇒7−8−24−4−23−40൩vଵvଶvଷ൩=000൩ ⇒ 7vଵ -8vଶ-2vଷ =0 ⇒ 4vଵ -4vଶ-2vଷ =0 ⇒ 3vଵ -4vଶ =0 ⇒ 3vଵ = 4vଶ ⇒ vଵ = 4/3vଶ Substituting this value of vଵ in 7vଵ -8vଶ-2vଷ = 0 ⇒ଶ଼ଷ vଶ -8vଶ-2vଷ = 0 ⇒vଷ= ଶଷ vଶ Thus vଵvଶvଷ൩ =൦43ൗvଶvଶ23ൗvଶ൪ = ଵ୴మଷ 432൩ This implies that Xଵ=432൩. Case 2: Eigen vector corresponding to eigenvalue λ = 2; Consider (A-2I)v = O ; munotes.in
Page 67
67
Eigen Vectors ⇒6−8−24−5−23−44൩vଵvଶvଷ൩=000൩ Performing row operations Rଷ→2Rଷ-Rଵ and Rଶ→Rଶ-Rଵ; ⇒ 6−8−2−230000൩vଵvଶvଷ൩=000൩ ⇒6vଵ -8vଶ-2vଷ =0 ⇒ -2vଵ +3vଶ=0 ⇒vଵ= ଷଶ vଶ Substituting the value of vଵin 6vଵ -8vଶ-2vଷ = 0, ⇒-vଷ= ୴మଶ Thus vଵvଶvଷ൩ = ൦ଷଶvଶvଶଵଶvଶ൪= ଵଶvଶ 321൩ This implies that Xଶ= 321൩. Case 3: Eigen vector corresponding to λ = 3: Consider (A-3I) = O, By simplification, we get 5−8−24−6−23−4−2൩vଵvଶvଷ൩=000൩ ⇒Performing Rଶ⟶5Rଶ−4Rଵ,and Rଷ⟶5Rଷ−3Rଵ ⇒5−8−202−204−4൩vଵvଶvଷ൩=000൩ Performing Rଷ⟶Rଷ−2Rଶ, we get ⇒5−8−202−2000൩vଵvଶvଷ൩=000൩ ⇒5vଵ−8vଶ−2vଷ = 0−−−−−−−−−−(i) ⇒ 2vଶ−2vଷ=0 ⇒vଶ=vଷ substituting in (i), we get ⇒vଵ=2vଷ munotes.in
Page 68
68 Linear algebra using python ⇒vଵvଶvଷ൩ = 22vଷvଷvଷ൩=vଷ211൩ Hence, Xଷ = 211൩. Thus the eigenvalues are 1, 2, and 3. Their corresponding eigen vectors are 432൩ ,321൩and 211൩ respectively. Example 5: Find eigen values and Eigen vectors of matrix A= 2−2311113−1൩. Solution: Given A= 2−2311113−1൩ Consider the characteristic equation of A is | A-λI| = 0. ⇒2−λ−2311−λ113−1−λ൩ = 0 ⇒(λ-1)( λ-3) ( λ+2) = 0 ⇒λ=1,3,-2. Case 1: Eigen vector corresponding to eigenvalue λ = 1; Consider (A-1I)v = O, ⇒2−1−2311−1113−1−1൩vଵvଶvଷ൩=000൩ ⇒1−2310113−2൩vଵvଶvଷ൩=000൩ Performing Rଶ⟶Rଶ−Rଵ,and Rଷ⟶Rଷ−Rଵ; ⇒12102−205−5൩vଵvଶvଷ൩=000൩ Performing Rଶ⟶Rଶ/2 and Rଷ⟶Rଷ/5; munotes.in
Page 69
69
Eigen Vectors ⇒12101−101−1൩vଵvଶvଷ൩=000൩ Performing Rଷ⟶Rଷ−Rଶ; ⇒12101−1000൩vଵvଶvଷ൩=000൩ ⇒vଵ+2vଶ+vଷ = 0−−−−−−−−−−(i) ⇒ vଶ−vଷ=0 ⇒vଶ=vଷ Substituting the value of vଶ in (i), we get ⇒vଵ=−3vଷ ⇒vଵvଶvଷ൩ = −3vଷvଷvଷ൩ = vଷ−311൩ Hence Xଵ = −311൩. Case 2: Eigen vector corresponding to eigen value λ = 3 Consider (A-3I)v = O; ⇒2−3−2311−3113−1−3൩vଵvଶvଷ൩=000൩ ⇒−1−231−2113−4൩vଵvଶvଷ൩=000൩ Performing Rଶ⟶Rଶ−Rଵ,and Rଷ⟶Rଷ+Rଵ, ⇒−1−2300−201−1൩vଵvଶvଷ൩=000൩ Performing Rଶ⟷Rଶ, ⇒−1−2301−100−2൩vଵvଶvଷ൩=000൩ ⇒−vଵ−2vଶ+3vଷ = 0−−−−−−−−−−(i) ⇒ vଶ−vଷ=0 vଶ=vଷ Substituting value of in vଶ equation (i), −vଵ= −vଷ munotes.in
Page 70
70 Linear algebra using python ⇒vଵ= vଷ ⇒vଵvଶvଷ൩ = vଷvଷvଷ൩=vଷ111൩ Hence Xଶ = 111൩. Case 2: Eigen vector corresponding to eigenvalue λ = -2; Consider (A+2I)v = O; ⇒2+2−2311+2113−1+2൩vଵvଶvଷ൩=000൩ ⇒4−23131131൩vଵvଶvଷ൩=000൩ Performing Rଶ⟶4Rଶ−Rଵ,and Rଷ⟶4Rଷ− Rଵ; ⇒4−230141000൩vଵvଶvଷ൩=000൩ ⇒4vଵ−2vଶ+3vଷ = 0−−−−−−−−−−(i) ⇒14vଶ+vଷ = 0−−−−−−−−−−(ii) ⇒−14vଶ= vଷ substituting in equation (i), we get ⇒4vଵ−2vଶ+3(−14vଶ) = 0 ⇒4vଵ−44vଶ=0 ⇒4vଵ=44vଶ ⇒vଵ=11vଶ ⇒vଵvଶvଷ൩ = 11vଶvଶ−14vଶ൩=vଶ111−14൩ Hence Xଷ = 111−14൩. Thus the eigenvalues are 1,3, and -2 and their corresponding eigenvectors are −311൩ ,111൩and 111−14൩ respectively. munotes.in
Page 71
71
Eigen Vectors Example 6: Find Eigen values and Eigen vectors of 3−11−13−11−13൩. Solution: Given A = 3−11−13−11−13൩ The characteristic equation of the square matrix A is | A-λI| = 0. i.e. 3−11−13−11−13൩- λ 100010001൩ = 0 ⇒อ3−λ−11−13−λ−11−13−λอ = 0 ⇒ (3 - λ)ቚ3−λ−1−13−λቚ − (−1)ቚ−1−113−λቚ+1ቚ−13−λ1−1ቚ = 0 ⇒ (3- λ)((3- λ)(3- λ) -1) + (-(3- λ) + 1) + 1(1- (3- λ))=0 ⇒ (λ-2) ( λ-5) ( λ-2)=0 ⇒λ = 2, 2, 5 are eigenvalues of A. Case 1: Eigen vector corresponding to eigenvalue λ = 5; Consider (A-5I)v = O ⇒{3−11−13−11−13൩- 5 100010001൩}vଵvଶvଷ൩= O ⇒−2−11−1−2−11−1−2൩vଵvଶvଷ൩=000൩ ⇒Performing row operations Rଵ↔Rଷ, we get ⇒1−1−2−1−2−1−2−11൩vଵvଶvଷ൩=000൩ ⇒Performing Rଶ⟶Rଶ+Rଵ and Rଷ⟶Rଷ+2Rଵ ⇒1−1−20−3−30−3−3൩vଵvଶvଷ൩=000൩ ⇒Performing Rଷ⟶Rଷ−Rଶ ⇒1−1−20−3−3000൩vଵvଶvଷ൩=000൩ munotes.in
Page 72
72 Linear algebra using python ⇒Performing Rଶ⟶ିଵଷRଶ ⇒ 1−1−2011000൩vଵvଶvଷ൩=000൩ ⇒Vଵ - Vଶ - 2Vଷ = 0 And Vଶ+Vଷ =0 ⇒Vଶ= -Vଷ Substituting this value in Vଵ - Vଶ - 2Vଷ = 0 Vଵ -Vଷ= 0 ⇒ Vଵ =Vଷ ⇒vଵvଶvଷ൩=vଷ−vଷvଷ൩ = vଷ1−11൩ Hence, the eigenvector Xଵ=1−11൩ is corresponding eigenvector to eigenvalue λ=5. Case 2: Eigen vector corresponding to eigen value λ = 2 Consider (A-2I)v = O ⇒{3−11−13−11−13൩- 2 100010001൩}vଵvଶvଷ൩= O ⇒ 1−11−11−11−11൩vଵvଶvଷ൩=000൩ ⇒ Vଵ -Vଶ+Vଷ =0 ⇒ -Vଵ +Vଶ-Vଷ =0 ⇒ Vଵ -Vଶ+Vଷ =0 We get, Vଶ = Vଵ + Vଷ Now, vଵvଶvଷ൩ = 1vଵ+ 0vଷ 1vଵ+1vଷ0vଵ+1vଷ൩ = vଵ110൩ + vଷ011൩ Thus , the eigenvectors are Xଶ =110൩ and Xଷ011൩ . munotes.in
Page 73
73
Eigen Vectors Hence eigenvalues are 5, 2, 2 and corresponding eigenvectors are Xଵ =1−11൩ , Xଶ =110൩ , Xଷ =011൩ respectively. Properties of Eigen values: i. The sum of the eigenvalues of a matrix is sum of the elements of principal diagonal. It is called trace of the matrix A. Let A = aଵଵaଵଶaଵଷaଶଵaଶଶaଶଷaଷଵaଷଶaଷଷ൩ If λଵ,λଶ and λଷ are eigen values of A, then trace(A) = λଵ+λଶ + λଷ=aଵଵ+aଶଶ+aଷଷ ii. The product of the eigenvalues of a matrix A is equal to its determinant. iii. If λ is an eigen value of A then ଵ is eigen value of Aିଵ. iv. If λଵ,λଶ ...λ୬ are the eigen values of matrix A then λଵ୫,λଶ୫,…….λ୬୫ are eigen values of A୫. v. If A is upper-triangular matrix of order nxn, then its eigenvalues are its diagonal elements. vi. Eigen values of real symmetric matrix are real. 7.3 DIAGONALIZATION If a square matrix A of order n has n linearly independent eigenvectors or n distinct eigenvalues, then there exists a matrix P of same order such that 𝑃ିଵAP is a diagonal matrix. i.e. a square matrix A of order n is diagonalizable, iff it has n linearly independent eigen vectors. Let λଵ, λଶ,…., λ୬ are the distinct eigenvalues of a matrix A of order n and the corresponding eigen vectors are Xଵ, Xଶ,…., X୬. Then a square matrix P can be formed with these eigen vectors as P = [Xଵ Xଶ…. X୬]. Now AP = A[Xଵ Xଶ…. X୬] = [λଵXଵ λଶXଶ…. λ୬X୬] For n = 3, AP = A[Xଵ Xଶ Xଷ] = [AXଵ AXଶ AXଷ] = [λଵXଵ λଶXଶ λଷXଷ] = λଵxଵ λଶxଶ λଷxଷλଵyଵ λଶyଶ λଷyଷλଵzଵ λଶzଶ λଷzଷ൩ munotes.in
Page 74
74 Linear algebra using python = xଵ xଶ xଷyଵ yଶ yଷzଵ zଶ zଷ൩*λଵ000λଶ000λଷ൩ = PD, where D is the diagonal matrix. So PିଵAP = PିଵPD = D. The matrix P which diagonalizes A is called the transforming matrix or modal matrix of A. The resulting diagonal matrix D is known as spectral matrix of A. D has the eigenvalues of A as its elements. 7.3.1 Similar Matrix: A square matrix B of order n is called similar to a square matrix A of same order if B = PିଵAP for some non-singular matrix P of order n. Since matrix B is similar to matrix A, B has same eigenvalues as A. If X is an eigenvector of A, then y = 𝑃ିଵX is an eigen vector of B corresponding to same eigen values. 7.3.2 Calculation of powers of a matrix: Let matrix P diagonalizes matrix A, i.e. D = PିଵAP Then Dଶ = (PିଵAP)( PିଵAP) = PିଵAPPିଵAP = PିଵAଶP [since PPିଵ = I] Again Dଷ = ( PିଵAଶP) ( PିଵAP) = PିଵAଶP PିଵAP = PିଵAଷP Similarly, D୬ = PିଵA୬P ; pre-multiplying by P and post-multiplying by Pିଵ, we get PD୬Pିଵ = PPିଵA୬PPିଵ = A୬ . 7.3.3 Diagonalization of the Fibonacci Matrix Fibonacci considered the following problem (breeding rabbits): We breed rabbits, starting with one pair of rabbits. Each pair of rabbits produces one pair of offspring in every month. After one month, the offspring is adult and ready for reproduction. After neglecting all kinds of effects (as death) and always considering pairs of rabbits, we get the number of rabbits increase quite rapidly. Let rabbit vector r⃗ = ቀjaቁ ∈ Rଶ , where j and a denote the number of juvenile pairs and number of adult pairs respectively. Since, j୬ାଵ = a୬ a୬ାଵ = j୬ + a୬ munotes.in
Page 75
75
Eigen Vectors In vector notation, ൬j୬ାଵa୬ାଵ൰ = ቀ0111ቁ൬j୬a୬൰ Or, r⃗୬ାଵ= ቀ0111ቁ r⃗୬ The transition matrix of this dynamical system is A = ቀ0111ቁ The initial condition is r⃗ = ቀ10ቁ, that means there is one pair of juvenile rabbits, no adult rabbits. That means the dynamical system in the equations can be summarized as r⃗୬ାଵ= ቀ0111ቁ r⃗୬ , r⃗ = ቀ10ቁ The solution of the above equation will be in the form of r⃗୬ = A୬r⃗ Or, ൬j୬a୬൰ = ቀ0111ቁ୬ ቀ10ቁ Analysis of the problem: Now we calculate first few rabbit vectors : N 0 1 2 3 4 5 6 7 8 j୬ 1 0 1 1 2 3 5 8 13 a୬ 0 1 1 2 3 5 8 13 21 The table shows that after 5 months, there are 3 juvenile pairs and 5 adult pairs of rabbits. The sequence a୬ = (0, 1, 1, 2, 3, 5, 8, …) is the famous Fibonacci sequence. For finding the eigenvalue, rewrite the vector equation as follows: ቀ0111ቁ ቀjaቁ = λ ቀjaቁ ቀ0111ቁ ቀjaቁ = λ ቀ0111ቁ ቀjaቁ ቀ0111ቁ ቀjaቁ = ቀλ00λቁ ቀjaቁ ቀλ−1−1λ−1ቁ ቀjaቁ = ቀ00ቁ The rabbit vector ቀjaቁ has to be non-zero, so for the solution of the above matrix equation the coefficient matrix must be zero. The matrix is singular if detቀλ−1−1λ−1ቁ = 0. detቀλ−1−1λ−1ቁ = λ(λ−1)-1 = 0 munotes.in
Page 76
76 Linear algebra using python λ(λ−1)-1 = 0 is called characteristic equation of the matrix A = ቀ0111ቁ and its root is known as eigen values of A. Solving the characteristic equation, we get the two eigen values are λଵ = ଵା√ହଶ and λଶ = ଵି√ହଶ. Eigen vector corresponding to eigenvalue λଵ = ଵା√ହଶ : ቌଵା√ହଶ−1−1ଵା√ହଶ−1ቍ ቀjaቁ = ቀ00ቁ After row reducing the coefficient matrix, we get ቌଵା√ହଶ−1−1ଵା√ହଶ−1ቍ→ ቆ1ଵି√ହଶ00ቇ For the non-trivial solution of the above equation is ቀjaቁ = ቆ൫√ହିଵ൯ୟଶaቇ Thus the eigen vector is vሬ⃗ଵ = ൬√5−12൰ corresponding to eigen value eigen value λଵ = ଵା√ହଶ. Now we calculate eigen vector corresponding to eigen vector λଶ = ଵି√ହଶ : Putting the value of λଶ in ቀλ−1−1λ−1ቁ , we get ቌଵି√ହଶ−1−1ଵି√ହଶ−1ቍ ቀjaቁ = ቀ00ቁ After row reducing the coefficient matrix, we get ቌଵି√ହଶ−1−1ଵି√ହଶ−1ቍ → ቆ1ଵା√ହଶ00ቇ For the non-trivial solution of the above equation is ቀjaቁ =ቆି(ଵା√ହ)ୟ ଶaቇ. Thus the eigenvector is vሬ⃗ଶ = ൬1+√5−2൰ corresponding to eigen value eigen value λଶ = ଵି√ହଶ. munotes.in
Page 77
77
Eigen Vectors Example 1: Find a matrix P which transforms the matrix A = 113151311൩ to diagonal form. Hence calculate 𝐴ସ . Solution: The characteristic equation is | A – λI | = 0 อ1−𝜆1315−𝜆1311−𝜆อ = 0 𝜆ଷ - 7𝜆ଶ + 36 = 0 (λ+2) (λ-3) (λ-6) = 0 Eigen values of A are λ = -2, 3 and 6. Now eigen vector corresponding to λ = -2 can be found by solving 1+21315+21311+2൩ ቈ𝑥𝑦𝑧 = 0 i.e. 3 x + y + 3z = 0, x + 7y + z = 0 , 3x + y + 3z = 0. We get ቈ𝑥𝑦𝑧 = k −101൩. Similarly, eigenvectors corresponding to λ = 3 and λ = 6 are arbitrary non-zero multiples of the vectors [1, -1, 1] and [1, 2, 1]. Hence the transforming matrix P = −1110−12111൩. Now find 𝑃ିଵ using adjoint method : 𝐴ଵଵ = -3 , 𝐴ଵଶ = 2 , 𝐴ଵଷ = 1, 𝐴ଶଵ = 0 , 𝐴ଶଶ = -2 , 𝐴ଶଷ = 2, 𝐴ଷଵ = 3, 𝐴ଷଶ = 2, 𝐴ଷଷ =1 and |P| = 6. Hence 𝑃ିଵ = 1/6 −3032−22121൩. Thus, D = 𝑃ିଵAP = −200030006൩ Now 𝐴ସ = −1110−12111൩ 16000810001296൩1/6 −3032−22121൩ = 2514852354851051485235485251൩ munotes.in
Page 78
78 Linear algebra using python 7.4 COORDINATE REPRESENTATION IN TERMS OF EIGEN VECTORS Let 𝜆ଵ, 𝜆ଶ,…., 𝜆 are the eigen values of a matrix A of order n and the corresponding eigen vectors are 𝑋ଵ, 𝑋ଶ,…., 𝑋 which are columns of P. Let u(୲) be the coordinate representation of x(୲) in terms of eigenvectors. The equation x(୲) = A୲. x() gives rise to ൣu(୲)൧ = λଵ୲λଶ୲λଷ୲ൣu()൧ As the power increases and if |𝜆| > |𝜆| for all j, then λ୧୲ will dominate. 7.5 THE INTERNET WORM An Internet worm is a program that exploits flaws in utility programs in systems. The flaws allow the program to break into those machines and copy itself, thus infecting those systems. It spread itself without human intervention by using a scanning strategy to find vulnerable hosts to infect. Some of the famous examples of code red, SQL Stammer, and Blalter. It performs self-replication by sending copies of their codes in network packets and ensuring the codes are executed by the computers that receive them. Meanwhile, when computers on network become a victim of its infection, it spreads further copies of the worm by exploiting low level software defects. The following are the activities of worms: i. Infection: By injecting new code and new control flow edges into the program. Worms gain control of the execution of a remote program. ii. Spreading: Worms typically replicate itself to infect other computers. iii. Hiding: Worms use the following techniques to avoid being detected on internet. Traffic shopping, Polymorphism, and finger printing. In order to defend against future worms, it is important to understand how worms propagate and how different scanning strategies affect worm propagation dynamies. An efficient and reliable vigilante system for worm containment was developed using Markov chain. Markov chain is a mathematical system that describes transitions from one state to another, between a finite or countable number of possible states. The Markov chain model is developed for uniform scanning worms, specifically for scanning worms, we are able to provide condition that determines whether the worm spread would eventually stop and obtain the distribution of the total number of infected hosts. munotes.in
Page 79
79
Eigen Vectors Modelling the Worm: Worm population represented by a vector X = [xଵ,yଵ,xଶ,yଶ,xଷ,yଷ,] for i=1,2,3 is the expected number of mortal worms at computer x୧and y୧ is the expected number of immortal worms at computer i. For t = 0, 1, 2, …. Let x(୲)={xଵ(୲),xଶ(୲),yଵ(୲),yଶ(୲),xଷ(୲),yଷ(୲)}, any mortal worm on computer 1 is a child of computer 2 or 3. Therefore, the expected number of mortal worms at computer 1 after t+1 iterations is xଵ(୲ାଵ)=110xଶ(୲)+110yଶ(୲)+110xଷ(୲)+110yଷ(୲) With probability ଵ , a mortal worm at computer 1 becomes immortal. The previously immortal worms stay immortal. Therefore, yଵ(୲ାଵ)=ଵxଵ(୲)+yଵ(୲) Then we get a matrix A such that A= ⎣⎢⎢⎢⎢⎢⎢⎢⎢⎡00ଵଵଵଵଵଵଵଵଵ10000ଵଵଵଵ00ଵଵଵଵ00ଵ100ଵଵଵଵଵଵଵଵ000000ଵ1⎦⎥⎥⎥⎥⎥⎥⎥⎥⎤ The matrix has linearly independent vectors and its largest eigenvalues is about 1034. 7.6 EXISTENCE OF EIGEN VALUES If A is an n*n matrix with entries in C, Then det(A - λ I) is a polynomial of degree n in λ with coefficients in C. By the corollary of fundamental theorem of algebra, it has n roots. This gives the existence of eigenvalues. Let V ≠ {0} be a finite dimensional vector space over C, and let T ∈ L(V, V). Then, T has at least one eigenvalue. 7.7 MARKOV CHAINS Stochastic Process: Stochastic process is a process that involves a variable changing at a random rate through time. There are various types of stochastic process such as random walks, Markov chains and Bernoulli processes. munotes.in
Page 80
80 Linear algebra using python Probability vectors: A row vector v = (vଵ,vଶ,....,v୬) is called a probability vector if vଵ,vଶ,....,v୬are non-negative and their sum is equal to 1. Example: v = (ଵସ ,ଵସ,ଵସ,ଵସ,0) Markov Property: A Markov property or memoryless property, when the future and past states are given, the future states of the process depend only on present state and not at all the past states. Markov Process: A random process with the Markov property is called Markov process. Markov Chain: A Markov chain is a Markov process with discrete time and discrete state space. Markov chain is a mathematical model that describes transitions from one state to another according to certain probabilistic rules. It is a stochastic process in which possible future states are fixed. In other words, the probability of transitioning to any particular state is dependent only on the current state and time elapsed. Markov chain is denoted by X = (X୬)୬∈= (X,Xଵ,Xଶ,.......) 7.7.1 Transition Matrix: A Markov chain {X} at time t can be represented as a matrix. This matrix contains information on the probability of transitioning between states, so the matrix is known as transition matrix. It is denoted by p୲. The (i,j)୲୦ element of the matrix p୲ is given by (p୲)୧,୨=p(x୲ାଵ = j/x୲=i) This means each row of the matrix is a probability vector and the sum of its entries is 1. Transition matrices have the property that the product of subsequent ones describes a transition along the time interval spanned by the transition matrices. Let us assume that we have a finite number N of possible states in E such that E = {eଵ,eଶ,....,e}. The initial probability distribution can be described as a row vector q of size N such that (q)୧= q(e୧)=P(X=e୧) P୧୨=P(e୧,e୨)=P(x୬ାଵ=e୨/x୬=e୧) (q୬)୧=q୬(e୧)=P(x୬=e୧) q୬ାଵ=q୬P,q୬ାଶ=q୬ାଵP=(q୬P)P=q୬Pଶ q୬ା୫=q୬Pଶ That means the probability vector after n repetitions of the experiment is qP୬. munotes.in
Page 81
81
Eigen Vectors The row vector describing probability describing at time step n+1 Row vector describing probability distribution at times of X transitions. Properties of transition Matrix: 1. It is square, since all possible states must be used behaviors and as columns. 2. All entries are between 0 and 1, because all entries represent probability. 3. The sum of the entries in any row must be 1, since the numbers in the row give the probability of changing from the state at the left to one of states indicated across the top. 7.7.2 Graphical Representation: The finite state space Markov chain can be represented as a directed graph such that each node in the graph is a state. For all pairs of state (e୧,e୨) there exists an edge if P(e୧,e୨) > 0 and the value of the edge is same probability P(e୧,e୨). Example 1: Consider the daily behavior of student of SYCS towards visit of college library for each day, there are 3 possible states: The student does not visit the library this day (N), the student visits library but does not issue any book (V) and the student visits library and takes at least one book (R) so, we have the following state space E = {N, V, R}. Assume that at the first day this student has 70% chance to only visit library and 30% chance to visit library and to take at least one book for some the vector describing the initial probability distribution (n=0) is that q=(0.0,0.7,0.3). Now assume that the following probabilities have been observed: i. When the student does not visit library a day, he has 25% chance of visiting the next day, 50% chance to only visit and 25% chance to visit and to issue at least one book. ii. When the student visits library without issuing any book a day. He has 60% chance to visit again without issuing the next day and 40% to visit and issue. iii. When the student visits and issues a book on a day, he has 35% chance of not visiting the next day, 40% chance to only visit and 25% to visit and issue a book again. Thus we have the transition matrix P = 𝑁𝑉𝑅̇ ⎣⎢⎢⎢⎡0.250.50.250.000.600.400.350.400.15ᇩᇭᇭᇭᇭᇭᇪᇭᇭᇭᇭᇭᇫ ேோ⎦⎥⎥⎥⎤ munotes.in
Page 82
82 Linear algebra using python The probability of each state for the second day (n=1) 𝑞ଵ=𝑞𝑃 =(0.0,0.7,0.3)0.250.50.250.000.600.400.350.400.15൩ Finally, the probabilistic dynamic of this Markov chain can be graphically represented as follows:
7.7.3 Regular transition Matrices: Markov chain is used to find long range predictions. It is not possible to make long range predictions with all transition matrices, but for a large set of transition matrices, predictions are possible with regular transition matrices. A transition matrix is regular if some power of the matrix contains all positive entries. A Markov chain is a regular Markov chain if its transition matrix is regular. This matrix L gives the long range trend of the Markov chain. It can be found by solving a system of linear equations. 7.7.4 Steady state:(solution set): (Equilibrium Matrix): A probability matrix which is the solution to LP=L is called equilibrium Matrix. Absorbing Markov Chain: A state 𝑆 of a Markov chain is called absorbing if it is not possible to leave it. A Markov chain is absorbing if it has at least one absorbing state. Example 2: After close analysing the weather for several years, a meteorologist concludes: The chance of a day after a sunny day is sunny 80% and cloudy 20% of the time. The chance of a day after a cloudy day is sunny 60% and cloudy 40% of time. Find the long range trend. Solution: The diagram of the Markov chain for this process having two states sunny(S) and cloudy(C) is
munotes.in
Page 83
83
Eigen Vectors The transition matrix P= 𝑆𝐶0.80.20.60.4ᇩᇭᇪᇭᇫௌ To find long term probabilities, we have to solve LP=L where L = [vଵvଶ]. [vଵvଶ]ቂ0.80.20.60.4ቃ = [vଵvଶ] 0.8vଵ+0.6vଶ=vଵ and 0.2vଵ+0.4vଶ=vଶ -0.2vଵ+0.6vଶ=0 and 0.2vଵ−0.6vଶ=0 Both the equations are same 0.2vଵ= 0.6vଶ vଵ = 3vଶ But we have vଵ+vଶ=1 (probability vector) Solving these equations, we have vଵ=ଷସ and vଶ=ଵସ Hence L= ቂvଵvଶቃ = ଷସଵସ This vector L= ଷସଵସ is a long term, the probability that the process will be in state 1 is ଷସ and the probability that the process will be in state 2 is ଵସ. Example 3: Assume that a man’s profession can be classified as professional, skilled labourer or unskilled labourer. Assume that, of the sons of professional men, 80% are professional, 10% are skilled labourers and 10% are unskilled labourers. In the case of sons of skilled labourers 60% are skilled labourers, 20% are professionals and 20% are unskilled. Finally, in the case of unskilled labourers, 50% of the sons are unskilled labourers, and 25% each are in the other two categories. Assume that every man has at least one son, and form a Markov chain by following the profession of a randomly chosen son of a given family trough several generations. Form the transition matrix and find probability of their long run behaviour.
munotes.in
Page 84
84 Linear algebra using python Solution: Let P, S and U denote the three states as professional, skilled labourer and unskilled labourer. According to the given information, Transition matrix P is P= 𝑃𝑆𝑈⎣⎢⎢⎢⎡0.80.10.10.20.60.20.250.250.5ᇩᇭᇭᇭᇭᇪᇭᇭᇭᇭᇫௌ⎦⎥⎥⎥⎤ Let L = (xଵ,xଶ,xଷ) be probability vector. Then long term behaviour can be found by solving L*P = L. (xଵ,xଶ,xଷ) PSU⎣⎢⎢⎢⎡0.80.10.10.20.60.20.250.250.5ᇩᇭᇭᇭᇭᇪᇭᇭᇭᇭᇫୗ⎦⎥⎥⎥⎤ = (xଵ,xଶ,xଷ) Then 0.8xଵ+0.2xଶ+0.25xଷ=xଵ -0.2xଵ+0.2xଶ+0.25xଷ=0----------------(i) 0.1xଵ+0.2xଶ+0.25xଷ=xଶ 0.1xଵ−0.4xଶ+0.25xଷ=0----------------------(ii) And 0.1xଵ+0.2xଶ+0.5xଷ=xଷ 0.1xଵ+0.2xଶ−0.5xଷ=0--------------------------(iii) Equation (iii) is the sum of equation (i) and equation (ii). From equation (i), we get 5xଷ=4xଵ−4xଶ---------------------------------(iv) And from (iii), we get 5xଷ=xଵ+2xଶ---------------------------(v) Solving(iv)and(v),weget, xଵ=2xଶ and xଷ=ସହxଶ Since L is the probability vector, hence, xଵ+xଶ+xଷ=1 2xଶ+xଶ+ସହxଶ=1 xଶ= ହଵଽ Now we have L= ⎣⎢⎢⎢⎡ଵଵଽହଵଽସଵଽ⎦⎥⎥⎥⎤. munotes.in
Page 85
85
Eigen Vectors 7.8 MODELLING A WEB SURFER: PAGERANK A search query with Google’s search engine usually returns a very large number of pages. Google assigns a number to each individual webpage based on the link structure of the web, expressing its importance. This number is known as the page rank and is computed via the page rank algorithm. It has applications in search, browsing and traffic estimation. 7.8.1 Page Rank algorithm as a Markov Process: We describe page rank algorithm as a Markov process, web page as state of Markov chain, Link structure of web as transitions probability matrix of Markov chains. It mainly focus on how to relate the eigenvalues and eigen vector of Google matrix to page rank values to guarantee that there is a single stationary distribution vector to which the page rank algorithm converges and efficiently compute the page rank for large sets of web pages. 7.8.2 Basic Page Rank Algorithm Model: A webpage U’s page rank is calculated base on how many other webpages backlink into U. The page rank of U is the sum of the page ranks of each webpage 𝑣 that back links to U divided by the number of webpages to which 𝑣 links. That means if webpage U is linked to only low page ranks web pages, it may not get more importance. Moreover If U is linked by a webpage 𝑣 with a high page rank, but 𝑣 links to many other pages, U should not receive the full weight of 𝑣’s page rank. Let U=web page 𝐹௨=Forward links from U 𝐵௨=Back links into U C=normalization factor so that the total rank of all web pages is constant. Then page rank (by simple rankin)=R(U)=C∑ோ()ேೇ௩∈ೠ where C<1 7.8.3 Random web surfer Model: Page rank can also be defined as the model of a random web surfer navigating the internet. That means the model states that the page rank models the behavior of someone who keeps clicking on successive links at random. Consider a simple link structure of web pages: We can represent this structure using NXN adjacency matrix A, where 𝐴=1 if there is a link from webpage i to webpage j, and 0 otherwise. Let N=total number of webpages in the web. 𝜋்= 1𝑋𝑁 𝑝𝑎𝑔𝑒 𝑟𝑎𝑛𝑘 𝑟𝑜𝑤 𝑣𝑒𝑐𝑡𝑜𝑟 (𝑠𝑡𝑎𝑡𝑖𝑜𝑛𝑎𝑟𝑦 𝑣𝑒𝑐𝑡𝑜𝑟) munotes.in
Page 86
86 Linear algebra using python H=NXN row normalized adjacency matrix(or) Transition probability matrix Thus we can describe the page rank vector at the 𝑘௧ iteration as, 𝜋்=𝜋(ିଵ)்𝐻 To build a transition probability matrix 𝐻=∑ೖಿೖసభ So that each row 𝐴 of A is divided by its row sum. Consider the following diagram that shows the link of web pages A,B,C,D ,E and F
The 6X6 adjacency matrix for the above link structure is A = ⎣⎢⎢⎢⎢⎡010000011000011100001000000000⎦⎥⎥⎥⎥⎤ Transition probability matrix H is H= ⎣⎢⎢⎢⎢⎢⎢⎡0ଵଶ00ଵଶ000ଵଶଵଶ00000ଵଷଵଷଵଷ100000100000000000⎦⎥⎥⎥⎥⎥⎥⎤ But the matrix H is not stochastic due to dangling node F which has no outgoing links. It affects the model because it is not clear where its weight should be distributed. To overcome this type of problem, we assign artificial link to dangling node.
munotes.in
Page 87
87
Eigen Vectors Therefore, we define the stochastic S as, S= H+ ∗ே Where a = NX1 column vector such that 𝑎 =1 𝑖𝑓,∑𝐻=0ேୀଵ = 0, otherwise. E=NX1 column vector of one’s For the above example:S= ⎣⎢⎢⎢⎢⎢⎢⎡0ଵଶ00000ଵଶଵଶ0000ଵଷଵଷ1000010000ଵଵଵଵଵ⎦⎥⎥⎥⎥⎥⎥⎤ It makes sure that the surfer’s random walk process does not get stuck and the web pages are the states of the Markov chain. 7.8.4 Google matrix: The above matrix S has a unique stationary distribution vector 𝜋் , if S is irreducible as well as stochastic. A matrix is irreducible if and only if its graph is strongly connected. So, we define the irreducible row stochastic matrix G as G= 𝛼𝑆+(1−𝛼)𝐸; 0≤𝛼≤1 𝑎𝑛𝑑 𝐸= ே G is the Google matrix defined as 𝜋்=𝜋(ିଵ)்𝐺 as the new iterative method for page rank. For this above example: G= ⎣⎢⎢⎢⎢⎢⎢⎢⎢⎡ଵସଽଶଵସଵସଽଶଵସଵସଵସଽଶଽଶଵସଵସଵସଵସଵସଶହଶହଶହ଼ଵସଵସଵସଵସଵସ଼ଵସଵସଵସଵସଵସ଼ଷହ଼ଷହ଼ଷହ଼ଷହ଼ଷହ଼ଷହ⎦⎥⎥⎥⎥⎥⎥⎥⎥⎤ The power method: The Google matrix G is currently of size max than eight billion webpages. So the Eigen value competition not so easy. We iterate using the Google matrix G by writing 𝜋்=𝜋(ିଵ)்𝐺 munotes.in
Page 88
88 Linear algebra using python When dealing with large data sets, it is difficult to form a matrix G. It is more efficient to compute page rank vector using the power method, where we iterate using the sparse matrix H by rewriting the above equation as, 𝜋்=𝜋(ିଵ)்𝐺 = 𝜋(ିଵ)்(𝛼𝑆+(1−𝛼)𝐸 = 𝜋(ିଵ)்(𝛼𝑆+(1−𝛼)(ே) = 𝛼𝜋(ିଵ)்S + (1−𝛼) 𝜋(ିଵ)்(ே) = 𝛼𝜋(ିଵ)்S+ (1−𝛼)ே = 𝛼𝜋(ିଵ)்(𝐻+ே)+ (1−𝛼)ே = 𝛼𝜋(ିଵ)்𝐻+( 𝛼𝜋(ିଵ)்a+ (1−𝛼)ே Since 𝜋(ିଵ)் is a probability vector and thus 𝜋(ିଵ)்e = 1. The size of the Markov matrix makes storage issues non-trivial. For modern web structure for which the transition probability matrix H can be stored in main memory, compression of the data is not essential. In order to compute the page rank vector, the page rank power method requires vector matrix multiplication of 𝜋(ିଵ)்𝐻 at each iteration k. Hence we can say page rank is a global ranking of all web pages, regardless of their content based solely on their location in the web’s link structure. Using page rank, we are able to order search results so that more important and control webpages are given preference. 7.9 SUMMARY Any scalar λ and vector v that satisfies the relationship Av = λv are called an eigenvalue and an eigenvector respectively of the square matrix A. Eigenvalues and eigenvectors for a linear transformation T: V → V are determined by locating the eigenvalues and eigenvectors of any matrix representation for T; the eigenvectors of the matrix are coordinate representations of the eigenvector of T. An n*n matrix is diagonalizable if and only if it has n linearly independent eigenvectors. 7.10 REFERENCES 1. Linear Algebra and Probability for Computer Science Applications, Ernest Davis, A K Peters/CRC Press (2012). 2. Linear Algebra and Its Applications, Gilbert Strang, Cengage Learning, 4th Edition (2007). munotes.in
Page 89
89
Eigen Vectors Exercise Q1. Find Eigen values and Eigen vectors for the following i.2−1112−11−12൩ ii. 3−11−15−11−13൩ iii.201020102൩ iv.−22−321−6−1−20൩ v.211232334൩ Q2: Check whether the following matrices are diagonalizable or not, if yes, diagonalize them: i.−122121−1−10൩ ii. 10−1121223൩ iii.3−11−15−11−13൩ iv.111021−443൩ v.123020002൩ vi.3105−2−3−4357൩ Q3: Find the long term probability vector for the following Markov Process: i. In the dark ages, Harward, Dard mouth and Yale admitted only male students. Assume that , at that time 80% of the sons of Harward men went to Harward and rest went to Yale, 40% of the sons of Yale men went Yale, and the rest split evenly between Harward and Dard munotes.in
Page 90
90 Linear algebra using python mouth; and of the sons of Dard mouth men, 70% went to Dard mouth, 20% went to Harward, and 10% to Yale. Formulate Markov chain and find probability of their long term behavior. ii. A salesman’s territory consists of 3 cities A,B and C . He never sells in the same city on successive days. If he sells in city A, then the next day he sell in B. However if he sells in either B or C, then the next day he is twice likely to sell in city A as in the other city. In long run, how often does he sell in each of the cities? iii. Two boys 𝑢ଵ 𝑎𝑛𝑑 𝑢ଶ and two girls 𝑔ଵ 𝑎𝑛𝑑 𝑔ଶ are throwing a ball each other.Each boy throws the ball to the other boy with probability ଵଶ and each to the girl with probability ଵସ. On the other hand , each throws the ball to each boy with probability ଵଶ and never to the other girls. In the long run, how often does each receive the ball. A man walks along a four-block stretch of part-Avenue. If he is at corner 1,2,or3 then he walks to the left or right with equal probability. He continues until he reaches corner 4, which is a restaurant or corner 0, which is his home. If he reaches either home or restaurant, he stays there. Formulate the transition matrix for states 0,1,2,3 and 4 as a Markov chain. munotes.in