16.1 Properties of matrices

On the off-chance that someone other than me reads these, please don’t read this section in one go; it’s here for reference.

16.1.1 Introduction

A matrix has mm rows and nn columns. For example, a 2×32\times 3 matrix would look something like this

(012358)\begin{pmatrix}0&1&2\\ 3&5&8\end{pmatrix} (16.1)

Of course, the values in a matrix can be anything. If we want to denote a matrix having only real numbered elements, we can write this as m×n\mathbb{R}^{m\times n} (we can also do the same for other sets, for example m×n\mathbb{N}^{m\times n} for an mm by nn matrix whose elements are all natural numbers).

We can also define a matrix using the notation

(f(i,j))ij(f(i,j))_{ij} (16.2)

This means that the jjth column of the iith row is equal to f(i,j)f(i,j).

16.1.2 Adding matrices

Adding matrices is fairly straightforward - we just add all elements in the same position in the matrices we are adding (this does imply, however, that we can only add together matrices which are of the same size).

(A)ij+(B)ij=(A+B)ij(A)_{ij}+(B)_{ij}=(A+B)_{ij} (16.3)

For example, to add

(12512)+(3567)\begin{pmatrix}1&2\\ 5&12\end{pmatrix}+\begin{pmatrix}3&5\\ 6&7\end{pmatrix} (16.4)

We just add the first item of the first row of the first matrix with the first item of the first row of the second matrix and so on…

(12512)+(3567)=(471119)\begin{pmatrix}1&2\\ 5&12\end{pmatrix}+\begin{pmatrix}3&5\\ 6&7\end{pmatrix}=\begin{pmatrix}4&7\\ 11&19\end{pmatrix} (16.5)

16.1.3 Properties of matrix addition

For all m×nm\times n matrices AA and BB, there exists a value XX such that

A+X=BA+X=B (16.6)
Property 16.1.1

For all values of m,nm,n there exists an m×nm\times n matrix 0, such that all m×nm\times n matrices AA satisfy the property

A+0=0+AA+0=0+A (16.7)
Property 16.1.2

It is also the case that for any m×nm\times n matrix AA, there exists a matrix A-A, such that

A+(A)=0A+(-A)=0 (16.8)
Property 16.1.3

For all n×nn\times n matrices AA and BB, it is the case that

A+B=B+AA+B=B+A (16.9)

Together, all these properties mean that m×n\mathbb{R}^{m\times n} forms an Abelian Group under multiplication.

16.1.4 Matrix multiplication

Multiplying two matrices is a strange and at first unfamiliar thing. The fundamental principle is that when we multiply two m×nm\times n matrices AA and BB, we obtain a new matrix, CC, whose jjth entry in the iith row is defined as

Cij=0kjAikBkjC_{ij}=\sum_{0\leqq k\leqq j}A_{ik}B_{kj} (16.10)

16.1.5 Properties of matrix multiplication

Matrix multiplication has a number of useful properties, for example

  • It is associative; we can change the order in which we multiply several matrices together without changing the result (i.e. (AB)C=A(BC)(AB)C=A(BC)).

  • Matrix multiplication is distributive over matrix addition (i.e. we can factorise matrices, mathematically: A(B+C)=AB+ACA(B+C)=AB+AC).

Important: matrix multiplication is not commutative (i.e. ABBAAB\neq BA).

16.1.6 The identity matrix

In the same way that we have the number 11 which is an \sayidentity (or \sayneutral) element for multiplication in the real numbers 11 1 And also the natural numbers, integers, rational and irrational numbers., we have an identity matrix. This is usually denoted with the letter II and by definition satisfies the property that for any m×mm\times m matrix and any m×mm\times m matrix AA, it is the case that

AI=I=IAAI=I=IA (16.11)

We can define AA as

(A)ij={1 if i=j0 otherwise (A)_{ij}=\begin{cases}1\text{ if }i=j\\ 0\text{ otherwise }\end{cases} (16.12)

That is, a diagonal line of 11s and 0 everywhere else. For example, for the dimension 2×22\times 2, II is

(1001)\begin{pmatrix}1&0\\ 0&1\end{pmatrix} (16.13)

And for the 3×33\times 3 case, it is

(100010001)\begin{pmatrix}1&0&0\\ 0&1&0\\ 0&0&1\end{pmatrix} (16.14)

The same is true for higher dimensions.

16.1.7 Raising matrices to powers


: The matrix AA is defined as

A:=(2302)A:=\begin{pmatrix}2&3\\ 0&2\end{pmatrix} (16.15)

By considering AA, A2A^{2}, A3A^{3} and A4A^{4}, make a conjecture about AnA^{n}, and then prove this conjecture by induction.


: Although it’s tempting to reach for one’s calculator to compute AA, A2A^{2}, A3A^{3} and A4A^{4}, it makes things harder.

When we multiply AA by AA, we get that

A2=(2223+32022)A^{2}=\begin{pmatrix}2^{2}&2\cdot 3+3\cdot 2\\ 0&2^{2}\end{pmatrix} (16.16)

If we then multiply this by AA again, we get that

A3=(232(23+32)+322023)A^{3}=\begin{pmatrix}2^{3}&2(2\cdot 3+3\cdot 2)+3\cdot 2^{2}\\ 0&2^{3}\end{pmatrix} (16.17)

We can multiply out the bracket and get that

2(23+32)+322\displaystyle 2(2\cdot 3+3\cdot 2)+3\cdot 2^{2} =223+223+322\displaystyle=2^{2}\cdot 3+2^{2}\cdot 3+3\cdot 2^{2} (16.18)
=223+223+223\displaystyle=2^{2}\cdot 3+2^{2}\cdot 3+2^{2}\cdot 3 (16.19)
=3223\displaystyle=3\cdot 2^{2}\cdot 3 (16.20)

Simplifying here is a bad idea, as we’re looking for patterns, and these are easier to spot when we have more information to work with (which we do when we think about the factors of our numbers.)

Multiplying to find A4A^{4} we get that

A4=(242(3223)+323024)A^{4}=\begin{pmatrix}2^{4}&2(3\cdot 2^{2}\cdot 3)+3\cdot 2^{3}\\ 0&2^{4}\end{pmatrix} (16.21)

We can simplify this a bit, because

2(3223)+323\displaystyle 2(3\cdot 2^{2}\cdot 3)+3\cdot 2^{3} =3233+323\displaystyle=3\cdot 2^{3}\cdot 3+3\cdot 2^{3} =4233\displaystyle=4\cdot 2^{3}\cdot 3 (16.22)

This implies that

A4=(244233024)A^{4}=\begin{pmatrix}2^{4}&4\cdot 2^{3}\cdot 3\\ 0&2^{4}\end{pmatrix} (16.23)

Looking at these four matrices, the general shape is something like

An=(2nn2n1302n)A^{n}=\begin{pmatrix}2^{n}&n\cdot 2^{n-1}\cdot 3\\ 0&2^{n}\end{pmatrix} (16.24)

There’s another way of doing this, but the maths behind it isn’t on the A Level specification. It’s the way I originally did it.

From the initial multiplication, we can see that the general shape of AnA^{n} is

(2n?02n)\begin{pmatrix}2^{n}&?\\ 0&2^{n}\end{pmatrix} (16.25)

Here the ?? denotes the confusion about what A1,2A_{1,2} is. In terms of notation, it’s slightly more handy to call ?? something more like f(n)f(n).

We can also write the matrix AnA^{n} as AAn1AA^{n-1}.

An=(2302)(2n1f(n1)02n1)A^{n}=\begin{pmatrix}2&3\\ 0&2\end{pmatrix}\begin{pmatrix}2^{n-1}&f(n-1)\\ 0&2^{n-1}\end{pmatrix} (16.26)

We can apply the standard rules of matrix multiplication to the above.

An=(2n2f(n1)+32n102n)A^{n}=\begin{pmatrix}2^{n}&2f(n-1)+3\cdot 2^{n-1}\\ 0&2^{n}\end{pmatrix} (16.27)

We can compare the value of AnA^{n} we have computed here (in terms of f(n1)f(n-1)) to the one we’d like to know (that of f(n)f(n)). This gives

f(n)=2f(n1)+32n1f(n)=2f(n-1)+3\cdot 2^{n-1} (16.28)

We also know that f(1)=3f(1)=3. To find a closed-form expression for f(n)f(n), we can just keep substituting:

f(n)\displaystyle f(n) =2(2f(n2)+32n2)+32n1\displaystyle=2(2f(n-2)+3\cdot 2^{n-2})+3\cdot 2^{n-1} (16.29)
=22f(n2)+32n1+32n1\displaystyle=2^{2}f(n-2)+3\cdot 2^{n-1}+3\cdot 2^{n-1} (16.30)
=22(2f(n3)+32n3)+32n1+32n1\displaystyle=2^{2}(2f(n-3)+3\cdot 2^{n-3})+3\cdot 2^{n-1}+3\cdot 2^{n-1} (16.31)
=23f(n3)+32n1+32n1+32n1\displaystyle=2^{3}f(n-3)+3\cdot 2^{n-1}+3\cdot 2^{n-1}+3\cdot 2^{n-1} (16.32)
=n32n1\displaystyle=n\cdot 3\cdot 2^{n-1} (16.33)

The last step isn’t necessarily immediately obvious (doing the expansion by hand might make it easier to understand). The other way to think about this is by using one of the helpful heuristics looked at in the heuristics section, in this case \saywherever possible, draw a diagram 22 2 Unfortunately, it’s not a great diagram (but I tried)..

32n13\cdot 2^{n-1}32n23\cdot 2^{n-2}32n33\cdot 2^{n-3}......32n33\cdot 2^{n-3}......32n23\cdot 2^{n-2}32n33\cdot 2^{n-3}......32n33\cdot 2^{n-3}......

The sum of each node f(n)f(n) in the tree is 2f(n1)+32n12f(n-1)+3\cdot 2^{n-1} - the 2f(n1)2f(n-1)s are drawn as children of the parent node. We want to find the sum of all the nodes in the tree. To do this, note that we have nn levels of the tree and at each level the nodes sum to 32n13\cdot 2^{n-1}, and thus overall we have that f(n)f(n) is equal to the sum of all the nodes, which is equal to n32n1n\cdot 3\cdot 2^{n-1}.

It’s all downhill (in difficulty) from here!

For the proof by induction, if we set

P(n)=(2nn2n1302n)P(n)=\begin{pmatrix}2^{n}&n\cdot 2^{n-1}\cdot 3\\ 0&2^{n}\end{pmatrix} (16.34)

then we want to show that An=P(n)A^{n}=P(n) for every natural number.

We start with the basis case: as A1=AA^{1}=A, it is clear that A1=P(1)A^{1}=P(1).

For the inductive step, we assume that P(k)=AkP(k)=A^{k}, and then we consider P(k+1)P(k+1), which is equal to A1AkA^{1}A^{k}. To this expression, we can now apply the inductive hypothesis (always be looking at P(k+1)P(k+1) to see where P(k)P(k) has been hidden!) and thus this expression is equal to AP(k)AP(k). We can then carry out the multiplication

(2302)(2kk2k1302k)=(22k2(k2k13)+32k022k)\begin{pmatrix}2&3\\ 0&2\end{pmatrix}\begin{pmatrix}2^{k}&k\cdot 2^{k-1}\cdot 3\\ 0&2^{k}\end{pmatrix}=\begin{pmatrix}2\cdot 2^{k}&2(k\cdot 2^{k-1}\cdot 3)+3% \cdot 2^{k}\\ 0&2\cdot 2^{k}\end{pmatrix} (16.35)

This can then be rewritten as

(2k+1k2k3+32k02k+1)\begin{pmatrix}2^{k+1}&k\cdot 2^{k}\cdot 3+3\cdot 2^{k}\\ 0&2^{k+1}\end{pmatrix} (16.36)

and as k2k3+32kk\cdot 2^{k}\cdot 3+3\cdot 2^{k} is equal to 2k3(k+1)2^{k}\cdot 3\cdot(k+1) we have that

(2k+12k3(k+1)02k+1)\begin{pmatrix}2^{k+1}&2^{k}\cdot 3\cdot(k+1)\\ 0&2^{k+1}\end{pmatrix} (16.37)

The final step is to rewrite the 2k2^{k} as 2(k+1)12^{(k+1)-1}, and then we have

(2k+1(k+1)2(k+1)1302k+1)\begin{pmatrix}2^{k+1}&(k+1)\cdot 2^{(k+1)-1}\cdot 3\\ 0&2^{k+1}\end{pmatrix} (16.38)

Thus as P(n)P(n) is true for n=1n=1 and P(n)P(n) implies that P(n+1)P(n+1) is true, P(n)P(n) must hold for all nn.