Jordan Power

Let \( \newcommand{\x}{\mathbf{x}} \newcommand{\v}{\mathbf{v}} \newcommand{\e}{\mathbf{e}} T\) be the transition matrix of a discrete linear dynamical system. Recall the \(n\)th state starting from the initial vector \(\v\) is \( T^n \v.\)

We proved (without determinants!) that \(T = P^{-1} A P\) where \(A\) is in Jordan canonical form. Thus we can compute \(T^n\) via:

\[ T^n = (P^{-1} A P)^n = P^{-1} A^n P \]

If we’re lucky, then \(A\) is diagonal so \(A^n\) is trivial to calculate: just raise each diagonal entry to the \(n\)th power. A couple of matrix multiplications more yield \(T^n\). This is how we derived Binet’s formula and its generalization.

But what if there are ones on the superdiagonal?

A little algebra goes a long way. First, let \(N\) be an \(n\times n\) square matrix whose superdiagonal is all 1s, and is 0 everywhere else. Then it is easy to show that each successive power of \(N\) has 1s directly above the entries that were 1 in the previous power, and has 0s where the 1s were.

jsEval "curl_module('Matrix.ob')"

import Matrix

jordanBlock (a, n) = take n $ take n <$> iterate (0:) (a : 1 : repeat 0)
directSum a b = (++ zb) <$> a <|> (za ++) <$> b where
  za = replicate (length a) 0
  zb = replicate (length b) 0
jordan = foldr1 directSum . map jordanBlock

exampleN = Matrix $ jordanBlock (0, 6)

putStr $ unlines $ map show $ take 7 $ iterate (exampleN *) 1

Next, the \(k\)th power of a Jordan block is:

\[ (N + \lambda)^k = \sum_{i=0}^k {k \choose i} N^i \lambda^{k - i} \]

which looks like:

\[ \begin{bmatrix} \lambda^k & {k \choose 1} \lambda^{k-1} & {k \choose 2} \lambda^{k-2} & … \\ 0 & \lambda^k & {k \choose 1} \lambda^{k-1} & … \\ & \ddots & \ddots \\ 0 & & 0 & \lambda^k \\ \end{bmatrix} \]

m = Matrix $ jordanBlock (10, 4)

putStr $ unlines $ map show $ take 7 $ iterate (m *) 1

In general, the \(k\)th power of a matrix in Jordan canonical form is the direct sum of such blocks.

Thus we can find a Binet-like formula for the \(n\)th term of any linear recurrence. Though in general, the formula involves roots of some polynomial. For degree 5 and above, it may be impossible to find expressions that only use standard arithmetic operations and root extraction.

Ben Lynn blynn@cs.stanford.edu 💡

Jordan Power

Contents