Social network viSualization

Documents
196 pages
Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus

Description

Social network viSualization Name: Jasper A. Schelling Studentnumber: 0757136 Graduation Year: 2007 Major: Communicatie & Multimedia Design Minor: Interaction & Visual Interface Design Title: Social Network visualization Subject: Social network visualization Short description: Resarch into the posibilities of visually representing social networks on social networking websites and the effects on the experience of friendship in social net working websites. Graduation supervisor school: B.L.F. Leurs Graduation supervisors in company: P. Post & M. Kraft Copyrights: Jasper Schelling Version: 1.0
  • ‘rich internet application
  • 2.3 interaction design
  • friendship as an informal category without clear boundaries
  • emotional model
  • contacts from the networks
  • definition of friendship differs from person to person
  • social networks
  • friendship

Sujets

Informations

Publié par
Nombre de visites sur la page 23
Langue English
Signaler un problème

Fundamentals of Linear Algebra
Marcel B. Finan
Arkansas Tech University
°c All Rights Reserved
October 9, 20012
PREFACE
Linear algebra has evolved as a branch of mathematics with wide range of
applications to the natural sciences, to engineering, to computer sciences, to
management and social sciences, and more.
This book is addressed primarely to second and third your college students
who have already had a course in calculus and analytic geometry. It is the
result of lecture notes given by the author at The University of North Texas
and the University of Texas at Austin. It has been designed for use either as a
supplement of standard textbooks or as a textbook for a formal course in linear
algebra.
This book is not a ”traditional” book in the sense that it does not include
any applications to the material discussed. Its aim is solely to learn the basic
theory of linear algebra within a semester period. Instructors may wish to in-
corporate material from various fields of applications into a course.
I have included as many problems as possible of varying degrees of difficulty.
Most of the exercises are computational, others are routine and seek to fix
some ideas in the reader’s mind; yet others are of theoretical nature and have
the intention to enhance the reader’s mathematical reasoning. After all doing
mathematics is the way to learn mathematics.
Marcecl B. Finan
Austin, Texas
March, 2001.Contents
1 Linear Systems 5
1.1 of Linear Equations. . . . . . . . . . . . . . . . . . . . . 5
1.2 Geometric Meaning of Linear Systems . . . . . . . . . . . . . . . 8
1.3 Matrix Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.4 Elementary Row Operations . . . . . . . . . . . . . . . . . . . . 13
1.5 Solving Linear Systems Using Augmented Matrices . . . . . . . . 17
1.6 Echelon Form and Reduced Echelon Form . . . . . . . . . . . . . 21
1.7 Echelon Forms and Solutions to Linear Systems . . . . . . . . . . 28
1.8 Homogeneous Systems of Linear Equations . . . . . . . . . . . . 32
1.9 Review Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
2 Matrices 43
2.1 Matrices and Matrix Operations . . . . . . . . . . . . . . . . . . 43
2.2 Properties of Multiplication . . . . . . . . . . . . . . . . . 50
2.3 The Inverse of a Square Matrix . . . . . . . . . . . . . . . . . . . 55
2.4 Elementary Matrices . . . . . . . . . . . . . . . . . . . . . . . . . 59
¡12.5 An Algorithm for Finding A . . . . . . . . . . . . . . . . . . . 62
2.6 Review Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
3 Determinants 75
3.1 Definition of the Determinant . . . . . . . . . . . . . . . . . . . . 75
3.2 Evaluating Determinants by Row Reduction . . . . . . . . . . . . 79
3.3 Properties of thet . . . . . . . . . . . . . . . . . . . . 83
¡13.4 Finding A Using Cofactor Expansions . . . . . . . . . . . . . . 86
3.5 Cramer’s Rule. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
3.6 Review Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
4 The Theory of Vector Spaces 101
4.1 Vectors in Two and Three Dimensional Spaces . . . . . . . . . . 101
4.2 Vector Spaces, Subspaces, and Inner Product Spaces . . . . . . . 108
4.3 Linear Independence . . . . . . . . . . . . . . . . . . . . . . . . . 114
4.4 Basis and Dimension . . . . . . . . . . . . . . . . . . . . . . . . . 120
4.5 Transition Matrices and Change of Basis . . . . . . . . . . . . . . 128
4.6 The Rank of a matrix . . . . . . . . . . . . . . . . . . . . . . . . 133
34 CONTENTS
4.7 Review Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
5 Eigenvalues and Diagonalization 151
5.1 Eigenvalues and Eigenvectors of a Matrix . . . . . . . . . . . . . 151
5.2 Diagonalization of a Matrix . . . . . . . . . . . . . . . . . . . . . 164
5.3 Review Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
6 Linear Transformations 175
6.1 Definition and Elementary Properties . . . . . . . . . . . . . . . 175
6.2 Kernel and Range of a Linear Transformation . . . . . . . . . . . 180
6.3 The Matrix Representation of a Linear Transformation . . . . . . 189
6.4 Review Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . 194
7 Solutions to Review Problems 197Chapter 1
Linear Systems
Inthischapterweshalldevelopthetheoryofgeneralsystemsoflinearequations.
Thetoolwewillusetofindthesolutionsistherow-echelonformofamatrix. In
fact, the solutions can be read off from the row- echelon form of the augmented
matrix of the system. The solution technique, known as elimination method,
is developed in Section 1.4.
1.1 Systems of Linear Equations
Many practical problems can be reduced to solving systems of linear equations.
The main purpose of linear algebra is to find systematic methods for solving
thesesystems. Soitisnaturaltostartourdiscussionoflinearalgebrabystudy-
ing linear equations.
A linear equation in n variables is an equation of the form
a x +a x +:::+a x =b (1.1)1 1 2 2 n n
wherex ;x ;:::;x aretheunknowns(i.e. quantitiestobefound)anda ;¢¢¢;a1 2 n 1 n
are the coefficients ( i.e. given numbers). Also given the number b known as
theconstant term. Observe that a linear equation does not involve any prod-
ucts, inverses, or roots of variables. All variables occur only to the first power
and do not appear as arguments for trigonometric, logarithmic, or exponential
functions.
Exercise 1
Determine whether the given equations are linear or not:
(a) 3x ¡4x +5x =6:1 2 3
(b) 4x ¡5x =x x :1 2 1 2p
(c) x =2 x ¡6:2 1
(d) x +sinx +x =1:1 2 3
(e) x ¡x +x =sin3:1 2 3
56 CHAPTER 1. LINEAR SYSTEMS
Solution
(a) The given equation is in the form given by (1.1) and therefore is linear.
(b)Theequationisnotlinearbecausethetermontherightsideoftheequation
involves a product of the variables x and x :1 2p
(c) A nonlinear equation because the term 2 x involves a square root of the1
variable x :1
(d) Since x is an argument of a trigonometric function then the given equation2
is not linear.
(e) The equation is linear according to (1.1)
A solution of a linear equation (1.1) in n unknowns is a finite ordered col-
lection of numbers s ;s ;:::;s which make (1.1) a true equality when x =1 2 n 1
s ;x =s ;¢¢¢;x =s are substituted in (1.1). The collection of all solutions1 2 2 n n
of a linear equation is called the solution set or the general solution.
Exercise 2
Show that (5+4s¡7t;s;t); where s;t2IR; is a solution to the equation
x ¡4x +7x =5:1 2 3
Solution
x =5+4s¡7t;x =s; and x =t is a solution to the given equation because1 2 3
x ¡4x +7x =(5+4s¡7t)¡4s+7t=5:1 2 3
A linear equation can have infinitely many solutions, exactly one solution or no
solutions at all (See Theorem 5 in Section 1.7).
Exercise 3
Determine the number of solutions of each of the following equations:
(a) 0x +0x =5:1 2
(b) 2x =4:1
(c) x ¡4x +7x =5:1 2 3
Solution.
(a)Sincetheleft-handsideoftheequationis0andtheright-handsideis5then
the given equation has no solution.
(b) By dividing both sides of the equation by 2 we find that the given equation
has the unique solution x =2:1
(c) To find the set of the given equation we assign arbitrary values s
and t to x and x , respectively, and solve for x ; we obtain2 3 1
8
< x = 5+4s¡7t1
x = s2
:
x = t3
Thus, the given equation has infinitely many solutions1.1. SYSTEMS OF LINEAR EQUATIONS 7
s and t of the previous exercise are referred to as parameters. The solu-
tion in this case is said to be given in parametric form.
Many problems in the sciences lead to solving more than one linear equation.
The general situation can be described by a linear system.
A system of linear equations or simply a linear system is any finite col-
lection of linear equations. A particular solution of a linear system is any
common solution of these equations. A system is called consistent if it has a
solution. Otherwise, itiscalledinconsistent. Ageneralsolutionofasystem
is a formula which gives all the solutions for different values of parameters (See
Exercise 3 (c) ).
A linear system of m equations in n variables has the form
8
a x +a x +:::+a x =b> 11 1 12 2 1n n 1<
a x +a x +:::+a x =b21 1 22 2 2n n 2
:::::::::::::::::::::::: ::::>>:
a x +a x +:::+a x =bm1 1 m2 2 mn n m
As in the case of a single linear equation, a linear system can have infinitely
many solutions, exactly one solution or no solutions at all. We will provide a
proof of this statement in Section 1.7 (See Theorem 5). An alternative proof of
the fact that when a system has more than one solution then it must have an
infinite number of solutions will be given in Exercise 14.
Exercise 4
Find the general solution of the linear system

x + x = 71 2
2x + 4x = 18:1 2
Solution.
Multiply the first equation of the system by ¡2 and then add the resulting
equation to the second equation to find 2x =4: Solving for x we find x =2:2 2 2
Plugging this value in one of the equations of the given system and then solving
for x one finds x =51 1
Exercise 5
By letting x =t; find the general solution of the linear system3

x + x + x = 71 2 3
2x + 4x + x = 18:1 2 3
Solution.
By letting x =t the given system can be rewritten in the form3

x + x = 7¡t1 2
2x + 4x = 18¡t:1 2
By multiplying the first equation by¡2 and adding to the second equation one
4+tfinds x = : Substituting this expression in one of the individual equations2 2
10¡3tof the system and then solving for x one finds x =1 1 26
6
6
6
6
6
6
8 CHAPTER 1. LINEAR SYSTEMS
1.2 Geometric Meaning of Linear Systems
Intheprevioussectionwestatedthatalinearsystemcanhaveexactlyonesolu-
tion, infinitely many solutions or no solutions at all. In this section, we support
our claim using geometry. More precisely, we consider the plane since a linear
equation in the plane is represented by a straight line.
Consider the x x ¡plane and the set of points satisfying ax +bx = c: If1 2 1 2
a = b = 0 but c = 0 then the set of points satisfying the above equation is
empty. If a = b = c = 0 then the set of points is the whole plane since the
2
equation is satisfied for all (x ;x )2IR :1 2
Exercise 6
Show that if a = 0 or b = 0 then the set of points satisfying ax +bx = c is a1 2
straight line.
Solution.
cIf a=0 but b=0 then the equation x = is a vertical line in the x x -plane.1 1 2a
cIf a = 0 but b = 0 then x = is a horizontal line in the plane. Finally, sup-2 b
pose that a = 0 and b = 0: Since x can be assigned arbitrary values then the2
given equation possesses infinitely many solutions. Let A(a ;a );B(b ;b ); and1 2 1 2
C(c ;c ) be any three points in the plane with components satisfying the given1 2
b ¡a2 2equation. The slope of the line AB is given by the expression m =AB b ¡a1 1
c ¡a2 2whereasthatofAC isgivenbym = :Fromtheequations aa +ba =cAC 1 2c ¡a1 1
b ¡a c ¡a2 2 a 2 2 aand ab +bb = c one finds = ¡ : Similarly, = ¡ : This shows1 2 b ¡a b c ¡a b1 1 1 1
that the lines AB and AC are parallel. Since these lines have the point A in
common then A;B; and C are on the same straight line
The set of solutions of the system

ax + bx = c1 2
0 0 0ax + bx = c1 2
istheintersectionofthesetofsolutionsoftheindividualequations. Thus,ifthe
system has exactly one solution then this solution is the point of intersection of
twolines. Ifthesystemhasinfinitelymanysolutionsthenthetwolinescoincide.
If the system has no solutions then the two lines are parallel.
Exercise 7
Find the point of intersection of the lines x ¡5x =1 and 2x ¡3x =3:1 2 1 2
Solution.
To find the point of intersection we have to solve the system

x ¡ 5x = 11 2
2x ¡ 3x = 3:1 2
Using either elimination of unknowns or substitution one finds the solution
12 1x = ;x = :1 27 76
1.2. GEOMETRIC MEANING OF LINEAR SYSTEMS 9
Exercise 8
Do the three lines 2x +3x = ¡1; 6x +5x = 0; and 2x ¡5x = 7 have a1 2 1 2 1 2
common point of intersection?
Solution.
Solving the system

2x + 3x = ¡11 2
6x + 5x = 01 2
5 3 5 15we find the solution x = ;x =¡ : Since 2x ¡5x = + = 5 = 7 then1 2 1 28 4 4 4
the three lines do not have a point in common
A similar geometrical interpretation holds for systems of equations in three
3unknowns where in this case an equation is represented by a plane in IR : Since
there is no physical image of the graphs for linear equations in more than three
unknowns we will prove later by means of an algebraic argument(See Theorem
5 of Section 1.7) that our statement concerning the number of solutions of a
linear system is still valid.
Exercise 9
Consider the system of equations
8
< a x + b x = c1 1 1 2 1
a x + b x = c2 1 2 2 2
:
a x + b x = c :3 1 3 2 3
Discuss the relative positions of the above three lines when
(a) the system has no solutions,
(b) the has exactly one solution,
(c) the system has infinitely many solutions.
Solution.
(a) The lines have no point of intersection.
(b) The lines intersect in exactly one point.
(c) The three lines coincide
Exercise 10
In the previous exercise, show that if c = c = c = 0 then the system has1 2 3
always a solution.
Solution.
If c = c = c then the system has at least one solution, namely the trivial1 2 3
solution x =x =01 26
10 CHAPTER 1. LINEAR SYSTEMS
1.3 Matrix Notation
Our next goal is to discuss some means for solving linear systems of equations.
InSection1.4wewilldevelopanalgebraicmethodofsolutiontolinearsystems.
But before we proceed any further with our discusion, we introduce a concept
that simplifies the computations involved in the method.
The essential information of a linear system can be recorded compactly in a
rectangular array called a matrix. A matrix of size m£n is a rectangular
array of the form
0 1
a a ::: a11 12 1n
B Ca a ::: a21 22 2nB C
@ A::: ::: ::: :::
a a ::: am1 m2 mn
where the a ’s are the entries of the matrix, m is the number of rows, and nij
is the number of columns. If n=m the matrix is called square matrix.
We shall often use the notation A = (a ) for the matrix A; indicating that aij ij
is the (i;j) entry in the matrix A:
An entry of the form a is said to be on themain diagonal. An m£n matrixii
A with entries a is calledupper triangular (resp. lower triangular) if theij
entries below (resp. above) the main diagonal are all 0. That is, a =0 if i>jij
(resp. i < j). A is called a diagonal matrix if a = 0 whenever i = j: By aij
triangular matrix we mean either an upper triangular, a lower triangular, or a
diagonal matrix.
Further definitions of matrices and related properties will be introduced in the
next chapter.
Now, let A be a matrix of size m£ n and entries a ; B is a matrix of sizeij
n£p and entries b : Then the product matrix is a matrix of size m£p andij
entries
c =a b +a b +¢¢¢+a bij i1 1j i2 2j in nj
that is c is obtained by multiplying componentwise the entries of the ith rowij
of A by the entries of the jth column of B: It is very important to keep in mind
that the number of columns of the first matrix must be equal to the number of
rows of the second matrix; otherwise the product is undefined.
Exercise 11
Consider the matrices
0 1
µ ¶ 4 1 4 3
1 2 4 @ AA= ;B = 0 ¡1 3 1
2 6 0
2 7 5 2
Compute, if possible, AB and BA: