The Eigenvalue Problem Revisited, Numerically.

The eigenvalue problem is a fundamental problem of linear algebra that arises in many different settings in physics, chemistry, statistics, and mathematics. For any n x n matrix A, the eigenvalues of that matrix are the n roots l1, l2, ..., ln of the characteristic equation of the matrix A, that is, the roots of equation 1,

| lI - A | = 0 (1)

where I is the standard n x n identity matrix. Equation one expanded becomes

c(x) = xn + c1xn-1 + c2xn-2 + ... + cn-1x + cn (2)

The problem is in obtaining the coefficients c1, c2,..., cn of the characteristic polynomial which results from expanding the above determinant.

Le Verrier's method, as modified by Souriau and Frame, uses a recursive algorithm. The algorithm is as follows:

For an n by n matrix A

Begin

set Bo = I

For k = 1 to n

Ak = ABk-1

ck = -(1/k) tr(Ak) Where the ck are in Equation 2.

Bk = Ak + ckI

Next k

End.

The characteristic equation is then solved by any standard root-solver for the eigenvalues.

Sample Program For HP-75C w/ Math ROM:

``` 10	OPTION BASE 1 				! Array lower limit is 1
20	DIM A(10,10), B(10,10), C(11), E(10,2)	! Dimension arrays for n=10
30	INPUT "DIM: "; N			! Input order
40	REDIM A(N,N)				! Resize matrix for entry
50	MAT INPUT A				! Input matrix coefficients
60	MAT B=IDN(N,N)				! Initialize B to identity
70	MAT C=CON(N+1)				! Init. Characteristic coeff.
80	FOR I=1 TO N
90		MAT B=A*B			! Let B = A*B
100		T = 0				! Set Trace = 0
110		FOR J=1 TO N
120			T=T+B(J,J)		! Trace of A*B
130		NEXT J
140		C(I+1), Z = -T/I		! Char eq. Coeffs. computed
150		FOR J=1 TO N
160			B(J,J)=B(J,J) + Z	! Add coeff. to B
170		NEXT J
180	NEXT I
190	MAT E=PROOT(C)				! Solve characteristic eq.
200	MAT DISP USING "6d.7d,2x,6d.7d" ; E ;	! Display complex roots
210	END
```
This routine will solve for the eigenvalues of any real matrix (symmetric or non-symmetric) by solving the computed characteristic equation by a general polynomial root-solver, PROOT which gives all roots (real and complex) of any polynomial with real coefficients.

This method of calculating eigenvalues has generally been discouraged in the past due to its need for a root-finder,4 which has its own problems, but most good numerical libraries contain a root-finder that can be used. An example of the simple elegance of this routine may be seen in the sample program listing which is from a Hewlett-Packard HP-75C portable computer, which has up to 24K of CMOS RAM and a very powerful built-in 48K BASIC/operating system. With the addition of a 16K Math ROM, this portable computer has built-in BASIC keywords for matrix manipulations, complex numbers, numerical integration, and root-finding. A condensed version of this program only requires 436 bytes of memory, and thus all of the eigenvalues may be solved for in a matrix up to 28 x 28, all in a battery operated portable computer!

The following are some sample times:

```
NMean Time Seconds
3  3.628
4  7.036
5 13.327
6 20.041
7 30.855
8 47.111
9 68.767
10 98.068
11139.332
12187.216
253147.219
```
The time required in seconds is thus roughly proportional to n3/10.

#### By Dan Allen, 4 June 1984, for Math 411 Numerical Analysis at BYU.

Reformatted, albiet poorly, in HTML 8 Nov 2022.