The RegularChains:-MatrixTools subpackage is a collection of commands to manipulate matrices of polynomials modulo regular chains.

The commands of the RegularChains:-MatrixTools subpackage are quite standard in terms of their goals: multiplication of matrices, computation of inverse, or lower echelon of a matrix. However, these commands are considered here in a non-standard context. Indeed, the coefficients of these matrices are polynomials and the computations are performed modulo (the saturated ideal of) a regular chain.

The saturated ideal of a regular chain is not necessarily prime and working modulo such ideals may involve zero-divisors. However, computing with these zero-divisors is possible following the celebrated D5 Principle, after J. Della Dora, C. Discrescenzo, and D. Duval. The idea is the following. When a zero-divisor is encountered during a computation modulo a regular chain, you can split the computations into several cases (or branches) such that in each case this zero-divisor becomes either zero or a regular element (that is, an element that is not a zero-divisor). Therefore, this zero-divisor is not an obstacle for the computations in any of these branches.

The main purpose of the commands of the RegularChains:-MatrixTools subpackage is to compute the inverse of the Jacobian matrix of a polynomial systems modulo (the saturated ideal of) a regular chain. This question arises, for example, in Hensel lifting techniques for triangular sets. See the paper Degree bounds and lifting techniques for triangular sets by E. Schost.

The following is a list of available commands.

$\mathrm{with}\left(\mathrm{RegularChains}\right)\:$

$\mathrm{with}\left(\mathrm{LinearAlgebra}\right)\:$$\mathrm{with}\left(\mathrm{MatrixTools}\right)\;$$\mathrm{with}\left(\mathrm{ChainTools}\right)\:$

$\left[\mathrm{IsZeroMatrix}\,\mathrm{JacobianMatrix}\,\mathrm{LowerEchelonForm}\,\mathrm{MatrixInverse}\,\mathrm{MatrixMultiply}\,\mathrm{MatrixOverChain}\right]$

$R≔\mathrm{PolynomialRing}\left(\left[x\,y\,z\right]\,101\right)$

$R≔\mathrm{polynomial\_ring}$

$E≔\mathrm{Empty}\left(R\right)\:$

$T≔\mathrm{Chain}\left(\left[\left(z+1\right)\left(z+2\right)\,y^2+z\,\left(x-z\right)\left(x-y\right)\right]\,E\,R\right)$

$T≔\mathrm{regular\_chain}$

$\mathrm{Equations}\left(T\,R\right)$

$\left[x^2+\left(100y+100z\right)x+zy\,y^2+z\,z^2+3z+2\right]$

$\mathrm{split}≔\mathrm{ListConstruct}\left(\left[\left(z+1\right)\left(z+2\right)\,y^2+z\,\left(x-z\right)\left(x-y\right)\right]\,E\,R\right)$

$\mathrm{split}≔\left[\mathrm{regular\_chain}\,\mathrm{regular\_chain}\,\mathrm{regular\_chain}\,\mathrm{regular\_chain}\right]$

$\mathrm{map}\left(\mathrm{Equations}\,\mathrm{split}\,R\right)$

$\left[\left[x+1\,y+1\,z+1\right]\,\left[x+1\,y+100\,z+1\right]\,\left[x+100\,y+100\,z+1\right]\,\left[x^2+\left(100y+2\right)x+99y\,y^2+99\,z+2\right]\right]$

$m≔\mathrm{Matrix}\left(\left[\left[87z^2-56z\,-73-62z^2+97z\,-10-4z^2-83z\,80+62z^2-82z\right]\,\left[-44z+71\,-17z-75\,-10z-7\,-40z+42\right]\,\left[-92-50z^3+23z^2+75z\,37+6z^3+74z^2+72z\,29-23z^3+87z^2+44z\,-61+98z^3-23z^2+10z\right]\,\left[11-8z^3-29z^2+95z\,-81-49z^3-47z^2+40z\,31+91z^3+68z^2-10z\,1-51z^3+77z^2+95z\right]\right]\right)$

$m≔\left[\begin{array}{cccc}87z^2-56z& -62z^2+97z-73& -4z^2-83z-10& 62z^2-82z+80\\ -44z+71& -17z-75& -10z-7& -40z+42\\ -50z^3+23z^2+75z-92& 6z^3+74z^2+72z+37& -23z^3+87z^2+44z+29& 98z^3-23z^2+10z-61\\ -8z^3-29z^2+95z+11& -49z^3-47z^2+40z-81& 91z^3+68z^2-10z+31& -51z^3+77z^2+95z+1\end{array}\right]$

$d≔\mathrm{Determinant}\left(m\right)$

$d≔58241707z^9+19263260z^8-145068342z^7+169363187z^6+98898633z^5-333772968z^4+57745075z^3+54218412z^2+4321491z+3727553$

$\mathrm{inv}≔\mathrm{Inverse}\left(d\,T\,R\right)$

$\mathrm{inv}≔\left[\left[\left[89z+55\,1\,\mathrm{regular\_chain}\right]\,\left[89z+55\,1\,\mathrm{regular\_chain}\right]\,\left[89z+55\,1\,\mathrm{regular\_chain}\right]\,\left[89z+55\,1\,\mathrm{regular\_chain}\right]\right]\,\left[\right]\right]$

$\mathrm{seq}\left(\mathrm{Equations}\left(\mathrm{inv}\left[1\right]\left[i\right]\left[3\right]\,R\right)\,i=1..\mathrm{nops}\left(\mathrm{inv}\left[1\right]\right)\right)$

$\left[x+1\,y+1\,z+1\right],\left[x+1\,y+100\,z+1\right],\left[x+100\,y+100\,z+1\right],\left[x^2+\left(100y+2\right)x+99y\,y^2+99\,z+2\right]$

$\mathrm{MatrixOverChain}\left(m\,T\,R\right)$

$\left[\left[\begin{array}{cccc}87z+28& 81z+51& 30z+99& 35z+57\\ 57z+71& 84z+26& 91z+94& 61z+42\\ 60z+67& 94z+26& 26z+20& 58z+68\\ 25z+21& 40z+22& 19z+37& 12z+46\end{array}\right]\,\mathrm{regular\_chain}\right]$

$\mathrm{invm}≔\mathrm{MatrixInverse}\left(m\,T\,R\right)$

$\mathrm{invm}≔\left[\left[\left[\left[\begin{array}{cccc}87& 82& 90& 70\\ 11& 13& 63& 44\\ 34& 44& 63& 91\\ 4& 17& 70& 22\end{array}\right]\,\mathrm{regular\_chain}\right]\,\left[\left[\begin{array}{cccc}87& 82& 90& 70\\ 11& 13& 63& 44\\ 34& 44& 63& 91\\ 4& 17& 70& 22\end{array}\right]\,\mathrm{regular\_chain}\right]\,\left[\left[\begin{array}{cccc}87& 82& 90& 70\\ 11& 13& 63& 44\\ 34& 44& 63& 91\\ 4& 17& 70& 22\end{array}\right]\,\mathrm{regular\_chain}\right]\,\left[\left[\begin{array}{cccc}39& 47& 34& 34\\ 46& 86& 32& 70\\ 81& 75& 84& 31\\ 57& 35& 32& 38\end{array}\right]\,\mathrm{regular\_chain}\right]\right]\,\left[\right]\right]$

$\mathrm{seq}\left(\mathrm{Equations}\left(\mathrm{invm}\left[1\right]\left[i\right]\left[2\right]\,R\right)\,i=1..\mathrm{nops}\left(\mathrm{inm}\left[1\right]\right)\right)$

$\left[x+1\,y+1\,z+1\right]$

$\mathrm{lem}≔\mathrm{LowerEchelonForm}\left(m\,T\,R\right)$

$\mathrm{lem}≔\left[\left[\left[\begin{array}{cccc}98& 0& 0& 0\\ 33& 42& 0& 0\\ 76& 90& 20& 0\\ -8z^3-29z^2+95z+11& -49z^3-47z^2+40z-81& 91z^3+68z^2-10z+31& -51z^3+77z^2+95z+1\end{array}\right]\,\mathrm{regular\_chain}\right]\,\left[\left[\begin{array}{cccc}98& 0& 0& 0\\ 33& 42& 0& 0\\ 76& 90& 20& 0\\ -8z^3-29z^2+95z+11& -49z^3-47z^2+40z-81& 91z^3+68z^2-10z+31& -51z^3+77z^2+95z+1\end{array}\right]\,\mathrm{regular\_chain}\right]\,\left[\left[\begin{array}{cccc}98& 0& 0& 0\\ 33& 42& 0& 0\\ 76& 90& 20& 0\\ -8z^3-29z^2+95z+11& -49z^3-47z^2+40z-81& 91z^3+68z^2-10z+31& -51z^3+77z^2+95z+1\end{array}\right]\,\mathrm{regular\_chain}\right]\,\left[\left[\begin{array}{cccc}78& 0& 0& 0\\ 48& 12& 0& 0\\ 68& 15& 56& 0\\ -8z^3-29z^2+95z+11& -49z^3-47z^2+40z-81& 91z^3+68z^2-10z+31& -51z^3+77z^2+95z+1\end{array}\right]\,\mathrm{regular\_chain}\right]\right]$

Aubry, P.; Lazard, D.; and Moreno Maza, M. "On the Theories of Triangular Sets." Journal of Symbolic Computation, (July/August 1999): 105-124.

Boulier, F. and Lemaire, F. "Computing Canonical Representatives of Regular Differential Ideals." Proceedings of ISSAC 2000, pp. 38-47. 2000.

Dahan, X.; Moreno Maza, M.; Schost, E.; Wu, W.; and Xie, Y. "Equiprojectable Decompositions of Zero-Dimensional Varieties." Proceedings of ICPSS 2004, pp. 69-71. 2004.

Della Dora, J.; Discrescenzo, C.; and Duval, D. "About a New Method for Computing in Algebraic Number Fields." Proceedings of EUROCAL 1985, pp. 289-290. 1985.

Hubert, E. "Notes on Triangular Sets and Triangulation-Decomposition Algorithms." Lecture Notes in Computer Science, Vol. 2630, (2003).

Kalkbrener, M. Three Contributions to Elimination Theory. PhD Thesis, University of Linz, Austria, 1991.

Lazard, D. "Solving zero-dimensional algebraic systems" J. Symb. Comp., Vol. 13, (1992): 117-133.

Moreno Maza, M. "On Triangular Decompositions of Algebraic Varieties." Proceedings of MEGA 2000. 2000.

Moreno Maza, M. and Rioboo, R. "Polynomial GCD computations over towers of algebraic extensions." In proc. of AAECC-11, Lecture Notes in Comput. Sci, Vol. 948, Springer, (1995).