Computing the relations for the coefficients satisfied by the characteristic polynomial of the Kronecker product of a general

Elimination has a long tradition in commutative algebra and algebraic geometry, starting from the classical resultant methods, cf. e.g. [vdW 31, Chapter 11], nowadays getting partially replaced by Gröbner basis techniques using elimination orders, cf. [CLO 98] for a comparison of the two methods. The problem we wanted to treat came up in the context of the recognition problem for matrix groups over finite fields in [L-GO'B 97]: Decide whether a polynomial of degree

The purpose of this paper is twofold. Firstly it develops a general elimination method, called elimination by degree steering. Secondly it applies this method to the above problem for degrees 6 = 2 * 3, 8 = 2 * 4, and partially for 9 = 3 * 3. The method was found and tested in the context of Janet bases. It certainly can also be used in the context of general Gröbner bases. For our computations we use the package

For the concrete problem an essential step in the derivation is the investigation of the determinant-one case. Both, the computations and the results try to teach us something by their complexity: They do not seem to be adequate for the original problem. We therefore comment on the original problem of [L-GO'B 97] in the last section. Nevertheless, the challenge is a real good one to give a new impulse to develop new elimination techniques.

Concerning the algorithmic aspect our main point is to demonstrate how the lexicographic term ordering can be avoided. This ordering has its merits in short descriptions of elimination algorithms in the context of Gröbner bases, but in our experience it is not so convincing for hard problems, at least not for Janet bases, which are special Gröbner bases. The algorithmic idea of this paper is to approximate the lexicographic term ordering by using gradings, but only to the point that it performs the elimination and not any further. A simple, but effective lemma shows when one has reached the aim. We give some probabilistic tools to judge the difficulty of an elimination problem beforehand. Some generalities on Janet bases, in particular pointing out their advantages for the sort of calculations performed in the present paper, are also given.

We are grateful to C. Leedham-Green for pointing out the problem to us, to E. O'Brien for providing us with the background material, to V. Levandovskyy for trying to treat our examples using the conventional elimination methods in Singular, and to Mohamed Barakat for his support.

- (2,3)
- K_2_3.mws (Maple worksheet documenting the main computations)
- K_2_3.txt (the Maple worksheet as text file)
- K_2_3_min_gen.res (text file containing minimal generators over the rationals)
- K_2_3_min_gen_int.mws (Maple worksheet documenting the computation of minimal generators over the integers)
- K_2_3_min_gen_int.txt (the Maple worksheet as text file)
- K_2_3_min_gen_int.res (text file containing minimal generators over the integers)
- K_2_3_data.mws (Maple worksheet containing data about field extensions)
- K_2_3_data.txt (the Maple worksheet as text file)

- (2,4)
- K_2_4.mws (Maple worksheet documenting the main computations)
- K_2_4.txt (the Maple worksheet as text file)
- K_2_4_min_gen.res (text file containing minimal generators)
- K_2_4_data.mws (Maple worksheet containing data about field extensions)
- K_2_4_data.txt (the Maple worksheet as text file)

- (3,3)
- K_3_3.mws (Maple worksheet documenting the main computations)
- K_3_3.txt (the Maple worksheet as text file)
- K_3_3_det1.res (text file containing Janet basis for determinant 1 case)
- K_3_3_data.mws (Maple worksheet containing data about field extensions)
- K_3_3_data.txt (the Maple worksheet as text file)

In these worksheets the Maple package

[BCG 03] Y. A. Blinkov, C. F. Cid, V. P. Gerdt, W. Plesken, D. Robertz.

[BGY 01] Y. A. Blinkov, V. P. Gerdt, D. A. Yanovich.

[BCP 97] W. Bosma, J. J. Cannon, C. Playoust.

[CLO 98] D. Cox, J. Little, D. O'Shea.

[GeB 05] V. P. Gerdt, Y. A. Blinkov.

[Ger 05] V. P. Gerdt.

[ginv]

[Gla 01] S. P. Glasby.

[GPS 05] G.-M. Greuel, G. Pfister, H. Schönemann.

[L-GO'B 97] C. R. Leedham-Green, E. O'Brien.

[PlR 05] W. Plesken, D. Robertz.

[Sch 99] R. Schwingel.

[vdW 31] B. L. van der Waerden.

last modification: 16.05.08