Updated 2013-09-01 16:27:00 by RLE

GWM One of the features of solving Simultaneous Equations is that eigenvalues come into the problem at least in theory. See also Matrix determinant.

An eigenvalue is associated with an eigenvector; when a vector is multiplied by a matrix a new vector is created; if the new vector is parallel to the original vector then it is an eigenvector and the eigenvalue is the ratio of lengths of the vector after multiplication to before multiplication.

A matrix of size N by N has N eigenvalues (and vectors) although some of the eigenvalues may be repeated. Repeated eigenvalues makes the eigenvectors indistinguishable and the result is that any combination of the relevant eigenvectors is also an eigenvector. Often the user chooses one eigenvector and specifies that the other eigenvectors are perpendicular to all the other eigenvectors.

The largest eigenvalue of a matrix can be found by iteratively applying the matrix to a trial vector - gradually the vector will become constant in direction, and will be "eigenvalue" times longer each time the iteration is applied. If you are very lucky, you may find another eigenvector by chance of course, but the smallest deviation from the true eigenvector will result in the largest eigenvector being found again.! This example uses non-degenerate matrix, unlike the example in Matrix determinant.
  package require math::linearalgebra
  set m1  { {1 1 0}  {0 1 2}  {1 0 1} }
  set v {1 1 1}
  set i 0; while {$i<200} { incr i
    set v [::math::linearalgebra::matmul $m1 $v]
    set ev [::math::linearalgebra::norm  $v]
    set v [::math::linearalgebra::unitLengthVector   $v]
  puts "Eigenvector of $m1 is approx $v, largest eigenvalue is $ev"
Eigenvector of {1 1 0} {0 1 2} {1 0 1} is approx 0.557506665977 0.702414383919 0.442493334025, largest eigenvalue is 2.2599210499

Even though the original vector is near an eigenvector the algorithm still finds the largest eigenvalue (as this is the most amplified by the matrix multiplication).

Determining other eigenvectors I may come back to later.

It is possible to be more precise about some of the descriptions above. The method described above does NOT, in general, converge to an exact eigenvalue in a bounded number of steps. There are exact methods, but they lack the lovely succinctness of the successive-approximation iteration. Also, determination of the largest (in magnitude) eigenvalue affords an opportunity to recurse to the next one by projection to a lower eigenspace. Beyond all that, it is necessary in general to account for the degeneracies that can, in principle, arise.