## MA180 & MA185 ALGEBRA (SEMESTER I) LECTURER: GRAHAM ELLIS

### SYLLABUS & LEARNING OUTCOMES

For the course syllabus, learning outcomes and assessment details see the course web page and the continuous assessment web page. At the end of this module you'll be able to tackle questions such as those on the 2013 exam paper and those on the 2014 exam paper.

### FORTNIGHTLY HOMEWORKS

The fortnightly homeworks count 40% towards the module assessment.

To register for homeworks use your eight digit ID number, and choose a memorable password for the homework system. Don't forget your MA180/MA185/MA190 password because I am unable to reset it for you!

### WEEKLY WORKSHOPS

Workshops begin on Monday 15th September. Details can be found here.

### WHAT IS MATHEMATICS?

I'm not too sure of the answer. But whatever it is it is possibly something a bit larger than what was taught in your school mathematics classes. If you are interested in the question then you should browse this article by Fields Medallist William Thurston. He won the Fields Medal for his work in geometry.

### ALGEBRAMATERIAL

Algebra text:

I can't find a single suitable book to recommend for the algebra lectures. So you'll just have to rely on the lecture notes and the various references given below in the lecture outlines.

Algebra outline:

This module introduces the student to matrix algebra and systems of equations, emphasizing that: (i) the entries of a matrix can be any "numbers" for which we have a suitable notion of addition and multiplication; (ii)  matrix arithmetic underpins Ireland's knowledge economy; (iii) matrix arithmetic over the "real numbers" has a fruitful geometric interpretation. The module is divided into three parts. Part I introduces a number system that will be new to many students. Part II introduces matrix arithmetic over this number system, as well as over the usual real number system. Part III develops a geometric interpretation for matrix arithmetic and systems of equations over the real numbers. Students will be expected to develop their understanding of the topics through extensive calculation rather than through formal theory.

Online Calculator: This online calculator will help with all your modular arithmetic calculations.

Algebra lectures 2014-15:

The algebra lecture slides will be uploaded to the web after each lecture and links to the slides will be given below. A brief outline of each lecture will be added below shortly after each lecture.

Here is some student feedback after the first six weeks. I'll try to respond to the criticisms as best I can.

### 1

Lecture 1:
Introduction to modular arithmetic. An application to the ISBN book number was explained.

For another introduction to modular arithmetic take a look at this Youtube clip. Then take a look at this clip, this clip and this clip

### 2

Lecture 2:
Explained Euclid's algorithm for finding the greatest common divisor of two numbers, and used it to find the inverse of some number n modulo m. An application of modular arithmetic to IBAN bank numbers was explained.

Take a look at this clip for another example of using the Euclidean algorithm to find the inverse of a number in modular arithmetic.

For more background on modular arithmetic take a look at the wikipedia page here.

### 3

Lecture 3:
Explained the basic ideas underlying cryptography. Discussed the Enigma machine and an affine cryptosystem on single letter message units.

For more background on the Enigma machine take a look at the wikipedia page here.
For more background on affine cryptosystems take a look at the wikipedia page here.

### 4

Lecture 4:
Deciphered an enciphered message sent from Agent 007.

### 5

Lecture 5:
Explained the Chinese Remainder Theorem.

For more background on the Chinese Remainder Theorem take a look at the wikipedia page here.
Also, take a look at this youtube explanation which uses easily calculated numbers,

### 6

Lecture 6:
Introduced Euler's phi (or totient) function.

For more background on Euler's phi function take a look at the wikipedia page here.

### 7

Lecture 7:
Explained the RSA public key cryptosystem.

For more background on the RSA cryptosystem take a look at the wikipedia page here.

### 8

Lecture 8:
Stated and illustrated Euler's Theorem. Then stated and proved a special case known as Fermat's little theorem.

For more background on Euler's Theorem take a look at the wikipedia page here.
For more background on Fermat's little heorem take a look at the wikipedia page here.

### 9

Lecture 9:
Introduced the notion of a matrix and the operations of addition, subtraction and multiplication.

For more background on matrix multiplication look at the wikipedia page here.

Take a look at this clip for examples of matrix multiplication.

### 10

Lecture 10 (part 1) and Lecture 10 (part 2):
Explained the notion of an affine matrix cryptosystem.

### 11

Lecture 11:
Deciphered a ciphertext obtained from an affine matrix cryptosystem. In the process I got lots of practice of matrix multiplication.

### 12

Lecture 12:
Introduced the concept of a linear transformation of the plane. Showed that reflection in a line through the origin is a linear transormation.

For more background on linear transformations take a look at the Open Corseware notes from MIT here.

### 13

Lecture 13:
Explained why every linear transformation of the plane can be represented by a 2x2 matrix. Stated a theorem that asserts that composition of transformations corresponds to multiplication of matrices. Matrix multiplication has been invented just so that this theorem is true.

I didn't get around to deriving the matrix representing rotation through an angle theta about the origin. See the slides of a previous year's lecture for this important derivation.

### 14

Lecture 14:
Illustrated the Gauss-Jordan method for inverting a matrix. The method uses a sequence of row operations.

### 15

Lecture 15:
Explained why the Gauss-Jordan method for finding the inverse of a matrix works.

Gave an example to illustrate that row operations can be used to solve systems of linear equations arising from "real life" problems.

For more background on systems of linear equations take a look at the wikipedia page here.

### 16

Lecture 16:
Defined the determinant and adjoint of a 2x2 matrix. Gave a formula for the inverse of a 2x2 matrix in terms of its determinant and adjoint. Explained that the determinant of a 2x2 matrix is equal to the area of a certain parallelogram up to sign.

### 17

Lecture 17:
Proved that the determinant of a 2x2 matrix is equal to the area of a certain parallelogram up to sign. Then introduced and illustrated the notions of eigenvector and eigenvalue of a matrix.

### 18

Lecture 18:
Explained how eigenvectors are involved in Google's page rank algorithm. (I intensionally over simplified the explanation. In particular, the importance In of a page is determined from the full network of pages on the internet and not just those [8 in my explanation] containg the given searched words.)

More details on the page rank algorithm can be found here.

Also stated and illustrated the important Hamilton-Cayley Theorem.

### 19

Lecture 19:
Explained how to find eigenvalues of a 2x2 matrix using the characteristic equation. Explained how to find eigenvectors for the given eigenvalues.

Derived the recurrence relation Fn = Fn-1 + Fn-2 for the number of rabbits in a field after n months, based on some assumptions about rabbit breeding.

### 20

Lecture 20:
Talked about various occurences of the Golden Ratio.

### 21

Lecture 21:
Explained how to express a suitable 2x2 matrix A in the form A=T-1 D T where D is diagonal. Here "suitable" means that A must have two eigenvectors such that the matrix T containing the two eigenvectors as columns is invertible.
Used the above expression to find a formula for the terms Fn in the Fibonacci sequence.

### 22

Lecture 22:
Used eigenvalues and eigenvectors to study a diseased population of frogs.

### 23

Lecture 23:
Did some revision.

### 24

Lecture Sem II:
This is a Semester II lecture about the validity of logical arguments.

Algebra lectures 2012-13:

The course content is similar to that of 2012-13 and 2011-12. Links to lecture slides from that year are available below.

Lecture 1 (2012-13): Introduction to modular aritmetic. This lecture had to be repeated due to a timetable mixup. So these slides are a compilation of the original lecture and the repeat lecture.

Lecture 1 (2011-12): Introduction to the course. Introduction to modular aritmetic. The notions of multiplicative inverse n-1 and additive inverse -n modulo m were explained. The ISBN number was explained. The lecture was short due to a power failure, so the IBAN was only partially explained!

Take a look at the Wikipedia for a good introduction to modular arithmetic.

Lecture 2 (2012-13):

Lecture 2 (2011-12): Explanation of a validation test for International Bank Accounts Numbers (IBANs) using arithmetic mod 97. Explanation of how the mod 97 value of a large integer can be calculated by hand. Introduction to cryptography (U-boats, Bletchley Park, secure internet pages etc.) and an example of a simple affine cryptosystem over a 26-letter alphabet in which message units are single letters. Some mod 26 calculations show that the composite of the enciphering function f(n) with the deciphering function f'(n) yields the identity function f'(f(n)) = n.

Lecture 3 (2012-13): Attacked and decoded a ciphertext sent using an affine cryptosystem with single letter message units. As part of the attack the Euclidean algorithm was used to find the inverse of an integer n modulo m. A careful analysis of this method for finding an inverse shows that a number n has an inverse modulo m if and only if gcd(m,n)=1.
Lecture 3 (2011-12):

See here for an obituary of Peter Hilton - Codebreaker and Mathematician. He worked at Bletchley Park during World War II.

Lecture 4 (2012-13 & 2011-12): A lady has a basket of eggs. If she packs them in boxes containing exactly 13 eggs she can pack all but 3 eggs. If she packs them in boxes of 14 she can pack all but 6 eggs. If she packs them in boxes of 15 she can pack all but 9 eggs. In order to determine the least possible number of eggs she could have we used the Chinese Remainder Theorem. (It's fun to use this theorem but a bit boring to state it. So we used it without stating it!)  At the start of the lecture we computed the last digit of a large power of an integer.

Take a look at the Wikepedia for a good account of the Chinese Remainder Theorem.

Lecture 5 (2011-12): RSA public key cryptography and Euler's Phi function.

Lecture 6 (2011-12): RSA Cryptography and Euler's Theorem.

Lecture 5 (2012-13). Here are the photos of those who attended this lecture on 27 September 2012. Photo 1, Photo 2, Photo 3.

Lecture 6 (2012-13).

( Some may also find it useful to look at the three lectures 1, 2, 3 on RSA cryptography given in 2010-11.)

Lecture 7 (2011-12): Deciphered a message sent to me using the RSA system. Explained how RSA can be used to sign/authenticate documents electronically. Stated and proved a special case of Euler's Theorem known as Fermat's Little Theorem.

(Those who'd like to see a proof of the proposition (x^e)^d = x mod n satisfied by the integers e,d,n used in RSA cryptography could take a look at the second part of this lecture which I gave last year.)

Lecture 8 (2011-12): Recalled the notion of an mxn matrix (m rows, n columns). Recalled addition/subtraction of two mxn matrices, and multiplication AB of an mxn matrix A with a nxp matrix B. Recalled the notions of: zero matrix, identity matrix, inverse matrix. From the definition of an inverse matrix we evaluated the inverse of a 2x2 matrix modulo 5.

Lecture 9 (2011-12): Gave the formula for the inverse of a 2x2 matrix, and indicated its importance in affine encryption systems with message units of length 2.

Lecture 10 (2011-12): Used the inverse of a 2x2 matrix modulo 37 to attack an affine cryptosystem with 2-letter message units. We finished off the attack using a computer implementation of the cryptosystem.

Lecture 11 (2011-12): Introduced the notion of a linear transformation and gave various examples. Also gave an example of a transformations which is not linear.

Lecture 12 (2011-12): Proved that any linear transformation can be represaented by a matrix. Stated (without proof) that any reflection in a line through the origin is linear, as is any rotation about the origin. Noted that if S, T are two linear transformations represented by matrices A, B, then the composite transformation SoT: v ->S(T(v)) is represented by the matrix product AB. Derived the matrix representing an anticlockwise rotation through an angle theta about the origin.

Lecture 13 (2011-12): Illustrated the Gauss-Jordan method for finding the inverse of a square matrix. The method is based on three types of row operations: i) Add a multiplie of one row to a different row; ii) interchange two rows; (iii) multiply a row by a non-zero (i.e. invertible!!) scalar.

Lecture 14 (2011-12): Explained how each of the three row operations can be represented as pre-multiplication by a suitable matrix. Then proved that the Gauss-Jordan method always yields the inverse of a matrix when an inverse exists. (The proof incorporates a hidden assumption which is true but a bit tricky to prove. Please do try to spot the hidden assumption!) Finished off by explaining how systems of linear equations arise in real life, and how row operations can be used to solve such systems.

Lecture 15 (2011-12): Gave the definition and some basic properties of the determinant of a 2x2 matrix.

Lecture 16 (2011-12): Proved that the determinant of a 2x2 matrix is equal to the area of a parallelogram (up to sign). Then gave the definition of an eigenvalue and eigenvector, together with examples and a method for computing eigenvalues and vectors.

Lecture 17 (2011-12): Motivated by a problem of mathematically modelling a field of breeding rabbits, we used eigenvalues and eigenvectors to study the Fibonacci sequence and the Golden Ratio.

Lecture 18 (2011-12): Started with three equivalent definitions of the Golden Ratio, and mentioned its role in aesthetics. The used eigenvectors to find a closed formula for the n-th term of the Fibonacci sequence.

Lecture 19 (2011-12): Motivated by a problem of mathematically modelling an island of infected frogs, the notion of a Markov matrix and Markov process was introduced and used to study the long term prognosis for the island's frog population.

Lecture 20 (2011-12): Starting from a model of the internet as a collection of nodes, and arrows from one node to another, we saw how the eigenvector corresponding to the largest eigenvalue of a certain Markov matrix gives the ranking produced by a Google search. The very important Hamilton Cayley Theorem was squaezed in at the end of the lecture.

See this link for a more detailed account of Google's page rank algorithm.

In Lectures 21 and 22 (2011-12) I worked through some old exam questions (and found a slip in one of them)!