Elimination for coefficients of special characteristic polynomials

W. Plesken, D. Robertz


 

 
Abstract:
 
Computing the relations for the coefficients satisfied by the characteristic polynomial of the Kronecker product of a general n x n matrix by a general m x m matrix leads to an elimination problem which is already difficult for small values of n and m. In this article we focus on the problems for (n, m) in { (2,3), (2,4), (3,3) } and use these problems for developing and testing a new elimination technique called elimination by degree steering.
 
Introduction:
 
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 nm is the characteristic polynomial of a Kronecker product of two matrices of degrees n, m >= 2. As C. Leedham-Green pointed out, eliminating the coefficients of the polynomials of degree n and m from the expressions of the coefficients for the polynomial of degree nm in terms of these for the case n = m = 2 can be done by a short hand calculation. The next case 6 = 2 * 3 has been solved by heavy machine calculations in [Sch 99] using Magma, cf. [BCP 97]. It was noted there that no package at that time could deal with the problem as it stands. Though for instance Singular, cf. [GPS 05], can now just about tackle the problem, it still has to give up on the next one 8 = 2 * 4, though the equations can be written out in a few lines.
 
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 Involutive, cf. [BCG 03], where a powerful implementation of Janet's algorithm in C++ is available, cf. also [ginv]. Theoretical details on this algorithm can be found in [PlR 05].
 
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.
 

 
Results:
 
In these worksheets the Maple package Involutive [BCG 03] and the open source software package ginv [ginv] are used. The programs are available here: The minimal generating sets resp. the Janet basis for the case (3,3) with determinant 1 are given separately in text files. They can easily be read into Maple (for large files, use read("..."):, i.e. with a colon at the end). However, these text files can also be easily adapted to input format of e.g. Singular, Macaulay2, Magma etc.
 

 
References:
 
[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 (http://wwwb.math.rwth-aachen.de/Janet).
 
[BGY 01] Y. A. Blinkov, V. P. Gerdt, 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.
 
[BCP 97] W. Bosma, J. J. Cannon, C. Playoust. The Magma algebra system I: The user language. Journal of Symbolic Computation 24 (1997), 235-265 (http://magma.maths.usyd.edu.au/magma/MagmaInfo.html).
 
[CLO 98] D. Cox, J. Little, D. O'Shea. Using Algebraic Geometry. Springer, 1998.
 
[GeB 05] V. P. Gerdt, Y. A. Blinkov. Janet-like Gröbner bases. Computer algebra in scientific computing, 184-195, Lecture Notes in Comput. Sci., Vol. 3718, Springer, Berlin, 2005.
 
[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.
 
[ginv] ginv project, cf. http://invo.jinr.ru and http://wwwb.math.rwth-aachen.de/Janet.
 
[Gla 01] S. P. Glasby. On the tensor product of polynomials over a ring. J. Aust. Math. Soc. 71 (2001), 307-324.
 
[GPS 05] G.-M. Greuel, G. Pfister, H. Schönemann. Singular 3.0. A Computer Algebra System for Polynomial Computations. Centre for Computer Algebra, University of Kaiserslautern (2005) (http://www.singular.uni-kl.de).
 
[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.
 
[Sch 99] R. Schwingel. The Tensor Product of Polynomials. Experimental Mathematics 8 (1999), 395-397.
 
[vdW 31] B. L. van der Waerden. Moderne Algebra II. Springer, Berlin, 1931, 395-397.
 

 
last modification: 16.05.08