Elementary Linear Algebra

UVM/IIS

Thursday, July 8, 2010

 EUCLIDEAN SPACE
Thursday, July 8, 2010
 Euclidean Space is
The Euclidean plane and three-dimensional space
of Euclidean geometry, as well as the
generalizations of these notions to higher
dimensions.

The term “Euclidean” is used to distinguish these

spaces from the curved spaces of non-Euclidean
geometry and Einstein's general theory of
relativity.

Thursday, July 8, 2010

 Euclidean Space

Euclidean n-space, sometimes called Cartesian

space, or simply n-space, is the space of all n-
tuples of real numbers (x1, x2, ..., xn).
n
It is commonly denoted R , although older
n
literature uses the symbol E .

Thursday, July 8, 2010

 Euclidean Space

n
R is a vector space and has Lebesgue covering
dimension n.
n
Elements of R are called n-vectors.

R 1= R is the set of real numbers (i.e., the real line)

2
R is called the Euclidean Space.

Thursday, July 8, 2010

 One Dimension
1
R = R is the set of real numbers (i.e., the real line)

-∞ 0 ∞

√2

-∞ 0 1 √2 ∞
(1.41)

Thursday, July 8, 2010

 Two Dimensions
2
R is called the Euclidean Space.

P(-2, 1)

-∞ 0 ∞

-∞

Thursday, July 8, 2010

 Three Dimensions

y
P(2, 2, -2)
∞

-∞ 0 ∞
x

z -∞

Thursday, July 8, 2010

 n Dimensions
1
R Space of One Dimension (x, y)
2
R Space of Two Dimensions (x, y)
3
R Space of Three Dimensions (x, y, z)
4
R Space of Four Dimensions (x1, x2, x3, x4)
n
R Space of n Dimensions (x1, x2, x3, ...., xn)

Thursday, July 8, 2010

 SOLUTION OF EQUATIONS
Thursday, July 8, 2010
 Solutions of Systems of
Linear Equations
x1 + x 2 = 1
x1 - x 2 = 1
∞
HAS ONLY ONE SOLUTION:

x1 = 1
x2 = 0 0
-∞ ∞

-∞

Thursday, July 8, 2010

 Solutions of Systems of
Linear Equations
x1 + x 2 = 1
x1 + x 2 = 2
∞
HAS NO SOLUTIONS

-∞ 0 ∞

-∞

Thursday, July 8, 2010

 Solutions of Systems of
Linear Equations
x1 + x 2 = 1
2x1 + 2x2 = 2
∞
HAS INFINITELY MANY
SOLUTIONS

-∞ 0 ∞

-∞

Thursday, July 8, 2010

 Solutions of Systems of
Linear Equations
In general:

A SYSTEM OF LINEAR EQUATIONS CAN HAVE EITHER:

No solutions
Exactly one solution
Infinitely many solutions

Definition: If a system of equations has no solutions it is called

an inconsistent system. Otherwise the system is consistent.

Thursday, July 8, 2010

 Matrix Notation
MATRIX = RECTANGULAR ARRAY OF NUMBERS

( )( ) )
0 1 -2 4
3 -1 1
2 0 0 1
2 0 2
1 1 3 9

EVERY SYSTEM OF LINEAR EQUATIONS CAN BE

REPRESENTED BY A MATRIX
Thursday, July 8, 2010
 Elementary Row
Operations
1. INTERCHANGE OF TWO ROWS

( )( ) ) 0

1
1

1
-2

3
4

9
1

0
1

1
3

-2
9

Thursday, July 8, 2010

 Elementary Row
Operations
2. MULTIPLICATION OF A ROW BY A NON-ZERO NUMBER

( ) ( ) ) 1

5
0

5
3

1
4

0
*3
1

5
0

5
3

1
4

Thursday, July 8, 2010

 Elementary Row
Operations
3. ADDITION OF A MULTIPLE OF ONE ROW TO ANOTHER ROW

( ) ( ) ) 1

5
0

5
3

1
4

0
*2
1

7
0

5
3

7
4

Thursday, July 8, 2010

 How to Solve Systems
of Linear Equations

( )
-1 2 3 4
-x1 + 2x2 + 3x3 = 4

)
2x1 + 6x3 = 9 2 0 6 9
4x1 - x2 - 3x3 = 0
4 -1 -3 0

( )
x1 = ...
x2 = ... NICE MATRIX
x3 = ...

Thursday, July 8, 2010

 Linear Algebra Application
Google PageRank

Thursday, July 8, 2010

 Early Search Engines

SEARCH QUERY
DATABASE OF
WEB SITES LIST OF MATCHING WEBSITES
IN RANDOM ORDER

PROBLEM:
HARD TO FIND USEFUL SEARCH RESULTS

Thursday, July 8, 2010

 Google Search Engine

DATABASE OF SEARCH QUERY

WEB SITES
WITH MATCHING WEBSITES
RANKINGS! IMPORTANT SITES FIRST!

Thursday, July 8, 2010

 How to Rank?

VERY SIMPLE RANKING:

Ranking of a page = number of links

pointing to that page

PROBLEM: VERY EASY TO MANIPULATE

Thursday, July 8, 2010

 Google PageRank
IDEA: LINKS FROM HIGHLY RANKED PAGES
SHOULD WORTH MORE

IF
Ranking of a page is x
The page has links to n other pages
THEN
Each link from that page should be
worth x/n

Thursday, July 8, 2010

 Google PageRank
THIS GIVES EQUATIONS:

x1 = x3 + 1/2 x4
x2 = 1/3 x1
x3 = 1/3 x1 + 1/2 x2 + 1/2 x4
x4 = 1/3 x1 + 1/2 x2

Thursday, July 8, 2010

 Google PageRank
MATRIX EQUATION:

( ) ( )( ) )
x1 0 0 1 1/2 x1

x2 1/3 0 0 0 x2
=
x3 1/3 1/2 0 1/2 x3

x4 1/3 1/2 0 0 x4

COINCIDENCE MATRIX
OF THE NETWORK
Thursday, July 8, 2010
 Google PageRank

( ) ( )( ) )
x1 0 0 1 1/2 x1

x2 1/3 0 0 0 x2
=
x3 1/3 1/2 0 1/2 x3

x4 1/3 1/2 0 0 x4

( x1, x2, x3, x4 ) is an eigenvector of the

coincidence matrix corresponding to the
eigenvalue 1.

Thursday, July 8, 2010