next up previous
Next: An Example Due Up: Eigenvalue Problems. Previous: Eigenvalue Problems.

Symbolic Computation With Eigenvalues

For some special problems, efficiency or insight can be gained from working with symbolic representations of the eigenvalues, perhaps using the characteristic polynomial as an aid to symbolic manipulation. This helps particularly when the matrices depend on parameters, and the influence of the parameter needs to be studied.

The following example arose from a USENET discussion started by Cleve Moler, and is now part of the example files for the Symbolic Toolbox by which Matlab can call Maple.

Consider for example the `gallery(3)' matrix from Matlab:

The eigenvalues of this matrix are particularly sensitive to perturbation. In particular, if we choose the matrix E as

(notice that E is roughly the same size as A) and form the perturbed matrix A+tE where t is a scalar, we get

If we form the characteristic polynomial of this (symbolic) matrix (this is reasonable because the degree is only three), we get

This polynomial will have multiple roots when its discriminant with respect to x is zero (for a polynomial of degree three this is a precise characterization --- see [6] for more details). We find the discriminant in Maple via the discrim command:

> d := discrim(p,x);
                                    2                       3                 4
d := 4 - 5910096 t + 1403772863224 t  - 477857003880091920 t  + 242563185060 t
By using the realroot command we can easily show that this discriminant has two real roots, one of them (call it ) between and .

We thus see that this very small perturbation changes the eigenvalues of A (which are 1, 2, and 3) into a set with a multiple root. To verify this symbolically, we can find a symbolic expression for and substitute it for t, and try to factor the characteristic polynomial (this will be easy if there is a multiple root). The following Maple session shows how to do this. Note that the formula for in terms of radicals that is available since the discriminant is a degree four polynomial in t is not used. However, it is difficult to work with nested radicals. Instead, we use the RootOf notation. This notation is discussed further in the next section.

> alias(t0= RootOf(d,t));
                                     I, t0

> Normalizer := simplify;
                             Normalizer := simplify
is a symbolic way of representing any root of the discriminant. Later, we will use a routine that needs to normalize with the routine simplify, to deal effectively with the RootOf construct.
> pt0 := subs(t=t0,p);
                 3      2              2
         pt0 := x  - 6 x  + 11 x - t0 x  + 492512 t0 x - 6 - 1221271 t0
Now pt0 ought to have a multiple root.
> pf := factor(pt0);
   pf := 1/3617330840862075776271364437466707007583905327874048 (

       96703623305979008 x + 19716665846146478987085 t0 - 283005565738990253

                                          2                             3
        - 21733243079681277776111127375 t0  + 11031929259781122453495 t0 ) (

       193407246611958016 x - 297216174096883795 - 19716762549769784966093 t0

                                          2                             3
        + 21733243079681277776111127375 t0  - 11031929259781122453495 t0 )^2
Ah, it does. We can thus express the eigenvalues of A exactly in terms of , then.
> lambda := [solve(pf,x)];
lambda := [

   11031929259781122453495   3   1792424167831498089735      283005565738990253
 - ----------------------- t0  - ---------------------- t0 + ------------------
      96703623305979008             8791238482361728          96703623305979008

        21733243079681277776111127375   2
      + ----------------------------- t0 ,
              96703623305979008

 297216174096883795   1792432959069980451463
 ------------------ + ---------------------- t0
 193407246611958016      17582476964723456

        21733243079681277776111127375   2   11031929259781122453495   3
      - ----------------------------- t0  + ----------------------- t0 ,
              193407246611958016               193407246611958016

 297216174096883795   1792432959069980451463
 ------------------ + ---------------------- t0
 193407246611958016      17582476964723456

        21733243079681277776111127375   2   11031929259781122453495   3
      - ----------------------------- t0  + ----------------------- t0 ]
              193407246611958016               193407246611958016
This ought to have only two distinct roots, and (which is the multiple root).

Now we have symbolic expressions for the eigenvalues in terms of the (computable) critical value of the parameter . We can thus evaluate those eigenvalues to as many places as we wish. It is an easy exercise to compute symbolic expressions for the corresponding eigenvectors, in terms of .

Exercises

  1. Compute the eigenvectors for the above example, and show that the Jordan Canonical Form is nontrivial.
  2. Plot the paths of the eigenvalues of A + tE in the complex plane as functions of t. This plot is a bifurcation diagram since it shows how the characteristics of the matrix change (bifurcate) as t passes through the critical parameter .
  3. The matrix E from the example was chosen as where x and y were right and left eigenvectors of the matrix A corresponding to the smallest eigenvalue, . Use Maple to verify this by finding the right and left eigenvectors of A. Form two other perturbation matrices and from similar outer products of the eigenvectors of the eigenvalues and . Find the minimum norm of such that the perturbed matrix has a triple eigenvalue. [Ans: ]


next up previous
Next: An Example Due Up: Eigenvalue Problems. Previous: Eigenvalue Problems.



Robert Corless
Wed Jan 31 11:33:59 EST 1996