> < ^ From:

< ^ Subject:

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

> < [top]