Generalized Method to find nth power of matrix in $P^n = 5I - 8P$

Question

Question: Let $I$ be an identity matrix of order $2 \times 2$ and $P = \begin{bmatrix} 2 & -1 \\ 5 & -3 \\ \end{bmatrix}$. Then the value of $n ∈ N$ for which $P^n = 5I - 8P$ is equal to _______.

Answer: 6

Question Source: JEE Mains $18^{th}$ March Shift-2 2021

By characteristic Equation: $P^2-(\operatorname {Tr}(P))P+(\det (P))I=0$ we can find $n=6$ by hit and trial. i.e. multiplying equation by P gives

$P^3=(\operatorname {Tr}(P))P^2-(\det (P))P = (\operatorname {Tr}(P))[(\operatorname {Tr}(P))P+(\det(P))I]$

And going on solving for $P^6$. But is there a generalized method because it can't be done for high values of $n$ (eg:$100$)?

Answer 1

Here is a standard method which can be used both for calculating a high power of a $2 \times 2$ matrix and solving this problem. It can be extended to higher size matrix.

Let $X^2+aX+b$ be the characteristic polynomial. Then there exists some $a_n,b_n$ such that $$ X^n=Q(X)(X^2+aX+b)+ a_nX+b_n \,...(1) $$ $a_n,b_n$ can be calculated explicitely, by plugging in the equation the two roots $r_1,r_2$ of the characteristic polynomial.

Plugging $A$ in (1) you get $$ A^n=a_nA+b_n \,. $$

In case of a double root differentiate (1) with respect to $X$ gives ($\alpha$ is repeated eigenvalue) $$nX^n=2Q(X)(X-\alpha) + Q'(X)(X-\alpha)^2 + a_n \,...(2)$$ put eigenvalue in (1) and (2)

In your particular problem $r_{1,2}=\frac{-1\pm \sqrt{5}}{2}$ and hence $$ (\frac{-1\pm \sqrt{5}}{2})^n=a_n\frac{-1\pm \sqrt{5}}{2}+b_n $$ You need to figure out $n$ such that $$ (\frac{-1\pm \sqrt{5}}{2})^n=-8\frac{-1\pm \sqrt{5}}{2}+5 $$

Answer 2

We can diagonalize the matrix $P$ because it has unique eigenvalues.

One of the benefits of this is in finding matrix powers.

For your example, we have eigenvalues as

$$\lambda_{1,2} = \frac{1}{2} \left(\mp\sqrt{5}-1\right)$$

The eigenvectors are

$$v_{1,2} = \begin{pmatrix} \dfrac{1}{10} \left(5\mp\sqrt{5}\right) \\ 1\end{pmatrix}$$

We can now write $P = V D V^{-1}$ as

$$\begin{pmatrix} \dfrac{1}{10} \left(5-\sqrt{5}\right) & 1 \\ \dfrac{1}{10} \left(\sqrt{5}+5\right) & 1 \\ \end{pmatrix} \begin{pmatrix} \dfrac{1}{2} \left(-\sqrt{5}-1\right) & 0\\ 0 & \dfrac{1}{2} \left(\sqrt{5}-1\right) \end{pmatrix}\begin{pmatrix} \dfrac{1}{2} \left(1-\sqrt{5}\right) & 0 \\ 0 & \dfrac{1}{2} \left(\sqrt{5}+1\right) \\ \end{pmatrix}$$

Now $P^n = V D^n V^{-1}$ is

$$\begin{pmatrix} \dfrac{1}{10} \left(5-\sqrt{5}\right) & 1 \\ \dfrac{1}{10} \left(\sqrt{5}+5\right) & 1 \\ \end{pmatrix} \begin{pmatrix} \left(\dfrac{1}{2} \left(-\sqrt{5}-1\right)\right)^n & 0\\ 0 & \left(\dfrac{1}{2} \left(\sqrt{5}-1\right)\right)^n \end{pmatrix}\begin{pmatrix} \dfrac{1}{2} \left(1-\sqrt{5}\right) & 0 \\ 0 & \dfrac{1}{2} \left(\sqrt{5}+1\right) \\ \end{pmatrix}$$

Answer 3

Hint: Write $P^n= a_n P + b_n I$. Then $P^2=-P+I$ implies $a_{n+1}=-a_n+b_n$ and $b_{n+1}=a_n$. Thus, $a_{n+1}=-a_n+a_{n-1}$ with $a_0=0$ and $a_1=1$. Trying the first few $n$ suggests that $a_n=(-1)^{n+1} F_n$, where $F_n$ is the $n$th Fibonacci number. Prove it by induction and find $n$ such that $a_n=-8$.

Answer 4

As Moo implied in a comment, if the required value of $\ n\ $ were very large, it would be a very unfair question for you to be expected to answer in an exam in which you only have $2$ minutes $10$ seconds to do so. Here, however, is a reasonably efficient method for obtaining the value of $\ n\ $ (if it exists) for which $\ P^n=aP+b\ $.

You've found that $\ P\ $ satisfies the equation $$ P^2=-P+I\ , $$ which means that $$ P^n=c_nP+c_{n-1}I\ , $$ where $\ c_n\ $ is the $\ n^\text{th}\ $ term in the sequence satisfying the recurrence \begin{align} &c_{n+1}=-c_n+c_{n-1}\\ &c_1=1,\ c_2=-1\ . \end{align} The equation $$ P^n=aP+bI $$ can be solved for (positive) $\ n\ $ if and only if $\ b\ $ and $\ a\ $ are successive terms in this sequence. To find the value of $\ n\ $ for which $\ a=c_n\ $ and $\ b=c_{n-1}\ $ you can use the identity $$ c_n=\frac{\alpha^n-\beta^n}{\sqrt{5}}\ , $$ where $\ \alpha=\frac{\sqrt{5}-1}{2}\ $ and $\ \beta=-1-\alpha\ $. Thus, if $\ a=c_n\ $ and $\ b=c_{n-1}\ $, then $$ a-\beta b=\frac{(\alpha-\beta)\alpha^{n-1}}{\sqrt{5}}=\alpha^{n-1}\ $$ or $$ n=\frac{\log(a-\beta b)}{\log\alpha}+1\ . $$ This will only be a solution if it is an integer, and $\ a=c_n\ $, but once you've found the putative value of $\ n\ $ it's easy to check whether $\ a=c_n\ $ and $\ b=c_{n-1}\ $, or that $\ P^n=aP+b\ $ directly.

For the specific problem you've given $$ n=\frac{\log(-8-5\beta)}{\log\alpha}+1=6\ . $$

Addendum:

As lhf pointed out in his answer, $\ c_n=(-1)^{n+1}F_n\ $, where $\ F_n\ $ is the $\ n^\text{th}\ $ Fibonacci number (my $\ c_n $ is lhf's $\ a_n\ $), a point which I missed, and which may help you follow the above exposition more easily. My formula for $\ c_n\ $ above is just a transformed version of the corresponding one for Fibonacci numbers: $$ F_n=\frac{\phi^n-\psi^n}{\sqrt{5}}\ , $$ where $\ \phi=-\beta\ $ and $\ \psi=-\alpha\ $.

Answer 5

I wanted to give an extension to the answer from N.S., who reduced the problem to finding $n$ such that

$$\left(\frac{-1\pm \sqrt{5}}{2}\right)^n=-8\frac{-1\pm \sqrt{5}}{2}+5$$

This is actually two equations which are conjugate to each other, and if we add or multiply them together, the irrationalities disappear.

Multiplication would normally be the easier method, but unfortunately, in this case, calling the $\phi=\frac{-1+ \sqrt{5}}{2}$ and $\overline{\phi}=\frac{-1 - \sqrt{5}}{2}$, the fact that $\phi \overline{\phi}=-1$ and $\phi+\overline{\phi}=-1$ means that the equation simplifies to $$(-1)^n=1$$ which only tells us that $n$ must be even, although if we had a different problem where $\det(P)\neq \pm 1$, this would have let us easily solve the problem. We can get more information by adding the two equations, in which case $$\phi^n+\overline{\phi^n}=18.$$

N.B. We remark that taking the product or sum of the two equations is what falls out if we diagonalize the original matrix, then take the determinant and trace.

However, how do we deal with the left hand side of the equation? We can use the fact that $\phi$ and $\overline{\phi}$ both satisfy the equation $x^2=-x+1$, which will imply that $\phi^n$ and $\overline{\phi^n}$ (and hence their sum) both satisfy the linear recurrence relation $a_{n+1}=-a_{n}+a_{n-1}$, and their sum has the initial conditions that $a_0=2$, $a_1=-1$. This can be computed for small values of $n$ (and will be, up to a sign, the Lucas numbers), but this is prohibitively difficult for large values of $n$.

We can get an estimate, however, by using the fact that $0<\phi^2<1$ and $2<\overline{\phi^2}<3$. Because $3^2<17$, we know that $n>4$, and because $2^5>18$, we know that $n<10$. This means (since we know $n$ is even), that $n=6$ or $8$. Of course, if you have a calculator, none of this additional work is necessary, as one can simply solve the problem with logs.

Answer 6

I want to give an answer that is completely different than everything else given so far: using modular arithmetic.

We are trying to solve $P^n=5I-8P$. If we reduce this modulo different primes, we can get conditions on $n$ which will help narrow down our search (although other methods may be necessary to finish up, especially if we are in a different situation where $n$ is very large).

The characteristic polynomial of $P$ is $x^2+x-1$, and things work out best if we choose to reduce modulo a prime where this is solvable, although there are ways to make this work without this using finite fields. This, however, is beyond the scope of the answer I wish to give. Since the roots of this equation are $\frac{-1\pm \sqrt{5}}{2}$, we will choose primes where $5$ is a perfect square and $2$ is invertible. Quadratic reciprocity says that $5$ is a square mod $p$ if and only if $p$ is a square mod $5$, so $p\equiv 0, \pm 1 \pmod 5$. Let us see what happens mod 5 and 11.

Modulo 5, the characteristic equation has a double root of $x=2$, and since $P$ is not a scalar matrix mod 5, we need to use Jordan normal form. $P$ will be similar to $$Q=\begin{pmatrix} 2 &1\\ 0 &2 \end{pmatrix}.$$ We can compute that $$Q^n=\begin{pmatrix} 2^n &n2^{n-1}\\ 0 &2^n \end{pmatrix}.$$

Therefore, if $Q^n=5I-8Q=2Q \pmod 5$, then we we need $2^n\equiv 4 \pmod 5$ and $n2^{n-1}\equiv 2\pmod 5$. Since $\operatorname{ord}_5(2)=4$ and $2^2\equiv 4 \pmod 5$, this tells us that $n\equiv 2 \pmod 4$, or $n=2+4k$. Plugging into the second equation, we must solve $(2+4k)2^{1+4k}\equiv 2 \pmod 5$. By Euler's theorem, $2^{1+4k}\equiv 2 \pmod 5$, so we simplify to $(2+4k)2\equiv 2 \pmod 5$, which becomes $k\equiv 1 \pmod 5$, so $k=1+5\ell$. Thus, $n=2+4k=2+4(1+5\ell)=6+20\ell.$ If you knew that $n<26$, this would give only one possible value for $n$.

Let us now look modulo $11$. Since $5\equiv 4^2 \pmod{11}$, and $6\times 2\equiv 1 \pmod {11}$, the roots of the characteristic equation are $6(-1\pm 4)\equiv 3, 7 \pmod{11}$. Thus, modulo $11$ $P$ is similar to the matrix $Q=\operatorname{diag}(3,7)$, and solving $Q^n\equiv 5I-8Q \pmod{11}$ means solving $3^n\equiv 5-8(3) \pmod{11}$ and $7^n\equiv 5-8(7) \pmod{11}$.

The first equation simplifies to $3^n\equiv 3 \pmod{11}$, or $3^{n-1}\equiv 1 \pmod{11}$. The order of 3 must divide $\phi(11)=11-1=10$, so is either $1, 2, 5$, or $10$. We can compute that the order is $5$, so $n-1=5k$, or $n=1+5k$ for some $k$.

The second equation simplifies to $7^n\equiv 4 \pmod{11}$. Since $7\equiv -4 \pmod 11$, we can rewrite this as ${(-4)}^{n-1}\equiv -1 \pmod{11}$. If this is solvable at all, we must have that $2(n-1)$ divides $11-1$, so $n-1$ divides $5$. It is straight forward to check that $(-4)^5={-1}$, and by Euler's theorem, $(-4)^{n-1}\equiv -1 \pmod{11}$ if and only if $n-1\equiv 5 \pmod{10}$., or $n\equiv 6 \pmod{10}$.

Let us also examine modulo 2, since things simplify enough in that case that we can use general theory and avoid actual difficult computations. The equation we are trying to solve simplifies to $P^n\equiv I \pmod 2$. Since the characteristic equation has no solutions $\pmod 2$, we have to pass to $\mathbb F_4$ to find the eigenvalues. The group of units in $\mathbb F_4$ has size $4-1=3$, and so the order of $P\pmod 2$ must divide $3$. Since it is obviously not $1$, it is $3$. Thus, $n$ is a multiple of $3$, which we can combine with our observation that $n\equiv 6 \pmod{20}$ to get that $n\equiv 6 \pmod{60}$.

Working modulo different primes, we can get even more information about what $n$ would have to be, and in principle, this can be done entirely by hand. The results modulo different primes can then be assembled together by using the Chinese remainder theorem. While it does not yield a single solution, the information obtained can be combined with estimates such as given in my other answer to hone in on the exact solution.

Answer 7

A comment before the answer:

I was confused at this question but when I saw your quadratic equation, suddenly the method struck my mind. It was under all our noses, but we were too much attached to using the standard tools like eigen values and eigen vectors.

---

Soltn:

Mentally, one may calculate the trace as $-1$ and determinant as $-1$: This gives us the following equation:

$$P^2 + P =I \tag{1}$$

Since $ det P \neq 0 $ it is invertible, now go to problem in question $$P^n +8P = 5I$$

Now, plug in the identity matrix in terms of $P$ and simplfy:

$$P^n + 3P = 5P^2$$

We can multiply both side by $P^{-1}$:

$$P^{n-1} +3I = 5P$$

Repeating, the procedure :

$$ P^{n-2} + 3 P^1 = 2I$$

Let's hit it with the bat one more time:

$$ P^{n-3} +I= 2(P^1 )$$

And again:

$$ P^{n-4} +P = I$$

There is a famous quote "No need to beat a dead horse" but this equation we have to substitute once more:

$$P^{n-4} = P^2 $$

Hence, $n-4=2$ or $n=6$

For higher powers, there maybe a way to short this process of back substitution. I'll leave that to you to figure out.