Dear GAP-forum, dear Massimo Redaelli,

On Wed, 2 Jul 2003, Massimo Redaelli wrote:

I'm interested in the problem of finding eigenvalues and eigenvectors of a
matrix over (extensions of) finite fields.
I was wondering what the complexity of the algorithm used in GAP is, and
what the lowest complexity known is for such an algorithm.

The current implementation of this in GAP is not particularly
sophisticated (volunteers for improving this are welcome).

Example:

gap> mat := KroneckerProduct(PseudoRandom(GL(12,13)),PseudoRandom(GL(12,13)));;
gap> Eigenvalues(GF(13^2), mat);
[ Z(13)^6, Z(13)^2, Z(13)^5, Z(13^2)^93, Z(13^2)^145, Z(13^2)^148,
  Z(13^2)^16, Z(13^2)^19, Z(13^2)^31, Z(13^2)^33, Z(13^2)^37, Z(13^2)^40,
  Z(13^2)^67, Z(13^2)^76, Z(13^2)^79 ]
gap> Eigenspaces(GF(13^2), mat);
[ <vector space over GF(13^2), with 1 generators>,
  <vector space over GF(13^2), with 1 generators>,
  <vector space over GF(13^2), with 1 generators>,
  <vector space over GF(13^2), with 1 generators>,
  <vector space over GF(13^2), with 1 generators>,
  <vector space over GF(13^2), with 1 generators>,
  <vector space over GF(13^2), with 1 generators>,
  <vector space over GF(13^2), with 1 generators>,
  <vector space over GF(13^2), with 1 generators>,
  <vector space over GF(13^2), with 1 generators>,
  <vector space over GF(13^2), with 1 generators>,
  <vector space over GF(13^2), with 1 generators>,
  <vector space over GF(13^2), with 1 generators>,
  <vector space over GF(13^2), with 1 generators>,
  <vector space over GF(13^2), with 1 generators> ]

This does the following (let n, here 144, be the number of rows of the matrix,
and q, here 13^2, the cardinality of the base field):
- computes the minimal polynomial of mat with a variation of the Gauss
algorithm (so, about O(n^3) field operations)
- factorizes this polynomial over the base field with standard variants of
the Berlekamp algorithm - and then filters out the linear factors to
find the eigenvalues in the base field (I'm not sure if this is good
in any situation, for "small" fields one should probably better evaluate
the polynomial at all field elements).
(Is this O(q*n^2) or O(n^3) field operations?)
- uses for each found eigenvalue c a standard Gauss algorithm to find
the Nullspace of mat - c*Id (so, each again in about O(n^3) field
operations).

Does this answer your question?

With best regards,

Frank Lübeck

///  Dr. Frank Lübeck, Lehrstuhl D für Mathematik, Templergraben 64,  ///
\\\                    52062 Aachen, Germany                          \\\
///  E-mail: Frank.Luebeck@Math.RWTH-Aachen.De                        ///
\\\  WWW:    http://www.math.rwth-aachen.de/~Frank.Luebeck/           \\\

Miles-Receive-Header: reply