Find the power of the matrix.

Question

Let $A = \left( {\begin{array}{*{20}{c}} 0&1&1\\ 1&0&1\\ 1&1&0 \end{array}} \right)$. I want to find $A^k,$ where $k \in N$. So far I calculated $A^2, A^3, A^4,...$ but I can not see the general formula for $A^k$. Here are $A^2, A^3, A^4, A^5$.

Not sure if this leads to anything but I found the general formula for $B^k$, where $B = \left( {\begin{array}{*{20}{c}} 1&1&1\\ 1&1&1\\ 1&1&1 \end{array}} \right)$. ${B^k} = \left( {\begin{array}{*{20}{c}} {{3^{k - 1}}}&{{3^{k - 1}}}&{{3^{k - 1}}}\\ {{3^{k - 1}}}&{{3^{k - 1}}}&{{3^{k - 1}}}\\ {{3^{k - 1}}}&{{3^{k - 1}}}&{{3^{k - 1}}} \end{array}} \right)$

Thanks in advance.

Answer 1

Note that you get $$A^2=A+2I$$

Therefore $A^n$ is a linear combination of $A$ and $I\ $, i.e. $$ A^n=a_nA+i_nI$$

You get $A^{n+1}=a_nA^2+i_nA=a_n(A+2I)+i_nA=(a_n+i_n)A+2a_nI$

The system to solve is $\begin{cases}a_{n+1}=a_n+i_n\\i_{n+1}=2a_n\end{cases}\ $ and reporting for $a_{n+2}$ gives $\begin{cases}a_{n+2}=a_{n+1}+2a_n\\ a_0=0\\ a_1=1\end{cases}$

This solves to $a_n=\alpha\,2^n+\beta\,(-1)^n$ and initial conditions give $\ \alpha=-\beta=\frac 13$

Answer 2

Given matrix is real symmetric and hence diagonalisable. Hence $A=PDP^{-1}$. Thus $A^n$=$PD^nP^{-1}$ where P is the matrix of eigen vectors. D is diagonal and hence its powers are simply the powers of the eigenvalues which are $2,-1,-1$.

Answer 3

In general it is easy to compute a power of a matrix in it's jordan form, and even easier to compute it if the matrix is diagonalizable. This is because of the following claim:

Claim: given two matrices $A,B$ of size $n\times n$ and a nonsingular matrix $P$ such that $A=PBP^{-1}$, then $A^k=PB^kP^{-1}$ for all $k\in\mathbb{N}$.

We will prove this claim by induction

Induction base: for $k=1$ it is given that $A=PBP^{-1}$

Induction step: let's assume the claim is true for $k$, we know that $A^{k+1}=A\cdot A^k$, now by our induction hypothesis we know that $A^k=PB^kP^{-1}$ so $A^{k+1}=A\cdot A^k=A\cdot PB^kP^{-1}=PBP^{-1}\cdot PB^kP^{-1}=PB^{k+1}P^{-1}$

In your case notice that

$$ A= \begin{pmatrix} 0 & 1 & 1\\ 1 & 0 & 1\\ 0 & 1 & 1 \end{pmatrix} = \begin{pmatrix} -1 & -1 & 1\\ 0 & 1 & 1\\ 1 & 0 & 1 \end{pmatrix} \cdot \begin{pmatrix} -1 & 0 & 0\\ 0 & -1 & 0\\ 0 & 0 & 2 \end{pmatrix} \cdot \begin{pmatrix} -1 & -1 & 1\\ 0 & 1 & 1\\ 1 & 0 & 1 \end{pmatrix}^{-1} $$

So from our claim it follows that

$$ \begin{align} A^k=& \begin{pmatrix} -1 & -1 & 1\\ 0 & 1 & 1\\ 1 & 0 & 1 \end{pmatrix} \begin{pmatrix} -1 & 0 & 0\\ 0 & -1 & 0\\ 0 & 0 & 2 \end{pmatrix}^k \begin{pmatrix} -1 & -1 & 1\\ 0 & 1 & 1\\ 1 & 0 & 1 \end{pmatrix}^{-1}=\\ \\ =& \begin{pmatrix} -1 & -1 & 1\\ 0 & 1 & 1\\ 1 & 0 & 1 \end{pmatrix} \begin{pmatrix} (-1)^k & 0 & 0\\ 0 & (-1)^k & 0\\ 0 & 0 & 2^k \end{pmatrix} \begin{pmatrix} -1 & -1 & 1\\ 0 & 1 & 1\\ 1 & 0 & 1 \end{pmatrix}^{-1}=\\ \\ =&\frac{1}{3}\cdot \begin{pmatrix} 2\cdot(-1)^k+2^k & (-1)^{k+1}+2^K & (-1)^{k+1}+2^k\\ (-1)^{k+1}+2^k & 2\cdot(-1)^k+2^k & (-1)^{k+1}+2^k\\ (-1)^{k+1}+2^k & (-1)^{k+1}+2^k & 2\cdot(-1)^k+2^k \end{pmatrix} \end{align} $$

If my calculations are correct. But what if the matrix was not diagonalizable? Well, in that case we can find it's jordan form. Let's see how it would help. First of all we will calculate the powers of a Jordan block $N$ with zeroes on the diagonal, of size $n\times n$. This matrix uphold $(N)_{ij}=\delta_{i+1,j}$, so notice that $(N^2)_{ij}=\sum_{k=1}^n\delta_{i+1,k}\delta_{k+1,j}=\delta_{i+2,j}$. This observation will lead us to the next claim

Cliam: $(N^m)_{ij}=\delta_{i+m,j}$ for $m\in\mathbb{N}$

And agin we can prove this by induction

Induction base: for $m=1$ we saw alredy.

Induction step: let's asuume that the claim is true for $m$, so $(N^{m+1})_{ij}=(N\cdot N^m)_{ij}=\sum_{k=1}^n \delta_{i+1,k}\delta_{k+m,j}=\delta_{k+m+1,j}$

To clarify this property, this are the forms of the matrix $N$ and $N^2$ $$ N=\begin{pmatrix}0 & 1 & 0 & \cdots & 0\\ 0 & \ddots & \ddots & \ddots & \vdots\\ \vdots & \ddots & \ddots & \ddots & 0\\ \vdots & \ddots & \ddots & \ddots & 1\\ 0 & \cdots & \cdots & 0 & 0 \end{pmatrix},\; N^{2}=\begin{pmatrix}0 & 0 & 1 & \cdots & 0\\ 0 & \ddots & \ddots & \ddots & \vdots\\ \vdots & \ddots & \ddots & \ddots & 1\\ \vdots & \ddots & \ddots & \ddots & 0\\ 0 & \cdots & \cdots & 0 & 0 \end{pmatrix} $$ And in general each power take the diagonal of one's one diagonal higher until the nth power, where we will get $N^n=0$.

Now let's assume that $A$ is a jordan block of size $n\times n$, for example

$$ A=\begin{pmatrix}\mu & 1 & 0 & \cdots & 0\\ 0 & \ddots & \ddots & \ddots & \vdots\\ \vdots & \ddots & \ddots & \ddots & 0\\ \vdots & \ddots & \ddots & \ddots & 1\\ 0 & \cdots & \cdots & 0 & \mu \end{pmatrix} $$

so we could write $A=\mu\cdot I+N$ for $N$ the matrix from the last paragraph and $I$ the unit matrix.

From the binomial theorem we would get $$ A^m=(\mu\cdot I+N)^m=\sum_{k=0}^m\binom{m}{k}N^m\cdot \mu^{m-k} $$
and because $N^n=0$ we could write $$ A^m=\sum_{k=0}^m\binom{m}{k}N^m\cdot \mu^{m-k}=\sum_{k=0}^{\max(m,n-1)}\binom{m}{k}N^m\cdot \mu^{m-k} $$

Which is of the form

$$ \begin{pmatrix}\mu^{k} & k\mu^{k-1} & \binom{k}{2}\mu^{k-2} & \ddots\\ 0 & \mu^{k} & k\mu^{k-1} & \ddots & \ddots\\ \vdots & \ddots & \ddots & \ddots & \binom{k}{2}\mu^{k-2}\\ \vdots & & \ddots & \ddots & k\mu^{k-1}\\ 0 & \cdots & \cdots & 0 & \mu^{k} \end{pmatrix} $$

So we only need to calculate the first $n$ powers in this situation.

Another Observation that we could make, is that if $\mu\neq0$ then $A$ is invertible, and we could calculate it's invers with the following formula:

$$ A^{-1}=(\mu I+N)^{-1}=\mu^{-1}(I+\mu^{-1}N)^{-1} $$

And with the taylor series $(1+x)^{-1}=\sum_{i=0}^\infty(-1)^ix^i$ we will conclude that

$$ A^{-1}=\mu^{-1}(I+\mu^{-1}N)^{-1}=\sum_{i=0}^{\infty}(-1)^{i}\mu^{-i-1}N^{i}=\sum_{i=0}^{n-1}(-1)^{i}\mu^{-i-1}N^{i} $$

It's also helps computing exponent of matrices

$$ \begin{align} e^{x}&=\sum_{m=0}^{\infty}\frac{x^{m}}{m!}\Rightarrow e^{A}=\sum_{m=0}^{\infty}\frac{A^{m}}{m!}=\sum_{m=0}^{\infty}\frac{(\mu I+N)^{m}}{m!}=\sum_{m=0}^{\infty}\frac{1}{m!}\sum_{k=0}^{m}\binom{m}{k}\mu^{m-k}N^{k}=\\ &=\sum_{k=0}^{\infty}\left(\sum_{m=0}^{\infty}\frac{1}{(m+k)!}\binom{m+k}{k}\mu^{m}\right)N^{k}=\sum_{k=0}^{\infty}\left(\sum_{m=0}^{\infty}\frac{1}{(k!)(m)!}\mu^{m}\right)N^{k}=\sum_{k=0}^{n-1}\frac{e^{\mu}}{k!}N^{k}= \end{align} $$

So, in our case

$$ e^A= e^{\mu}\begin{pmatrix}1 & 1 & \frac{1}{2!} & \cdots & \frac{1}{n!}\\ 0 & \ddots & \ddots & \ddots & \vdots\\ \vdots & \ddots & \ddots & \ddots & \frac{1}{2!}\\ \vdots & \ddots & \ddots & \ddots & 1\\ 0 & \cdots & \cdots & 0 & 1 \end{pmatrix} $$

If now $A$ is a general jordan matrix, we could write

$$ A=\begin{pmatrix}A_{1} & 0 & \cdots & 0\\ 0 & A_{2} & \ddots & \vdots\\ \vdots & \ddots & \ddots & 0\\ 0 & \cdots & 0 & A_{\ell} \end{pmatrix} $$

Where $A_i$ are jordan blocks. So it follows that

$$ \begin{align} A^m&=\begin{pmatrix}A_{1}^m & 0 & \cdots & 0\\ 0 & A_{2}^m & \ddots & \vdots\\ \vdots & \ddots & \ddots & 0\\ 0 & \cdots & 0 & A_{\ell}^m \end{pmatrix},\;A^{-1}= \begin{pmatrix}A_{1}^{-1} & 0 & \cdots & 0\\ 0 & A_{2}^{-1} & \ddots & \vdots\\ \vdots & \ddots & \ddots & 0\\ 0 & \cdots & 0 & A_{\ell}^{-1} \end{pmatrix},\\ &e^A= \begin{pmatrix}e^{A_{1}} & 0 & \cdots & 0\\ 0 & e^{A_{2}} & \ddots & \vdots\\ \vdots & \ddots & \ddots & 0\\ 0 & \cdots & 0 & e^{A_{\ell}} \end{pmatrix} \end{align} $$

Of course the case of $A^{-1}$ is only valid if $A$ is invertible

And for a general matrix $B$, we know that we could find it's jordan form over the complex numbers. Let's assume that $B=PAP^{-1}$ were $A$ is a jordan matrix, then we saw that $B^m=PA^kP^{-1}$ and also it happens to be that $B^{-1}=PA^{-1}P^{-1}$ and $e^A=Pe^AP^{-1}$.

Let's do an example. Given $$ A=\begin{pmatrix}2 & 1 & 2 \\ -1 & 0 & -2 \\ 0 & 0 & 3 \end{pmatrix} $$ We will compute $A^8$. Observe that $A=PJP^{-1}$ where $$ P=\begin{pmatrix}1 & 1 & 2 \\ -1 & 0 & 0 \\ 0 & 0 & 1 \end{pmatrix},\; J=\begin{pmatrix}1 & 1 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 3 \end{pmatrix}= \begin{pmatrix}J_2(1) & \\ 0 & 3 \end{pmatrix} $$

Where $J_n(m)$ is a jordan block of size $n\times n$ with $m$ on its diagonal. As we computed before, we know that

$$ \begin{align} J_2(1)^8=&(J_2(0)+I)^8=\sum_{i=0}^8\binom{8}{i}j_2(0)^i=\sum_{i=0}^1\binom{8}{i}J_2(0)^i=I+8\cdot J_2(0)=\begin{pmatrix} 1 & 8\\ 0 & 1 \end{pmatrix} \end{align} $$

Hence

$$ J=\begin{pmatrix} 1 & 8 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 3^8 \end{pmatrix} $$

So in conclusion,

$$ \begin{align} A^8=&(PJP^{-1})^8= \begin{pmatrix} 1 & 1 & 2 \\ -1 & 0 & 0 \\ 0 & 0 & 1 \end{pmatrix} \begin{pmatrix} 1 & 8 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 3^8 \end{pmatrix} \begin{pmatrix} 0 & -1 & 0 \\ 1 & 1 & -2 \\ 0 & 0 & 1 \end{pmatrix}=\\ \\ =& \begin{pmatrix} 1 & 9 & 2\cdot3^8 \\ -1 & -8 & 0 \\ 0 & 0 & 3^8 \end{pmatrix} \begin{pmatrix} 0 & -1 & 0 \\ 1 & 1 & -2 \\ 0 & 0 & 1 \end{pmatrix}=\\ \\ =&\begin{pmatrix} 9 & 8 & 2\cdot 3^8-18 \\ -8 & -7 & 16 \\ 0 & 0 & 3^8 \end{pmatrix}= \begin{pmatrix} 9 & 8 & 13104 \\ -8 & -7 & 16\\ 0 & 0 & 6561 \end{pmatrix} \end{align} $$

And for $k\geq 1$ in the same way we would get

$$ A^k=(PJP^{-1})^k= \begin{pmatrix} 1 & 1 & 2 \\ -1 & 0 & 0 \\ 0 & 0 & 1 \end{pmatrix} \begin{pmatrix} 1 & k & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 3^k \end{pmatrix} \begin{pmatrix} 0 & -1 & 0 \\ 1 & 1 & -2 \\ 0 & 0 & 1 \end{pmatrix} $$

Answer 4

Hint. From the first few examples you gave, it is easy to conjecture that $A^n = a_nB+(-1)^nI$ for some sequence $(a_n)$ that starts off $1,1,3,5,11,\dots$. If this is the case, then we would have $$a_{n+1}B+(-1)^{n+1}I=A(a_nB+(-1)^nI)=a_nAB+(-1)^nA$$ for all $n$. Rearranging, and substituting the relationship $A+I=B$, this is equivalent to $$(a_{n+1}+a_n+(-1)^{n+1})B=a_nB^2.$$Now it is easy to see that $a_{n+1}+a_n+(-1)^{n+1}=3a_n$, so we have a recurrence for $(a_n)$ which can be solved by standard methods.