A calculus of the absurd

17.2 Matrices

17.2.1 Matrix multiplication

Example: given that

\begin{equation} A = \begin{pmatrix} 2 & 3 \\ 0 & 2 \end {pmatrix} \end{equation}

consider \(A\), \(A^2\), \(A^3\) and \(A^4\) to 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

\begin{equation} A^2 = \begin{pmatrix} 2^2 & 2\cdot 3 + 3\cdot 2 \\ 0 & 2^2 \end {pmatrix} \end{equation}

If we then multiply this by \(A\) again, we get that

\begin{equation} A^3 = \begin{pmatrix} 2^3 & 2(2\cdot 3 + 3\cdot 2) + 3\cdot 2^2 \\ 0 & 2^3 \end {pmatrix} \end{equation}

We can multiply out the bracket and get that

\begin{align} 2(2\cdot 3 + 3\cdot 2) + 3\cdot 2^2 &= 2^2\cdot 3 + 2^2\cdot 3 + 3\cdot 2^2 \\ &= 2^2\cdot 3 + 2^2\cdot 3 + 2^2\cdot 3 \\ &= 3\cdot 2^2\cdot 3 \end{align}

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

\begin{equation} A^4 = \begin{pmatrix} 2^4 & 2(3\cdot 2^2\cdot 3) + 3\cdot 2^3 \\ 0 & 2^4 \end {pmatrix} \end{equation}

We can simplify this a bit, because

\begin{align} 2(3\cdot 2^2\cdot 3) + 3\cdot 2^3 &= 3\cdot 2^3\cdot 3 + 3\cdot 2^3 &= 4\cdot 2^3\cdot 3 \end{align}

This implies that

\begin{equation} A^4 = \begin{pmatrix} 2^4 & 4\cdot 2^3\cdot 3 \\ 0 & 2^4 \end {pmatrix} \end{equation}

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

\begin{equation} A^n = \begin{pmatrix} 2^n & n\cdot 2^{n-1}\cdot 3 \\ 0 & 2^n \end {pmatrix} \end{equation}

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{equation} \begin{pmatrix} 2^n & ? \\ 0 & 2^n \end {pmatrix} \end{equation}

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 \(A A^{n-1}\).

\begin{equation} A^n = \begin{pmatrix} 2 & 3 \\ 0 & 2 \end {pmatrix} \begin{pmatrix} 2^{n-1} & f(n-1) \\ 0 & 2^{n-1} \end {pmatrix} \end{equation}

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

\begin{equation} A^n = \begin{pmatrix} 2^{n} & 2f(n-1) + 3\cdot 2^{n-1} \\ 0 & 2^{n} \end {pmatrix} \end{equation}

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

\begin{equation} f(n) = 2f(n-1) + 3\cdot 2^{n-1} \end{equation}

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

\begin{align} f(n) &= 2(2f(n-2)+3\cdot 2^{n-2}) + 3\cdot 2^{n-1} \\ &= 2^2f(n-2) + 3\cdot 2^{n-1} + 3\cdot 2^{n-1} \\ &= 2^2(2f(n-3) + 3\cdot 2^{n-3}) + 3\cdot 2^{n-1} + 3\cdot 2^{n-1} \\ &= 2^3f(n-3) + 3\cdot 2^{n-1} + 3\cdot 2^{n-1} + 3\cdot 2^{n-1} \\ &= n \cdot 3 \cdot 2^{n-1} \end{align}

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 “wherever possible, draw a diagram” 108108 Unfortunately, it’s not a great diagram (but I tried)..

(-tikz- diagram)

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

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

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 \(A P(k)\). We can then carry out the multiplication

\begin{equation} \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} \end{equation}

This can then be rewritten as

\begin{equation} \begin{pmatrix} 2^{k+1} & k\cdot 2^{k}\cdot 3 + 3\cdot 2^{k} \\ 0 & 2^{k+1} \end {pmatrix} \end{equation}

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{equation} \begin{pmatrix} 2^{k+1} & 2^{k}\cdot 3\cdot (k+1) \\ 0 & 2^{k+1} \end {pmatrix} \end{equation}

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

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

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