# qsAlgorithm -- computes a solution to the unimodular matrix problem

## Synopsis

• Usage:
M = qsAlgorithm U
• Inputs:
• U, , a unimodular matrix over a polynomial ring with coefficients in QQ, ZZ, or ZZ/p for p a prime integer, or a Laurent polynomial ring over QQ or ZZ/p
• Optional inputs:
• Verbose (missing documentation) => an integer, default value 0, which controls the level of output of the method (0, 1, 2, 3, or 4)
• CheckUnimodular => , default value false, which gives the user the option to check whether the matrix is unimodular
• Outputs:
• M, , such that U*M is of the form [I \ 0] or [I \ 0]^T, where I is an identity matrix

## Description

Given a unimodular m \times \ n matrix over a polynomial ring with coefficients in QQ, ZZ, or ZZ/p with p a prime integer, this method uses the algorithm of Logar-Sturmfels to compute a solution of the unimodular matrix problem for U. In other words, this method computes a square unimodular matrix M such that if m \leq \ n then U*M is of the form [I \ 0] where I is an m \times \ m identity matrix, and if m \geq \ n then M is of the form [I \ 0]^T, where I is an n \times \ n identity matrix.

 i1 : R = ZZ/101[x,y] o1 = R o1 : PolynomialRing i2 : U = matrix{{x^2*y+1,x+y-2,2*x*y}} o2 = | x2y+1 x+y-2 2xy | 1 3 o2 : Matrix R <--- R i3 : isUnimodular U o3 = true i4 : M = qsAlgorithm U o4 = | 1 2xy -x-y+2 | | 0 0 1 | | 50x -x2y-1 -50x2-50xy-x | 3 3 o4 : Matrix R <--- R i5 : isUnimodular M o5 = true i6 : U*M o6 = | 1 0 0 | 1 3 o6 : Matrix R <--- R

The inverse of the matrix obtained by qsAlgorithm gives a completion of the original unimodular matrix U to a square invertible matrix over the polynomial ring. This completion can also be obtained directly by using the method completeMatrix.

 i7 : I = inverse M o7 = {0} | x2y+1 x+y-2 2xy | {0} | 50x 0 -1 | {1} | 0 1 0 | 3 3 o7 : Matrix R <--- R i8 : det I o8 = 1 o8 : R

The method can also be used over a Laurent polynomial ring with coefficients in QQ or ZZ/p for p a prime integer. The following example demonstrates how to construct a Laurent polynomial ring and also how to use the method on a unimodular matrix over the ring.

 i9 : R = QQ[x,Inverses => true,MonomialOrder => Lex] o9 = R o9 : PolynomialRing i10 : U = matrix{{3*x^-1-2-2*x+2*x^2, 3*x^-1-2*x,2*x},{6*x^-1+25-23*x-16*x^2+20*x^3, 6*x^-1+29-4*x-20*x^2,2+4*x+20*x^2}} o10 = | 2x2-2x-2+3x-1 -2x+3x-1 2x | | 20x3-16x2-23x+25+6x-1 -20x2-4x+29+6x-1 20x2+4x+2 | 2 3 o10 : Matrix R <--- R i11 : M = qsAlgorithm U o11 = | -2/3x+31+8x-1 -3x-1 -360x+1080x-1 | | -2/3x2+65/3x-77/3-8x-1 -2+3x-1 -360x2+360x+720-1080x-1 | | -10x-7/3 1 -180 | 3 3 o11 : Matrix R <--- R i12 : det M o12 = 180 o12 : R i13 : U*M o13 = | 1 0 0 | | 0 1 0 | 2 3 o13 : Matrix R <--- R