6
$\begingroup$

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

1 Answers 1

9

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

  • 0
    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.2012-10-01