Result of matrix $A^{2016}$

Question

I want to find the result of $A^{2016}$ but I cannot find any pattern except for the zeros in the middle row and column.

$$A=\begin{bmatrix}1 & 0 & {-2}\\0 & 0 & {0}\\3 & 0 & {-4}\end{bmatrix}$$

Answer 1

Note that $A$ has characteristic polynomial $p(\lambda)=-\lambda^3-3\lambda^2-2\lambda$, which yields $\lambda_1=-2$, $\lambda_2=-1$ and $\lambda_3=0$. Since each eigenvalue is different and there are 3, then $A$ is diagonalizable.

It is easy to see that $A=PDP^{-1}$ with

$P=\left(\begin{array}{ccc}2&1&0\\0&0&1\\3&1&0\end{array}\right)$, $P^{-1}=\left(\begin{array}{ccc}-1&0&1\\3&0&-2\\0&1&0\end{array}\right) $ and $D=\left(\begin{array}{ccc}-2&0&0\\0&-1&0\\0&0&0\end{array}\right)$

Now:

$\begin{eqnarray}A^m&=&(PDP^{-1})^m=(PDP^{-1})(PDP^{-1})...(PDP^{-1})\\&=&PD(P^{-1}P)D(P^{-1}P)D...(P^{-1}P)DP^{-1}\\ &=&PDD...DP^{-1}\\ &=&PD^{m}P^{-1}\end{eqnarray}$

For $m=2016$ we have

$\begin{eqnarray} A^{2016}&=&PD^{2016}P^{-1}\\ &=&\left(\begin{array}{ccc}2&1&0\\0&0&1\\3&1&0\end{array}\right)\left(\begin{array}{ccc}-2&0&0\\0&-1&0\\0&0&0\end{array}\right)^{2016}\left(\begin{array}{ccc}-1&0&1\\3&0&-2\\0&1&0\end{array}\right)\\ &=&\left(\begin{array}{ccc}2&1&0\\0&0&1\\3&1&0\end{array}\right)\left(\begin{array}{ccc}(-2)^{2016}&0&0\\0&(-1)^{2016}&0\\0&0&0\end{array}\right)\left(\begin{array}{ccc}-1&0&1\\3&0&-2\\0&1&0\end{array}\right)\\ &=&\left(\begin{array}{ccc}2&1&0\\0&0&1\\3&1&0\end{array}\right)\left(\begin{array}{ccc}2^{2016}&0&0\\0&1&0\\0&0&0\end{array}\right)\left(\begin{array}{ccc}-1&0&1\\3&0&-2\\0&1&0\end{array}\right)\\ &=&\left(\begin{array}{ccc}-2^{2017}+3&0&2^{2017}-2\\0&0&0\\-3\cdot2^{2016}+3&0&3\cdot2^{2016}-2\end{array}\right) \end{eqnarray}$

Answer 2

The matrix is permutationally similar to $\begin{bmatrix}1&{-2}&0\\ 3&-4&0\\ 0&0&0\end{bmatrix}$. So, in essence, you only need to find the 2016-th power of $B=\begin{bmatrix}1&{-2}\\ 3&-4\end{bmatrix}$. Now, that how to find the power of a $2\times2$ matrix $B$ has been discussed many times on this site. Among all solution methods, the easiest one (that involves the least amount of computations) is this:

1. Calculate the characteristic polynomial of $B$. In your case it's $p(x)=x^3-3x+2$. So, the two eigenvalues of $B$ are $-2$ and $-1$.
2. It follows that if $r(x)$ is the remainder you obtain by dividing $x^{2016}$ by $p(x)$, that is, if $$x^{2016}=p(x)q(x)+r(x)\tag{2}$$ in the division, then $B^{2016}=r(B)$ because Cayley-Hamilton theorem says that $p(B)=0$.
3. In your case, as $\deg p=2$, the remainder $r$ at most has degree 1. Let $r(x)=ax+b$. To find $a$ and $b$, simply substitute the eigenvalues of $B$ for $x$ into $(2)$ and solve the resulting system of equations. (You don't need to know $q$ because $p(x)$ is always zero when $x$ is an eigenvalue.) In your case, if you put $x=-1$ and $x=-2$ respectively into $(2)$, you get $1=-a+b$ and $2^{2016}=-2a+b$. Hence $a=1-2^{2016}$ and $b=2-2^{2016}$. Consequently $$ B^{2016}=r(B)=aB+bI=\begin{bmatrix}3-2^{2017}&-2+2^{2017}\\ 3(1-2^{2016})&-2+3(2^{2016})\end{bmatrix}. $$

Answer 3

You can ignore the middle row and column, nothing happens there. You just need $$\begin{bmatrix}1 &-2 \\ 3 &-4\end{bmatrix}$$ This is very easily diagonalized (because you only need to compute the trace and determinant). You can write $A=PDP^{-1}$ and then $A^{n}=PD^n P^{-1}$. Then put the zeroes back in.

Another way that sometimes works well for small matrices or those with nice symmetry properties, is to split it into parts that are easy to multiply and find patterns (identities, outer products of two vectors, nilpotent matrices, in 2D the Pauli spin matrices...). Sometimes, SVD decomposition is obvious to see with naked eye (not in this case). How I'd approach this one?

$$\begin{bmatrix}1 &-2 \\3 &-4\end{bmatrix}=\begin{bmatrix}3 & -2 \\ 3 & -2 \end{bmatrix}-2 I=a^T b - 2I$$ where $a=(1,1)$ and $b=(3,-2)$. Now use binomial expansion: $$(a^Tb-2I)^n=\sum_{k=0}^n {n \choose k} (a^T b)^k (-2)^{n-k}=(-2)^n I+a^Tb\left[\sum_{k=1}^n {n \choose k} (a\cdot b)^{k-1} (-2)^{n-k}\right]$$ Here, I carried the zeroth term out (because it has no $a$ and $b$) and regrouped the rest so express them as dot products this way: $(a^Tb)(a^Tb)\cdots(a^Tb)=a^T(ba^T)(ba^T)\cdots b$.

Now we put in the numbers: $a\cdot b = 1$, and see that what's left of the binomial expansion is just $(1-2)^n$ without the leading term. $$A^n=(-2)^n I+a^Tb\sum_{k=1}^n {n\choose k}(-2)^{n-k}=(-2)^n I + ((-1)^n-(-2)^n)a^T b$$ $$=(-1)^n\begin{bmatrix}2^n+3(1-2^n) & -2(1-2^n) \\ 3(1-2^n) & 2^n-2(1-2^n) \end{bmatrix}$$ $$=(-1)^n\begin{bmatrix}-2^{n+1}+3 & 2^{n+1}-2 \\ -3\cdot 2^n+ 3 & -2^n-2 \end{bmatrix}$$