Let us define a $n\times n$ matrix $A$ as follows : the $(i,j)$-th entry in the matrix A is $1$ if $i$ and $j$ are distinct and equal to $3$ otherwise. Find the $(i,j)$-th entry in the matrix $A^m$ when $i\neq j$.
Asked
Active
Viewed 77 times
2 Answers
2
Let $e=(1,...,1)^T$. Then $A = e e^T+2 I$. Note that $I$ and $e e^T$ commute.
For $k =1,2,...$, we have $(e e^T)^k = n^{k-1} (e e^T)$, $(2I)^k = 2^k I$.
$A^m = (e e^T+2 I)^m = \sum_{k=0}^m \binom{m}{k} (e e^T)^k (2I)^{m-k} = 2^m I + \left(\sum_{k=1}^m \binom{m}{k} n^{k-1} 2^{m-k} \right) (e e^T)$.
$\sum_{k=1}^m \binom{m}{k} n^{k-1} 2^{m-k} = {2^m \over n}\sum_{k=1}^m \binom{m}{k} ( { n \over 2 } )^k = {2^m \over n} \left( (1+ { n \over 2 } \right) ^m -1 )$.
Finally, $A^m = 2^m I + {2^m \over n} \left( (1+ { n \over 2 } ) ^m -1 \right) (e e^T)$.
copper.hat
- 172,524
-
And the Caffe Med bursts into cheers! ;-) – Robert Lewis Dec 05 '13 at 04:39
-
1@RobertLewis: Miss that place! – copper.hat Dec 05 '13 at 05:31
-
@ copper.hat: so come on down! Seriously, I thought your answer on this one was top notch. I too had noticed that setting $A = 2I + J$ and using $J^m = n^{m - 1}J$ with the binomial theorem seemed the way to go, but I'm not very facile with reducing sums, and I probably only would have got as far as $A^m = 2^m I + \left(\sum_{k=1}^m \binom{m}{k} n^{k-1} 2^{m-k} \right) (e e^T)$. Again, way to go. And come on down! – Robert Lewis Dec 05 '13 at 05:34
-
@RobertLewis: I may try to get there Sunday morning... – copper.hat Dec 05 '13 at 05:37
-
@ copper.hat: well, I'll be here then, mos' likely after about 11 . . . – Robert Lewis Dec 05 '13 at 05:53
-
@RobertLewis: If I come, I usually sit beside the piano to listen to the music and typically have a Tilley hat! – copper.hat Dec 05 '13 at 05:57
-
@ copper.hat: I'm sure I'll recognize you! – Robert Lewis Dec 05 '13 at 06:49
-
@ copper.hat: do you know Rabia and Keizo who play at the Med on Sunday mornings? – Robert Lewis Dec 05 '13 at 17:17
-
@RobertLewis: I'm not sure, there's a blind fellow and a lady, is that them? – copper.hat Dec 05 '13 at 17:21
-
@ copper.hat: well, he's not quite blind, but yeah, that sounds like them. – Robert Lewis Dec 05 '13 at 17:23
-
@RobertLewis: My typing skills, space and fear of the Stack Exchange anti-politeness demons limits my powers of description :-). – copper.hat Dec 05 '13 at 17:26
-
@ copper.hat: I read you loud and clear on that one! – Robert Lewis Dec 05 '13 at 17:29
0
Your matrix is the sum of the matrix of all $1$s (known as $J$) and twice the identity. Which means that it can be diagonalized easily (the eigenvalues are $n+2$ and a bunch of $2$s, (one set of eigenvectors is: the vector of all ones and vectors of the form $e_1 - e_j,$ for $j>1,$ though you should be able to find some orthogonal eigenvectors, too, since the matrix is symmetric. Now it is an easy matter to raise to a power.
Igor Rivin
- 25,994
- 1
- 19
- 40
-
-
If $A = P B P^{-1}, then $A^k = P B^k P^{-1}.$ Raising a diagonal matrix to power should not present much of a problem. – Igor Rivin Dec 05 '13 at 04:00