Some elimination problems for matrices
Abstract:
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.
Introduction:
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:
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).
[ginv]
ginv project, cf.
http://invo.jinr.ru and
http://wwwb.math.rwth-aachen.de/Janet.
[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.