## Do We Really Need Eigen Values?

```Many problems in mathematics and physics reduce "eigenvalue
problems", and people often expend lots of effort trying to
determine the eigenvalues of a general NxN system, and this
is sometimes reduced to finding the roots of the Nth degree
characteristic polynomial.  The task of efficiently finding
all the complex roots of a high-degree polynomial is non-
trivial, and is complicated by the need to consider various
special cases such as repeated roots.

However, depending on what we're really trying to accomplish,
we may not need to find the eigenvalues at all.  Of course, the
description of an action is usually simplest when its components
are resolved along the directions of the eigenvectors, e.g., the
eigenvectors of a rotation matrix define its axis of rotation.
As a result, it's easy to write equations for the positions of
points on a rotating sphere if we work in coordinates that are
aligned with the eigenvectors of the rotation, whereas if we work
in some other arbitrary coordinates the equations describing the
motion will be more complicated.

However, there are many situations in which the characteristic
axes of the phenomenon can be exploited without ever explicitly
determining the eigenvalues.  For example, suppose we have the
system of three continuous variables x(t), y(t), and z(t) that
satisfy the equations

ax + by + cz  =  x'
dx + ey + fz  =  y'
gx + hy + iz  =  z'

and we want to determine the exact root-matched recurrence formulas
for x(nT), y(nT), and z(nT) for a given discrete time interval T.
The characteristic polynomial is

r^3 - Ar^2 + Br - C = 0
where
A = a+e+i
B = ae-bd+ai-cg+ei-fh
C = aei+bfg+cdh-ceg-bdi-afh

The root-matched recurrence coefficients are proportional to the
elementary symmetric functions (with alternating signs) of the
quantities exp(r_k T), where r_k, k=1,2,3 are the eigenvalues, so
a common approach is to solve the characteristic equation for the
eigenvalues and then compute the recurrence coefficients.  Even for
a simple cubic the precise determination of the (complex) roots in
embedded code, covering all possible cases, can be tricky and
time-consuming.  For higher order systems it's even worse.

However, we don't really need to solve for the eigenvalues.  Let
w(k) denote the sum of the kth powers of the roots r_1, r_2, r_3.
Clearly w(0)=3, and the values of w(k) for k=1,2,... are given by

w(1)   +   A  =  0
w(2) + w(1) A + 2 B  =  0
and
w(k) + A w(k-1) + B w(k-2) + C w(k-3)  =  0

for all k > N-1.  Now let E(k) denote the sum of the kth powers of
the values exp(r_k T), k=1,2,3.  Expanding each of the exponential
functions as a Taylor series and combining terms by powers of T gives

inf  (kT)^j
E(k)  =  SUM   ------ w(j)            k=1,2,3
j=0     j!

Letting s_k denote (-1)^k times the kth elementary symmetric function
of the quantities exp(r_j T), we can now compute s_0, s_1, s_2, and s_3
using the identities

s_0  =  1
E(1)   +  1s_1  =  0
E(2)   +  E(1)s_1 + 2s_2  =  0
E(3) + E(2)s_1 + E(1)s_2 + 3s_3  =  0

Then the exact homogeneous recurrence formula for x(t) is

s_0 x(nT) + s_1 x((n-1)T) + s_2 x((n-2)T) + s_3 x((n-3)T)  =  0

and the recurrences for y(t) and z(t) are identical.  The summation
for E(k) is quite well-behaved and can be implemented quite easily in
embedded code.  This method, which is directly applicable to systems
of any order, requires no root-finding algorithm and no special
consideration of repeated roots, etc.
```