Some elimination problems for matrices

W. Plesken, D. Robertz


New elimination methods are applied to compute polynomial relations for the coefficients of the characteristic polynomial of certain families of matrices such as tensor squares.
The problems treated here concern polynomial relations between the coefficients of characteristic polynomials of certain naturally defined varieties of matrices such as tensor squares of matrices. These questions originated from the recognition problem of finite matrix groups, cf. [L-GO'B 97] and [PlR], where the general question is addressed. The reason why we take up the problem here with different examples is that these problems provide good challenges for testing elimination techniques. They arise in sequences parametrized by n, and two quantities reflect their difficulty very well, the first being the Krull dimension and the second the number of variables. The Krull dimension grows linearly with n, the number of variables quadratically in n. We treat examples of Krull dimensions between 2 and 5 here and suggest that new elimination methods could be evaluated using these series of problems.
The methods we apply are developed in [PlR]. In particular, elimination by ``degree steering'' is the preferred strategy here. Janet bases of the same ideal are computed repeatedly for different gradings of the polynomial ring. The degrees of the variables to be eliminated are increased in each step until a Janet basis for the elimination ideal can be read off. Other techniques which come up in the course of [PlR] still wait for implementation.
All results were obtained by using implementations of the involutive basis algorithm by V. P. Gerdt and Y. A. Blinkov [Ger 05], [GBY 01]. More precisely, all Janet bases have been computed by the new open source software package ginv [ginv] in connection with its Maple interface to the Involutive package [BCG 03], which provides direct access to combinatorial tools like Hilbert series [PlR 05].

Maple worksheets: In these worksheets the Maple package Involutive [BCG 03] and the open source software package ginv [ginv] are used. The programs are available here:
[BCG 03] Y. A. Blinkov, C. F. Cid, V. P. Gerdt, W. Plesken, D. Robertz. The MAPLE Package ``Janet'': I. Polynomial Systems. In Proc. of Computer Algebra in Scientific Computing CASC 2003, edited by V. G. Ganzha, E. W. Mayr, E. V. Vorozhtsov, 31-40. Garching, Germany: Institut für Informatik, TU München, 2003. Also available together with the package from WWW (
[ginv] ginv project, cf. and
[Ger 05] V. P. Gerdt. Involutive Algorithms for Computing Gröbner Bases. In S. Cojocaru, G. Pfister, V. Ufnarovski. Computational Commutative and Non-Commutative Algebraic Geometry, NATO Science Series, IOS Press, 2005, 199-225.
[GBY 01] V. P. Gerdt, Y. A. Blinkov, D. A. Yanovich. Construction of Janet Bases, II. Polynomial Bases. In Computer Algebra in Scientific Computing CASC 2001, edited by V. G. Ganzha, E. W. Mayr, E. V. Vorozhtsov, Springer, 2001, 249-263.
[L-GO'B 97] C. R. Leedham-Green, E. O'Brien. Recognising tensor products for matrix groups. Int. J. of Algebra and Computation, 7 (1997), 541-559.
[PlR 05] W. Plesken, D. Robertz. Janet's approach to presentations and resolutions for polynomials and linear pdes. Arch. Math. 84:1 (2005), 22-37.
[PlR] W. Plesken, D. Robertz. Elimination for coefficients of special characteristic polynomials. Submitted for publication.