$A =\left( \begin{array}{ccc} 1 & 0 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 0 \\ \end{array} \right)$ then what would be $A^{50}$? For real entries
Computing $A^{50}$ for a given matrix $A$
-
0@GEdgar: This wouldn't change anything about $A^{50}$. $A$ can be seen as a matrix over any field. My answer works in general. – 2012-05-10
5 Answers
With PARI/GP:
gp >[1,0,0;1,0,1;0,1,0]^50 %1 = [1 0 0] [25 1 0] [25 0 1]
-
1[1 0 0] [500000000000000000000000000000000000000000000000000000000000000000000000000 1 0] [500000000000000000000000000000000000000000000000000000000000000000000000000 0 1] – 2012-05-10
Let $e_1,e_2,e_3$ be the basis vectors. We have $Ae_2=e_3$ and $Ae_3=e_2$, so $A^{50}$ fixes both $e_2$ and $e_3$. We only need to check what $A^{50} e_1$ is. Calculate the first few: $ Ae_1=e_1+e_2,~A^2e_1 =e_1+e_2+e_3, A^3e_1=e_1+2e_2+e_3. $ We use induction to prove $A^{2k-1}e_1=e_1+k e_2 + (k-1)e_3$ and $A^{2k}e_1=e_1+ke_2+ke_3$. So $A^{50}e_1=e_1+25e_2+25e_3$ and $ A^{50}=\begin{pmatrix}1&0&0\\25&1&0\\25&0&1\end{pmatrix} $
-
0@Lubin: True, but at least my method gives $A^k$ for odd $k$ too :) – 2012-05-12
the characteristic polynomial is \[ \chi_A(t) = (1-t)\bigl(t^2 - 1) \] so the eigenvalues are $\pm 1$, we have \[ A - 1 = \begin{pmatrix} 0 & 0 & 0\\\ 1 & -1 & 1 \\\ 0 & 1 & -1 \end{pmatrix} \] which has defect $1$ (so $A$ isn't diagonalizable). It holds \[ (A - 1)^2 = \begin{pmatrix} 0 & 0 & 0\\\ -1 & 2 & -2 \\\ 1 & -2 & 2 \end{pmatrix} \] so a basis of $\ker (A-1)^2$ is $\\{(2,1,0), (2,0,-1)\\}$, we have $A \cdot (2,1,0) = (0, 1, 1)$, so $\\{(2,1,0), (0,1,1)\\}$ is the basis of $\ker(A-1)^2$ we will use. It holds \[ A + 1 = \begin{pmatrix} 2 & 0 & 0\\\ 1 & 1 & 1 \\\ 0 & 1 & 1 \end{pmatrix} \] we choose the basis $\{(0,1,-1)\}$ of its kernel. So we let \[ S := \begin{pmatrix} 2 & 0 & 0\\\ 1 & 1 & 1 \\\ 0 & 1 & -1 \end{pmatrix} \] Then \[ S^{-1}AS = \begin{pmatrix} 1 & 0 & 0\\\ 1 & 1 & 0 \\\ 0 & 0 & -1 \end{pmatrix} \] so \[ S^{-1}A^{50}S = \begin{pmatrix} 1 & 0 & 0\\\ 50 & 1 & 0 \\\ 0 & 0 & -1 \end{pmatrix} \] and finally \[ A^{50} = \begin{pmatrix} 1 & 0 & 0\\\ 25 & 1 & 0 \\\ 25 & 0 & 1 \end{pmatrix} \]
-
0I got the idea. This involves theory of generalized eigen vectors. – 2012-05-10
The characteristic polynomial of $A$ is
$X^3-X^2-X+1=(x-1)^2(x+1)$
The Division Theorem tells us that
$X^{50}=(X^3-X^2-X+1)Q(x)+ax^2+bx+c (*)$
Plugging in $x=1$, $x=-1$ yield
$1=a+b+c$ $1=a-b+c$
Thus $b=0$ and $a+c=1$.
Differentiating $(*)$ and using the fact that $(X^3-X^2-X+1)Q(x)=(x-1)^2(something)$ we get
$50x^{49}=(x-1)(junk)+2ax+b$
Plugging in $a=1$ we get
$50=2a+b$
Thus $a=25, b=0, c=-24$
This proves that
$X^{50}=(X^3-X^2-X+1)Q(x)+25x^2-24$
Using the fact that $A^3-A^2-A+I =0$ we get
$A^{50}=25A^2-24I$
P.S. This is basically the same proof as Ihf 's, the only difference is that long division can replace the induction process.
To get the general formula, repeating the process for
$X^{n}=(X^3-X^2-X+1)Q(x)+ax^2+bx+c (*)$
yields
$a+b+c=1$ $a-b+c =(-1)^n$ $2a+b=n$
and
$A^n= aA^2+bA+cI$
-
0Nice solution. (But please make up your mind between $x$ and $X$.) – 2012-05-25
By the Cayley–Hamilton theorem, $A^3= A^2+A-I$. From this relation we can find all powers of $A$ in terms of $A^2$, $A$, and $I$. By induction, we get $ A^{2n} = n A^2 -(n-1)I, \qquad A^{2n+1} = n A^2 +A-nI $ Hence, $A^{50} = 25A^2-24I$.
-
0@srijan, if you don't want to use induction, compute $A^{50}=A^{32} A^{16} A^2$, which is easy from $A^4$, $A^8$, $A^{16}$, $A^{32}$ when written in terms of $A^2$ and $I$. – 2012-05-10