Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $J$ be the following $k-by-k$ Jordan block: $$ J:= \begin{bmatrix} e^{i \theta} & 1 & \\ & e^{i \theta} & 1 \\ & & \ddots & \ddots \\ & & & \ddots & 1 \\ & & & & e^{i \theta} \end{bmatrix}. $$

Is there an efficient way to compute the action of large powers of $J$, ie: $$J^n x$$ to within tolerance $\epsilon$, when $n$ is extremely large?

Notes,

  • The goal is to find a computational procedure $f_n$, so that $||f_n(x)-J^nx||<\epsilon$ for all $x$, and computing $f_n(x)$ takes (significantly) less work than iteratively applying $J$ over and over.
  • Feel free to make $n$ depend on $k$ and $\epsilon$ and let $n$ it be as large as you want - I'm interested in the asymptotic behavior.
  • $\theta/2\pi$ could be irrational
share|improve this question

1 Answer 1

up vote 9 down vote accepted
+500

I do not see much problem. Write $J = e^{i \theta} I \; + \; K,$ where $I$ is the identity matrix and $K$ is the matrix of $1$'s just above the main diagonal. The point, of course, is that $KI = IK = K$ and $K^k = 0.$ So $$ (e^{i \theta} I + K)^n = \sum_{w = 0}^{k-1} \; \binom{n}{w} e^{i (n-w) \theta} \; K^w $$ where $K^0 = I.$

I almost used $N$ for the nilpotent part but felt $K$ worked better here. Note that the nonzero entries in $K^w$ are $1$'s in postions $ij,$ meaning row $i$ and column $j,$ with $1 \leq i \leq k - w$ and $j = i + w.$ So these are parallel to the main diagonal. By the time we get to $w= k-1,$ the only nonzero entry in $K^{k-1}$ is a single $1$ in position $1k.$ And then $K^k =0.$ So, for what it may be worth, the recipe above gives an explicit value for each of the relevant $(k^2 + k)/2$ nonzero entries. How you feel about the potential accuracy of these individual entries, $ \binom{n}{w} e^{i (n-w) \theta}, $ is another matter, as the binomial coefficient may be huge.

On the note of accuracy, I did want to indicate my answer at this one $\sin(A)$, where $A$ is a matrix , mention the gerbils, but also mention the comment underneath with an article about numerically dubious ways to find $e^A$ for a square matrix $A.$ I think the message is that you match methods to needs. See pdf at DUBIOUS

share|improve this answer
    
Wow. I actually did that decomposition and wrote down that formula, but didn't think to eliminate the terms $j>k$. Thank you. I'm going to think about it a little bit and then when I've thought it over fully I'll award the bounty. –  Nick Alger Oct 1 '12 at 5:27
    
Haha, ok. As an aside, this is the last piece in raising an arbitrary (nondiagonalizagle) matrix to very high powers, which I plan to write up in a short explanation and put on my website. I will be sure to cite you and this thread. –  Nick Alger Oct 1 '12 at 5:31

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.