16.1 Properties of matrices

A matrix has $m$ rows and $n$ columns. For example, a $2\times 3$ matrix would look something like this

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 $\mathbb{R}^{m\times n}$ (we can also do the same for other sets, for example $\mathbb{N}^{m\times n}$ for an $m$ by $n$ matrix whose elements are all natural numbers).

We can also define a matrix using the notation

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

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).

For example, to add

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…

For all $m\times n$ matrices $A$ and $B$, there exists a value $X$ such that

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

Multiplying two matrices is a strange and at first unfamiliar thing. The fundamental principle is that when we multiply two $m\times n$ matrices $A$ and $B$, we obtain a new matrix, $C$, whose $j$th entry in the $i$th row is defined as

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)$).

• •
  ​

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

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

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

We can define $A$ as

That is, a diagonal line of $1$s and $0$ everywhere else. For example, for the dimension $2\times 2$, $I$ is

And for the $3\times 3$ case, it is

The same is true for higher dimensions.

Example

: The matrix $A$ is defined as

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

By considering $A$, $A^{2}$, $A^{3}$ and $A^{4}$, make a conjecture about $A^{n}$, and then prove this conjecture by induction.

Solution

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

When we multiply $A$ by $A$, we get that

$$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 $A$ again, we get that

$$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

	$\displaystyle 2(2\cdot 3+3\cdot 2)+3\cdot 2^{2}$	$\displaystyle=2^{2}\cdot 3+2^{2}\cdot 3+3\cdot 2^{2}$		(16.18)
		$\displaystyle=2^{2}\cdot 3+2^{2}\cdot 3+2^{2}\cdot 3$		(16.19)
		$\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 $A^{4}$ we get that

$$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

$\displaystyle 2(3\cdot 2^{2}\cdot 3)+3\cdot 2^{3}$

$\displaystyle=3\cdot 2^{3}\cdot 3+3\cdot 2^{3}$

$\displaystyle=4\cdot 2^{3}\cdot 3$

(16.22)

This implies that

$$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

$$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 $A^{n}$ is

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

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

We can also write the matrix $A^{n}$ as $AA^{n-1}$.

$$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.

$$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 $A^{n}$ we have computed here (in terms of $f(n-1)$) to the one we’d like to know (that of $f(n)$). This gives

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

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

	$\displaystyle f(n)$	$\displaystyle=2(2f(n-2)+3\cdot 2^{n-2})+3\cdot 2^{n-1}$		(16.29)
		$\displaystyle=2^{2}f(n-2)+3\cdot 2^{n-1}+3\cdot 2^{n-1}$		(16.30)
		$\displaystyle=2^{2}(2f(n-3)+3\cdot 2^{n-3})+3\cdot 2^{n-1}+3\cdot 2^{n-1}$		(16.31)
		$\displaystyle=2^{3}f(n-3)+3\cdot 2^{n-1}+3\cdot 2^{n-1}+3\cdot 2^{n-1}$		(16.32)
		$\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 ²² 2 Unfortunately, it’s not a great diagram (but I tried)..

The sum of each node $f(n)$ in the tree is $2f(n-1)+3\cdot 2^{n-1}$ - the $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 $n$ levels of the tree and at each level the nodes sum to $3\cdot 2^{n-1}$, and thus overall we have that $f(n)$ is equal to the sum of all the nodes, which is equal to $n\cdot 3\cdot 2^{n-1}$.

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

For the proof by induction, if we set

$$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 $A^{n}=P(n)$ for every natural number.

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

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

$$\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

$$\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 $k\cdot 2^{k}\cdot 3+3\cdot 2^{k}$ is equal to $2^{k}\cdot 3\cdot(k+1)$ we have that

$$\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 $2^{k}$ as $2^{(k+1)-1}$, and then we have

$$\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)$ is true for $n=1$ and $P(n)$ implies that $P(n+1)$ is true, $P(n)$ must hold for all $n$.