MTH1030/35: Assignment 2, 2022 Applications of matrices

The Rules of the Game

Before starting to work on this assignment, please make sure that you understand the in- structions on Moodle that go with our assignments (Assignment 1 (=Assignment 2) rules and F.A.Q. plus Academic integrity, plagiarism, and collusion policy).

Your submission for this assignment should be ONE pdf file.

This assignment is worth 100 marks.

Now, let’s have some fun!

1    Funny numbers (25 Marks)

Let’s call a 2 ⇥ 2 matrix a funny number if it is of the form

 ◆

a) Show that:  i) the identity matrix is a funny number; ii) sums and products of funny numbers are funny numbers; iii) all funny numbers except for one (which one?)  have an inverse; iv) multiplication of funny numbers is commutative (that is, given any two funny numbers A and B, it is always true that AB = BA).  (10 Marks)

Together with the fact that matrix multiplication and addition are associative, distributive, and so on, this means that funny numbers really do behave like real numbers. This means, that you can do linear algebra with funny numbers instead of real numbers.  Let’s do that in the next question.

b) What is the solution of the following system of two linear equations with funny number coefficients in the funny number unknowns X and Y?

✓ 0(1)   1(0) ◆ X + ✓ 1

 ◆ X + ✓ 0(1)

0(1) ◆ Y = ✓ 0(2)

1(0) ◆ Y = ✓ 0(1)

0 ◆

1(0) ◆

Hint: Start by setting X =  ◆ and Y = ✓ w(v)   v(−w) ◆ , and then find v,w,x,y such

that the above equations are satisfied.  (5 Marks)

There are also funny funny numbers.   These are all funny number 2 ⇥ 2 matrices of the

following form:

0   ◆

@

 ◆ 1C

 ◆ A(C)

c) Which funny funny number plays the role of the number 1? That is, which funny funny number I has the property that IF = FI = F for all funny funny numbers F . What is the determinant of a funny funny number.  Which funny funny numbers have an inverse?  (5 Marks)

d) Find two funny funny numbers A and B such that AB  BA.

What is all this good for? Well, believe it or not, but these funny and funny funny numbers are some of the most important objects in the whole of mathematics, just heavily disguised.

2    What’s next?  (25 Marks)

0, 1, 5, 19, 65, 211,....

are the first few elements of an infinite sequence of numbers that satisfies the following recurrence relation:

xn  = 5xn−1 − 6xn−2 ,

where x0  = 0,x1  = 1,x2  = 5,x3  = 19, and so on.

This means that every element of the sequence is equal to 5 times the previous element minus 6 times the element before that. So, 5 = 5 · 1 − 6 · 0, 19 = 5 · 5 − 6 · 1, etc. Using this recurrence relation over and over, we can generate as many of the elements of this sequence as we wish. Of course, calculating the millionth element in this way would take quite a while.

Wouldn’t it be nice if, instead, we could find a formula for xn , that is, express xn  as some explicit function in the variable n?

Using some linear algebra this is indeed possible (we did this for the Fibonacci sequence in the lectures). Here is what you have to do to find such a magical formula.

a) Find a 2 ⇥ 2 matrix M = ✓ c(a)   d(b) ◆ such that for all natural numbers n ≥ 2  ◆ = M  ◆ .

Consequently, for all natural number n ≥ 2

 ◆ = Mn−1  ✓ 0(1) ◆ .

This means that you can also use powers of the matrix M to calculate the elements of the sequence.x (5 Marks)

b) Diagonalize M, i.e., write M in the form M = NDN − 1 , where D is a diagonal matrix. To do this, first find the eigenvalues e and f of M, as well as two corresponding eigenvectors (it does not matter which). Then we know that the following matrices will do the trick:

D = ✓ 0(e)   f(0) ◆ ,

N = the 2 ⇥ 2 matrix the first and second columns of which are the eigenvectors of e and f , respectively.  (10 Marks)

c) Using b) derive a formula for xn .  (10 Marks)

3    Matrices of Graphs (50 marks, 6 marks for each of the seven questions plus two bonus points for really smart reasoning.)

1                              23

This is an example of a graph. It consists of four vertices (the four circles), labeled 1, 2, 3, and 4 and a number of edges connecting these vertices. Its adjacency matrix A is the

The number in the i’th row and j’th column is equal to the number of edges connecting vertex i with vertex j . For example, the 2s stand for the two edges connecting vertex 2 with 3 (or, equivalently, vertex 3 with vertex 2).

If n is any natural number, an n-step walk connecting two vertices is a journey from one of the vertices to the other that includes exactly n edges; here an edge counts as many times as you travel along it. In particular, this means that we could also call the matrix A ‘the matrix which summarizes the numbers of 1-step walks between the di↵erent vertices of the graph.’

One neat result in graph theory says that, in general, the number of n-step walks between the di↵erent vertices of the graph is summarized by the nth power of the matrix A. For example, if we are looking for the numbers of 3-step walks for our graph we’d be looking at

So, the 2 in the upper left corner of this matrix means that there are exactly two 3-step walks that start and end at vertex 1. These two walks consist of traveling clockwise and counterclockwise around the triangle visible in our graph.

In the following, let G be a graph in which two vertices are connected by at most one edge1

1 unlike our sample graph in which vertex 2 and vertex 3 are connected by two edges.

and no edge starts and ends at the same vertex. This means that the entries of its adjacency matrix are all either 0 or 1, and that all the entries on the main diagonal of A are 0.

a) The trace of a matrix, tr(A), is the sum of all the entries on the main diagonal. Explain why

• tr(A) = 0;

• tr(A2 ) = 2 ⇥ the number of edges of the graph;

• tr(A3 ) = 6 ⇥the number of triangles in the graph. Here a triangle in the graph consists of three vertices and three edges connecting any two of these vertices.

b) Our graph can be two- coloured if it is possible to colour its vertices with two colours such that any two vertices that are connected by an edge have di↵erent colours. Show that a graph cannot be two-coloured if the trace of any of the odd powers of A di↵ers from 0.

In fact, it turns out that the converse is also true, that is, if the traces of all odd powers of A are 0, then the graph can be two-coloured. You don’t need to show this.2

c) A graph is connected if it is possible to walk along the edges from any vertex to any other vertex inside the graph. If this is not possible the graph is called disconnected. The distance between two vertices inside a graph is the length of the shortest walk between them. The diameter of a graph is the maximum distance between two of its vertices.3  For example, our sample graph is connected and its diameter is 2.

Let P1  = A, P2  = A + A2 , P3  = A + A2 + A3  and in general

Pm  = A + A2 + A3 + A4 + ··· + Am .

How would you measure the distance between two given vertices and the diameter of a graph using the matrices Pm ? How could you decide, again using these matrices, whether or not a graph is connected or disconnected?

d) Here is an adjacency matrix of a mystery graph. Use the results in a), b) and c) to answer the following questions: How many triangles does this graph have? Is the graph connected?

2 On the other hand, you definitely get the bonus point if you manage to find a proof of this last fact.

3 For disconnected graphs the diameter is not defined. Similarly, it does not make sense to speak of the distance between vertices in di↵erent components of a disconnected graph.

What is its diameter? Is it two-colourable?

 1C

B(B) 1   0   0   1   0   0   1   0   C(C)

B(B) 0   1   1   0   0   0   0   1   C(C)

B(B) 1   0   0   0   0   1   1   0   C(C)

B(B) 0   1   0   0   1   0   0   1   C(C)

B 0   0   1   0   1   0   0   1   C

0   0   0   1   0   1   1   0

You should use  Mathematica for these calculations.   But just in case you cannot bring yourself to doing that you can also use online tools like the WIMS matrix calculator at https://tinyurl.com/55nvf2br to calculate powers of A, the matrices Pm , and in general analyze matrices to your heart’s content. Again, it is a good idea to prepare your matrix in a word processor and then cut and paste it into the calculator. This way you can use it over and over.

e) Note that the entries in all the rows and columns of this matrix add up to 3. What does this mean for the graph?  When you calculate the eigenvalues of this matrix (again using the online calculator) you will find that 3 is also among these eigenvectors.  Show that this is not a coincidence, i.e., show that if all the rows of a matrix add up to the same number k, then k is an eigenvalue of this matrix. Describe one possible eigenvector corresponding to this special eigenvalue.

f) Calculating the matrices

Pm  = A + A2 + A3 + A4 + ··· + Am

is “expensive” if m is a large number, when cost is measured by the numbers of calculations

necessary. If you replace the matrix A by a number a, this sum turns into a + a2 + a3 + a4 + ··· + am

and this sum is known to be equal to

a − am+1

1 − a   .

For example, check out “Geometric series” on Wikipedia to learn how this formula is derived. What would the corresponding formula for A + A2 + A3 + A4 + ··· + Am  look like and for which matrices A would it be valid? Would it be valid for the 8 ⇥ 8 matrix of our mystery graph?

What is all this good for?  Well, it’s all really beautiful mathematics.  But apart from that graphs are also very applicable. For example, any maze is really a graph with the junctions at which paths meet playing the part of the vertices and the paths themselves playing the