Transcript Sense making in linear algebra

Sense making in linear
algebra
Lee Peng Yee
Bangkok
10-07-2008
Historical events
• Geometry went algebraic after Felix Klein
• Algebra turned abstract
• Linear algebra came from geometry
Contents
• Vector spaces and bases
• Matrices
• Eigenvalues and eigenvectors
Two questions
• Why linear algebra or motivation
• Why eigenvalues and eigenvectors
Why linear algebra
•
•
•
•
Linear systems
Geometric transformations
Markov chains
Lately linear codes
LINEAR CODES
• Message  encode  transmit
 received  decode  detect error 
correct error  final message
• Concepts used: vector space/linear space,
basis, matrices, matrix multiplication
An example
• {000 000, 001 110, 010 101, 011 011,
100 011, 101 101, 110 110, 111 000}
a linear code or a linear space (closed
under linear combination with 1 + 1 = 0)
• Elements in the space are codewords
Basis
• { 100 011, 010 101, 001 110 } forms a
basis for the space
{000 000, 001 110, 010 101, 011 011,
100 011, 101 101, 110 110, 111 000}
• Check 000 000 = 100 011 + 100 011,
011 011 = 010 101 + 001 110 etc
Generator matrix
1 0 0 0 1 1


G  0 1 0 1 0 1 
0 0 1 1 1 0
Message
•
•
•
•
[110] is a 3-bit message
We turn it into a codeword (encode)
Transmit the codeword
Then decode
Encoding
1 0 0 0 1 1


1 1 00 1 0 1 0 1  1 1 0 1 1 0
0 0 1 1 1 0
Message received
• The codeword [110 110] is transmitted
• Suppose the received word is
[100 110] (with an error)
• [100 110] is not a codeword
• How do we decode, detect the error and
correct it?
Parity check matrix
0 1 1 1 0 0 


H  1 0 1 0 1 0 
1 1 0 0 0 1
Decoding
1
1
0 1 1 1 0 0    0 
1 0 1 0 1 0 0  0

 1  
1 1 0 0 0 1   0
1
0 
 
1
0 
0 1 1 1 0 0   1
1 0 1 0 1 0 0  0

 1  
1 1 0 0 0 1   1
1
0 
 
Error detecting
• If HxT = [0 0 0]T then x is a codeword
• If HxT = [1 0 1]T then en error is detected
• If x is a codeword, r is received word, and
e is error then
HrT = HxT + HeT = HeT
Error correcting
• [1 0 1]T is the syndrome of the errors
• [1 0 0 1 1 0] has an error in the second
entry
• The corrected message is [1 1 0 1 1 0]
Summary
•
•
•
•
Codewords of length 6
3-bit messages
At most one error
Use generator matrix to encode and parity
check matrix to decode
Hamming code (1950)
• {0000000, 1101001, 0101010, 1000011,
1001100, 0100101, 1100110, 0001111,
1110000, 0011001, 1011010, 0110011,
0111100, 1010101, 0010110, 1111111}
the (7,4) Hamming code
An application of linear codes
• In 1971 Mariner 9 transmitted pictures of
Mars back to earth
• The distance between Mars and earth is
84 million miles
• The transmitter on Mariner 9 had only 20
watts
Why eigenvectors
• Diagonalization
• Write A = PDP-1 where D is a diagonal
matrix Then An = PDnP-1 (used in Markov
chains)
• Alternatively use geometry
EIGENVECTORS
 3 1 1 1

   4 
 1 3 1 1
 3 1   1   1

   2 
 1 3  1   1 
4 and 2 are called eigenvalues
1
  1
  and  
1
1
are called eigenvectors
What are they for?
Suppose
 3  1   1
      2 
  1 1  1 
Then
 3 1  3   3 1 1  3 1   1

   
   2
 
 1 3   1  1 31  1 3 1 
1
  1  8 
 4   2  2    
1
 1   0
We reduce matrix multiplication
to scalar multiplication.
Geometric meaning
 3 1  1   3

    
 1 3 0   1 
 3 1 1 1

   4 
 1 3 1 1
Finding eigenvectors
using geometry
Finding eigenvectors
using geometry
 3 1  1   3

    
 1 3 0   1 
 3 1   1   2 

    
 1 3 1   2 
 3 1  0    1 

    
 1 3  1   3
 3 1 1 1

   4 
 1 3 1 1
 3 1   1   3

    
 1 3 0    1 
 3 1  0   1 

    
 1 3 1   3
 3 1   1   4 

    
 1 3  1   4 
 3 1  1   2 

    
 1 3  1   2 
Using eigenvectors as coordinates
 3 1  maps  3 
 


  1
 1 3
into
8
 
0
 3 1  maps  1  into  4  1    4 


2  (2)  4
 2

  
 
 1 3
Using eigenvectors as coordinates
Eigenvectors as geometry
• To find eigenvectors is to find new
coordinates
• To find new coordinates is to simplify
computation
• Linear algebra is by no means abstract
Two recent reports
• www.ed.gov/MathPanel
• www.reform.co.uk/documents/The%20valu
e%20of%20mathematics.pdf
To teach mathematics
is to teach skills and rigour
END
[email protected]