$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$
-
5Compute the Jordandecomposition $A = S^{-1}(\Lambda + N)S$, with $\Lambda$ diagonal, $N$ nilpotent. Then $A^{50} = S^{-1}(\Lambda + N)^{50}S = S^{-1}(\Lambda^{50} + 50\Lambda^{49}N + 25\cdot 49 \Lambda^{48}N^2)S$. – 2012-05-10
-
0i was thinking along the line of minimal polynomial, looks like it doesn't help. – 2012-05-10
-
0Can't i diagonalized it? – 2012-05-10
-
1If $A$ is diagonalizable, then $N = 0$ in the above decomposition, so $A^{50} = S^{-1}\Lambda^{50}S$. – 2012-05-10
-
0Find the Eigenvalues and Eigen vectors using Wolfram Alpha The command "Eigenvalues[{1,0,0},{1,0,1},{0,1,0}]" works. There is a repeated Evalue and the Espace associated is 1 dimensional. You can find the nilpotent part by subtracting. – 2012-05-10
-
0$(D+N)^{50}$ where $D$ is diagonal matrix , will be calculated? – 2012-05-10
-
0Another wrinkle for this question (probably not intended): Srijan did not say $A$ is a real or complex matrix. What if the entries are in some other field, say a finite field? – 2012-05-10
-
0that is for real field – 2012-05-10
-
0eigen values are 1 , 1, -1 what next? – 2012-05-10
-
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]
-
1I don't really like using programs for this type of problems, because the students don't learn anything. Actually often I have a hard time explaining to the students why they should try to think when there is a program which can solve this type of problems.... – 2012-05-10
-
0I often wonder what the point of teaching students arithmetic (whether simple or complex) is. I feel that there is a purpose, but I can't identity it... – 2012-05-10
-
1The point is to get them to understand what they are doing and think. Ultimately my main hope in each class is that the students really understand when a certain method can or cannot be used, and catch whenever an answer makes no sense, but how many students wouldn't take what the software sais for granted... And there are soo many instances when there is a flaw in the usage... I wonder if this problem would be an assignment, and some software would say that the answer is – 2012-05-10
-
0$$A^{50} =\left( \begin{array}{ccc} 1 & 0 & 0 \\ -25 & 0 & 0 \\ -25 & 0 & 0 \\ \end{array} \right) $$ how many students would figure that that cannot be right... Or in a room fool of rocket scientists I would expect at least one to figure out that there is a 60% error in a computation, but somehow at some point NASA made such an error with the metric vs. imperial system.. 60% error and noone figured it, people take these for granted... – 2012-05-10
-
1And just for curiosity, what answer does PARI/GP yield for $A^{10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}$? – 2012-05-10
-
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} $$
-
0Why the downvote? – 2012-05-10
-
2Alternatively, write down the matrix of $A^2$, when the answer becomes obvious. – 2012-05-10
-
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} \]
-
0Dear sir what if matrix A is not diagonalizable? – 2012-05-10
-
1$A$ isn't diagonalizable, so I computed its [Jordan form](http://en.wikipedia.org/wiki/Jordan_normal_form). – 2012-05-10
-
0oops sorry for my stupidity? – 2012-05-10
-
0No need to say sorry, everything is ok. You do know the Jordan normal form of a matrix? – 2012-05-10
-
0Thanks sir. I am reading now. – 2012-05-10
-
0Sie why we have chosen basis of $ker(A-1)^2$? – 2012-05-10
-
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$.
-
0I am unable tp stand induction process? However, method looks facinating. Can you explain bit more? – 2012-05-10
-
0@srijan, from $A^3= A^2+A-I$ we get $A^4= A^3+A^2-A = (A^2+A-I)+A^2-A=2A^2-I$. Repeat the process to find $A^5$, $A^6$, etc. Identify a pattern... – 2012-05-10
-
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