The Eigenvalue Problem Revisited, Numerically.
Dan Allen

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.

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 method of calculating eigenvalues has generally been discouraged in the past due to its need for a root-finder, 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:

N
Mean 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
11
139.332
12
187.216
25
3147.219

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

1st reformatting via LibreOffice,  8 Nov 2022.
2nd reformatting in HTML by hand, 31 Jan 2024.