This is QuillenSuslin.info, produced by Macaulay2, version 1.25.05

QuillenSuslin -- computes a free basis of a projective module over a polynomial ring
************************************************************************************

Description
===========

Using the algorithms in Logar-Sturmfels and Fabianska-Quadrat, this package
computes a free basis of a projective module over a polynomial ring with
coefficients in the rationals, integers, or a finite field.  It also provides
methods to solve related problems involving completing a unimodular matrix to a
square invertible matrix over a polynomial ring with coefficients in the
rationals, integers, or a finite field, or a Laurent polynomial ring with
coefficients in the rationals or a finite field.

For mathematical background and applications, see
  * A. Fabianska. Algorithmic analysis of presentations of groups and modules.
    http://darwin.bth.rwth-aachen.de/opus/volltexte/2009/2950/ (see
    http://darwin.bth.rwth-aachen.de/opus/volltexte/2009/2950/ ), Jan 2009.
  * T. Y. Lam. Serre's problem on projective modules. Springer Monographs in
    Mathematics. Springer-Verlag, Berlin, 2006.
  * A. Logar and B. Sturmfels. Algorithms for the Quillen-Suslin theorem. J.
    Algebra, 145(1):231-239, 1992.
  * A. Fabianska and A. Quadrat. Applications of the Quillen-Suslin theorem to
    multidimensional systems theory. Grobner bases in control theory and signal
    processing. Radon Series Comp. Appl. Math (3):23-106, 2007.

Authors
=======

  * Brett Barwick (see http://faculty.uscupstate.edu/bbarwick/ )
    <bbarwick@uscupstate.edu>
  * Branden Stone (see http://bstone.github.io/ )
    <branden.stone@gtri.gatech.edu>

Certification a gold star
=========================

Version 1.7 of this package was accepted for publication in volume 5 (see
https://msp.org/jsag/2013/5-1/ ) of The Journal of Software for Algebra and
Geometry (see https://msp.org/jsag/ ) on 2013-09-18, in the article Computing
free bases for projective modules (see https://msp.org/jsag/2013/5-1/p05.xhtml
) (DOI: 10.2140/jsag.2013.5.26 (see https://doi.org/10.2140/jsag.2013.5.26 )).
That version can be obtained from the journal (see
https://msp.org/jsag/2013/5-1/jsag-v5-n1-x05-code.zip ).

Version
=======

This documentation describes version 1.7 of QuillenSuslin.

Citation
========

If you have used this package in your research, please cite it as follows:

+-----------------------------------------------------------------------------+
|@misc{QuillenSuslinSource,                                                   |
|  title = {{QuillenSuslin: the Quillen-Suslin algorithm for bases            |
|  author = {Brett Barwick and Branden Stone},                                |
|  howpublished = {A \emph{Macaulay2} package available at                    |
|    \url{https://github.com/Macaulay2/M2/tree/master/M2/Macaulay2/           |
|}                                                                            |
|                                                                             |
|@article{QuillenSuslinArticle,                                               |
|  title = {{Computing free bases for projective modules}},                   |
|  author = {Brett Barwick and Branden Stone},                                |
|  journal = {The Journal of Software for Algebra and Geometry},              |
|  volume = {5},                                                              |
|  year = {2013},                                                             |
|}                                                                            |
|-----------------------------------------------------------------------------|
|of projective modules. Version~1.7}},                                        |
|                                                                             |
|                                                                             |
|packages}}                                                                   |
+-----------------------------------------------------------------------------+

Exports
=======

  * Functions and commands
      * changeVar -- computes a change of variables which
        make the first entry of a unimodular row monic in a specified variable
      * completeMatrix -- completes a unimodular matrix
        over a polynomial ring or Laurent polynomial ring to a square
        invertible matrix
      * computeFreeBasis -- computes a free basis of a
        projective module
      * getMaxIdeal -- computes a maximal ideal containing
        a given ideal in a polynomial ring
      * horrocks -- computes a local solution to the
        unimodular row problem over a localization at a maximal ideal
      * isProjective -- determines if a given module is
        projective with constant rank over a Noetherian ring
      * isUnimodular -- determines if a given matrix is
        unimodular
      * maxMinors -- computes the ideal generated by the
        maximal non-vanishing minors of a given matrix
      * patch -- patch together local solutions to eliminate a
        variable
      * qsAlgorithm -- computes a solution to the
        unimodular matrix problem
      * qsIsomorphism -- computes an isomorphism between
        a free module and a given projective module
  * Methods
      * "changeVar(Matrix,List)" -- see changeVar, -- computes
        a change of variables which make the first entry of a unimodular row
        monic in a specified variable
      * "completeMatrix(Matrix)" -- see completeMatrix,
        -- completes a unimodular matrix over a polynomial ring or Laurent
        polynomial ring to a square invertible matrix
      * "computeFreeBasis(Ideal)" -- see computeFreeBasis,
        -- computes a free basis of a projective module
      * "computeFreeBasis(Module)" -- see computeFreeBasis,
        -- computes a free basis of a projective module
      * "getMaxIdeal(Ideal)" -- see getMaxIdeal, -- computes
        a maximal ideal containing a given ideal in a polynomial ring
      * "getMaxIdeal(Ideal,List)" -- see getMaxIdeal, --
        computes a maximal ideal containing a given ideal in a polynomial ring
      * "horrocks(Matrix,RingElement,Ideal)" -- see horrocks,
        -- computes a local solution to the unimodular row problem over a
        localization at a maximal ideal
      * "isProjective(Module)" -- see isProjective, --
        determines if a given module is projective with constant rank over a
        Noetherian ring
      * "isUnimodular(Matrix)" -- see isUnimodular, --
        determines if a given matrix is unimodular
      * "maxMinors(Matrix)" -- see maxMinors, -- computes the
        ideal generated by the maximal non-vanishing minors of a given matrix
      * "patch(List,RingElement)" -- see patch, -- patch together
        local solutions to eliminate a variable
      * "qsAlgorithm(Matrix)" -- see qsAlgorithm, --
        computes a solution to the unimodular matrix problem
      * "qsIsomorphism(Module)" -- see qsIsomorphism, --
        computes an isomorphism between a free module and a given projective
        module
  * Symbols
      * CheckProjective -- optional input which gives
        the user the option to check whether the given module is projective
      * CheckUnimodular -- optional input which gives
        the user the option to check whether the given matrix is unimodular

For the programmer
==================

The object QuillenSuslin, is a package (Macaulay2Doc),
defined in QuillenSuslin.m2.

-------------------------------------------------------------------------------

The source of this document is in QuillenSuslin.m2:1972:0.

changeVar -- computes a change of variables which make the first entry of a unimodular row monic in a specified variable
************************************************************************************************************************

  * Usage:
        (A,B,C) = changeVar(U,L)
  * Inputs:
      * U, a matrix (Macaulay2Doc),  a unimodular row
      * L, a list (Macaulay2Doc),  the variables appearing in the
        matrix, ordered so that the first entry of the new row will become
        monic in the last variable in the list
  * Optional inputs (Macaulay2Doc),:
      * Verbose (missing documentation) => an integer (Macaulay2Doc),
        default value 0,  which controls the level of output of the method (0,
        1, 2, 3, or 4)
  * Outputs:
      * A, a matrix (Macaulay2Doc),  a unimodular matrix that
        when multiplied by the row will make the first entry monic after the
        change of variables
      * B, a matrix (Macaulay2Doc),  change of variables
      * C, a matrix (Macaulay2Doc),  inverse change of variables

Description
===========

The purpose of changeVar is to compute a unimodular matrix A and an invertible
change of variables (given as a matrix B with the inverse change of variables
given by C) so that after multiplying the given unimodular row U by A and
applying the substitution B (with sub(U*A,B)), the first entry of the new row
becomes monic in the last variable in the list L.

This method is primarily used before applying horrocks, since
horrocks requires the first entry of the unimodular row to be monic in the
given variable.
+-----------------------------------------------------------------------------+
|i1 : R = ZZ[x]                                                               |
|                                                                             |
|o1 = R                                                                       |
|                                                                             |
|o1 : PolynomialRing                                                          |
+-----------------------------------------------------------------------------+
|i2 : U = matrix{{12*x^2+20*x+7,4*x^2+12*x+5,12*x^2+44*x+35}}                 |
|                                                                             |
|o2 = | 12x2+20x+7 4x2+12x+5 12x2+44x+35 |                                    |
|                                                                             |
|             1      3                                                        |
|o2 : Matrix R  <-- R                                                         |
+-----------------------------------------------------------------------------+
|i3 : isUnimodular U                                                          |
|                                                                             |
|o3 = true                                                                    |
+-----------------------------------------------------------------------------+
|i4 : (A,B,C) = changeVar(U,{x})                                              |
|                                                                             |
|o4 = (| 3024x18+63720x17-952320x16-15154128x15+107756844x14+479809876x13+3995|
|      | -504x13-15996x12-10056x11+2511768x10+9939946x9+16560274x8-699416978x7|
|      | -3024x18-57672x17+1064640x16+12968688x15-132601500x14-202184380x13-37|
|     ------------------------------------------------------------------------|
|     606820x12-39391285472x11-58650473936x10+102412518582x9+116188662804x8+  |
|     -1487252938x6-4031638520x5-5360330891x4-1814067042x3                    |
|     30045168x12+46718607960x11-38451238904x10+23035969708x9-224995699378x8  |
|     ------------------------------------------------------------------------|
|     1077893682748x7+684018133334x6-1471276697626x5                          |
|                                                                             |
|     -573273666782x7+211144844680x6+603448147606x5+                          |
|     ------------------------------------------------------------------------|
|     -1009133585930x4-116618595557x3 1 0                          |, | x |, ||
|                                     0 1                          |          |
|     240206603531x4+23582871546x3+1  0 6x5-76x4+180x3-26x2-94x-13 |          |
|     ------------------------------------------------------------------------|
|     x |)                                                                    |
|                                                                             |
|o4 : Sequence                                                                |
+-----------------------------------------------------------------------------+
|i5 : U' = sub(U*A,B)                                                         |
|                                                                             |
|o5 = | x3+12x2+44x+35 12x2+20x+7                                             |
|     ------------------------------------------------------------------------|
|     72x7-648x6-974x5+4948x4+4028x3-5198x2-3850x-450 |                       |
|                                                                             |
|             1      3                                                        |
|o5 : Matrix R  <-- R                                                         |
+-----------------------------------------------------------------------------+
|i6 : isUnimodular U'                                                         |
|                                                                             |
|o6 = true                                                                    |
+-----------------------------------------------------------------------------+

Notice that after multiplying U by the unimodular matrix A and applying the
change of variables B (using the sub (Macaulay2Doc), command),
the first entry in U' above is now monic in x.

The order of the variables given in the list matter, as changeVar will
construct a change of variable so that the new unimodular row is monic in the
last variable of the list.

In the next example, since we are using the command changeVar(U,{x,y}) the
first entry in the row sub(U*A,B) will be monic in y.
+--------------------------------------------------------------------+
|i7 : R = ZZ/7[x,y]                                                  |
|                                                                    |
|o7 = R                                                              |
|                                                                    |
|o7 : PolynomialRing                                                 |
+--------------------------------------------------------------------+
|i8 : U = matrix{{2*x^2*y+x*y+1,3*x^2*y^2+x*y,5*x^3*y^2+x*y}}        |
|                                                                    |
|o8 = | 2x2y+xy+1 3x2y2+xy -2x3y2+xy |                               |
|                                                                    |
|             1      3                                               |
|o8 : Matrix R  <-- R                                                |
+--------------------------------------------------------------------+
|i9 : isUnimodular U                                                 |
|                                                                    |
|o9 = true                                                           |
+--------------------------------------------------------------------+
|i10 : (A,B,C) = changeVar(U,{x,y})                                  |
|                                                                    |
|o10 = (| -3 0 0 |, | y x+y |, | -x+y x |)                           |
|       | 0  1 0 |                                                   |
|       | 0  0 1 |                                                   |
|                                                                    |
|o10 : Sequence                                                      |
+--------------------------------------------------------------------+
|i11 : U' = sub(U*A,B)                                               |
|                                                                    |
|o11 = | xy2+y3-3xy-3y2-3 3x2y2-xy3+3y4+xy+y2 -2x2y3+3xy4-2y5+xy+y2 ||
|                                                                    |
|              1      3                                              |
|o11 : Matrix R  <-- R                                               |
+--------------------------------------------------------------------+
|i12 : isUnimodular U'                                               |
|                                                                    |
|o12 = true                                                          |
+--------------------------------------------------------------------+

One can also check that the inverse change of variables, C, will give the
matrix U*A, undoing the change of variables given by B.
+--------------------------------------+
|i13 : U'' = sub(U',C)                 |
|                                      |
|o13 = | x2y-3xy-3 3x2y2+xy -2x3y2+xy ||
|                                      |
|              1      3                |
|o13 : Matrix R  <-- R                 |
+--------------------------------------+
|i14 : U'' == U*A                      |
|                                      |
|o14 = true                            |
+--------------------------------------+

See also
========

  * horrocks -- computes a local solution to the unimodular
    row problem over a localization at a maximal ideal
  * substitute (Macaulay2Doc) -- substituting values for
    variables

Ways to use changeVar:
======================

  * "changeVar(Matrix,List)"

For the programmer
==================

The object changeVar, is a method function with options (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in QuillenSuslin.m2:2033:0.

CheckProjective -- optional input which gives the user the option to check whether the given module is projective
*****************************************************************************************************************

Functions with optional argument named CheckProjective:
=======================================================

  * "computeFreeBasis(...,CheckProjective=>...)" -- see computeFreeBasis,
    -- computes a free basis of a projective module
  * "qsIsomorphism(...,CheckProjective=>...)" -- see qsIsomorphism,
    -- computes an isomorphism between a free module and a given
    projective module

For the programmer
==================

The object CheckProjective, is a symbol (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in QuillenSuslin.m2:2512:0.

CheckUnimodular -- optional input which gives the user the option to check whether the given matrix is unimodular
*****************************************************************************************************************

Functions with optional argument named CheckUnimodular:
=======================================================

  * "horrocks(...,CheckUnimodular=>...)" -- see horrocks, --
    computes a local solution to the unimodular row problem over a localization
    at a maximal ideal
  * "qsAlgorithm(...,CheckUnimodular=>...)" -- see qsAlgorithm,
    -- computes a solution to the unimodular matrix problem

For the programmer
==================

The object CheckUnimodular, is a symbol (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in QuillenSuslin.m2:2517:0.

completeMatrix -- completes a unimodular matrix over a polynomial ring or Laurent polynomial ring to a square invertible matrix
*******************************************************************************************************************************

  * Usage:
        M = completeMatrix U
  * Inputs:
      * U, a matrix (Macaulay2Doc),  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 (Macaulay2Doc),:
      * Verbose (missing documentation) => an integer (Macaulay2Doc),
        default value 0,  which controls the level of output of the method (0,
        1, 2, 3, or 4)
  * Outputs:
      * M, a matrix (Macaulay2Doc),  which completes U to a
        square invertible 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 returns the
inverse of the matrix returned by qsAlgorithm.  The first m
rows or columns (depending on whether  m < n  or  m > n) of this matrix are
equal to U and the determinant of the matrix is a unit in the polynomial ring.
+--------------------------------------+
|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 = completeMatrix U             |
|                                      |
|o4 = {0} | x2y+1 x+y-2 2xy |          |
|     {0} | 50x   0     -1  |          |
|     {1} | 0     1     0   |          |
|                                      |
|             3      3                 |
|o4 : Matrix R  <-- R                  |
+--------------------------------------+
|i5 : det M                            |
|                                      |
|o5 = 1                                |
|                                      |
|o5 : 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.
+-----------------------------------------------------------------------------+
|i6 : R = QQ[x,Inverses => true,MonomialOrder => Lex]                         |
|                                                                             |
|o6 = R                                                                       |
|                                                                             |
|o6 : PolynomialRing                                                          |
+-----------------------------------------------------------------------------+
|i7 : 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+ |
|                                                                             |
|o7 = | 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                                                        |
|o7 : Matrix R  <-- R                                                         |
|-----------------------------------------------------------------------------|
|20*x^3, 6*x^-1+29-4*x-20*x^2,2+4*x+20*x^2}}                                  |
+-----------------------------------------------------------------------------+
|i8 : M = completeMatrix U                                                    |
|                                                                             |
|o8 = | 2x2-2x-2+3x-1                     -2x+3x-1                            |
|     | 20x3-16x2-23x+25+6x-1             -20x2-4x+29+6x-1                    |
|     | 2/9x4-4/9x3-2/9x2+7/9x-1/9-1/3x-1 -2/9x3+2/9x2+5/9x-1/3-1/3x-1        |
|     ------------------------------------------------------------------------|
|     2x                   |                                                  |
|     20x2+4x+2            |                                                  |
|     2/9x3-2/9x2-2/9x+1/3 |                                                  |
|                                                                             |
|             3      3                                                        |
|o8 : Matrix R  <-- R                                                         |
+-----------------------------------------------------------------------------+
|i9 : det M                                                                   |
|                                                                             |
|       1                                                                     |
|o9 = - -                                                                     |
|       3                                                                     |
|                                                                             |
|o9 : R                                                                       |
+-----------------------------------------------------------------------------+

See also
========

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

Ways to use completeMatrix:
===========================

  * "completeMatrix(Matrix)"

For the programmer
==================

The object completeMatrix, is a method function with options (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in QuillenSuslin.m2:2073:0.

computeFreeBasis -- computes a free basis of a projective module
****************************************************************

  * Usage:
        computeFreeBasis M
  * Inputs:
      * M, a module (Macaulay2Doc),  a projective module over a
        polynomial ring
  * Optional inputs (Macaulay2Doc),:
      * Verbose (missing documentation) => an integer (Macaulay2Doc),
        default value 0,  which controls the level of output of the method (0,
        1, 2, 3, or 4)
      * CheckProjective => a Boolean value (Macaulay2Doc),
        default value false,  which gives the user the option to check whether
        the given module is projective
  * Outputs:
      * a matrix (Macaulay2Doc),  a free generating set for M

Description
===========

Using the fact that every finitely generated projective module over a
polynomial ring R is isomorphic to the kernel of some surjection between free
modules, we define a surjective R-linear map from R^3 \to \ R to get a
projective module.
+--------------------------------------+
|i1 : R = QQ[x,y]                      |
|                                      |
|o1 = R                                |
|                                      |
|o1 : PolynomialRing                   |
+--------------------------------------+
|i2 : M = 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 M                   |
|                                      |
|o3 = true                             |
+--------------------------------------+

Let P be the stably-free (and hence projective) kernel with rank 2.  Notice
that the first generator is a linear combination of the other two.
+--------------------------------------------------------+
|i4 : P = ker M                                          |
|                                                        |
|o4 = image {3} | 0      2x+2y-4          2y2-4y        ||
|           {1} | 2xy    -2x2y-2xy2+4xy-2 -2xy3+4xy2-2y ||
|           {2} | -x-y+2 xy+y2-2x-4y+4    y3-4y2+4y+1   ||
|                                                        |
|                             3                          |
|o4 : R-module, submodule of R                           |
+--------------------------------------------------------+
|i5 : isProjective P                                     |
|                                                        |
|o5 = true                                               |
+--------------------------------------------------------+
|i6 : rank P                                             |
|                                                        |
|o6 = 2                                                  |
+--------------------------------------------------------+
|i7 : mingens P                                          |
|                                                        |
|o7 = {3} | 0      -2x-2y+4 -2y2+4y   |                  |
|     {1} | 2xy    2        2y        |                  |
|     {2} | -x-y+2 x2+xy-2x xy2-2xy-1 |                  |
|                                                        |
|             3      3                                   |
|o7 : Matrix R  <-- R                                    |
+--------------------------------------------------------+
|i8 : syz mingens P                                      |
|                                                        |
|o8 = {3} | -1     |                                     |
|     {4} | -y2+2y |                                     |
|     {5} | x+y-2  |                                     |
|                                                        |
|             3      1                                   |
|o8 : Matrix R  <-- R                                    |
+--------------------------------------------------------+

Notice that the native command mingens (Macaulay2Doc), does not
return a free generating set.  We can use computeFreeBasis to construct a free
generating set for P.
+-----------------------------------------+
|i9 : B = computeFreeBasis(P)             |
|                                         |
|o9 = {3} | -2x-2y+4        -2y2+4y      ||
|     {1} | 2x2y+2xy2-4xy+2 2xy3-4xy2+2y ||
|     {2} | -xy-y2+2x+4y-4  -y3+4y2-4y-1 ||
|                                         |
|             3      2                    |
|o9 : Matrix R  <-- R                     |
+-----------------------------------------+
|i10 : image B == P                       |
|                                         |
|o10 = true                               |
+-----------------------------------------+
|i11 : syz B                              |
|                                         |
|o11 = 0                                  |
|                                         |
|              2                          |
|o11 : Matrix R  <-- 0                    |
+-----------------------------------------+

Ways to use computeFreeBasis:
=============================

  * "computeFreeBasis(Ideal)"
  * "computeFreeBasis(Module)"

For the programmer
==================

The object computeFreeBasis, is a method function with options (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in QuillenSuslin.m2:2116:0.

getMaxIdeal -- computes a maximal ideal containing a given ideal in a polynomial ring
*************************************************************************************

  * Usage:
        M = getMaxIdeal I
        M = getMaxIdeal(I,L)
  * Inputs:
      * I, an ideal (Macaulay2Doc),  an ideal of a polynomial ring
        over QQ, ZZ, or ZZ/p for p a prime integer.
      * L, a list (Macaulay2Doc),  a subset of the variables of the
        ring.  This list must contain the variables that appear in the ideal I.
        By default, L is assumed to be the list of variables in the ring.
  * Optional inputs (Macaulay2Doc),:
      * Verbose (missing documentation) => an integer (Macaulay2Doc),
        default value 0,  which controls the level of output of the method (0,
        1, 2, 3, or 4).
  * Outputs:
      * M, an ideal (Macaulay2Doc),  maximal with respect to the
        variables in L.

Description
===========

In absence of an input list, getMaxIdeal yields a maximal ideal containing the
input ideal I.
+---------------------------------------------+
|i1 : R = ZZ/3[x,y]                           |
|                                             |
|o1 = R                                       |
|                                             |
|o1 : PolynomialRing                          |
+---------------------------------------------+
|i2 : I = ideal(x*(x-1)*(x-2)*y*(y-1)*(y-2)+1)|
|                                             |
|            3 3    3       3                 |
|o2 = ideal(x y  - x y - x*y  + x*y + 1)      |
|                                             |
|o2 : Ideal of R                              |
+---------------------------------------------+
|i3 : J = getMaxIdeal I                       |
|                                             |
|                    2                        |
|o3 = ideal (x - y, y  + 1)                   |
|                                             |
|o3 : Ideal of R                              |
+---------------------------------------------+
|i4 : isSubset(I,J)                           |
|                                             |
|o4 = true                                    |
+---------------------------------------------+

The function isSubset shows that I is contained in our new ideal.  To see that
J is indeed maximal, consider the codimension and the minimal primes.
+----------------------------+
|i5 : codim J                |
|                            |
|o5 = 2                      |
+----------------------------+
|i6 : P = minimalPrimes J    |
|                            |
|                     2      |
|o6 = {ideal (x - y, y  + 1)}|
|                            |
|o6 : List                   |
+----------------------------+
|i7 : J == P_0               |
|                            |
|o7 = true                   |
+----------------------------+

The optional list argument allows us to restrict our maximal ideal to a
polynomial ring defined by a subset of the variables of the ambient ring.  Note
that the list must contain the variables that appear in the generators of I.
+--------------------------------+
|i8 : R = ZZ[x,y,z,a,b,c]        |
|                                |
|o8 = R                          |
|                                |
|o8 : PolynomialRing             |
+--------------------------------+
|i9 : I = ideal(27,x^2+1)        |
|                                |
|                 2              |
|o9 = ideal (27, x  + 1)         |
|                                |
|o9 : Ideal of R                 |
+--------------------------------+
|i10 : J = getMaxIdeal(I,{x,y,z})|
|                                |
|                    2           |
|o10 = ideal (z, y, x  + 1, 3)   |
|                                |
|o10 : Ideal of R                |
+--------------------------------+
|i11 : isSubset(I,J)             |
|                                |
|o11 = true                      |
+--------------------------------+

Ways to use getMaxIdeal:
========================

  * "getMaxIdeal(Ideal)"
  * "getMaxIdeal(Ideal,List)"

For the programmer
==================

The object getMaxIdeal, is a method function with options (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in QuillenSuslin.m2:2163:0.

horrocks -- computes a local solution to the unimodular row problem over a localization at a maximal ideal
**********************************************************************************************************

  * Usage:
        U = horrocks(f,var,M)
  * Inputs:
      * f, a matrix (Macaulay2Doc),  a unimodular matrix over a
        polynomial ring with coefficients in QQ, ZZ, or ZZ/p for p a prime
        integer
      * var, a ring element (Macaulay2Doc),  a variable in
        the polynomial ring
      * M, an ideal (Macaulay2Doc),  a maximal ideal in the
        polynomial ring excluding the given variable
  * Optional inputs (Macaulay2Doc),:
      * Verbose, => an integer (Macaulay2Doc),
        default value 0,  which controls the level of output of the method (0,
        1, 2, 3, or 4)
      * CheckUnimodular => a Boolean value (Macaulay2Doc),
        default value false,  which gives the user the option to test whether
        the given matrix is unimodular
  * Outputs:
      * U, a matrix (Macaulay2Doc),  a local solution to the
        unimodular row problem

Description
===========

Given a unimodular row f over a polynomial ring  R = S[x_1,\ldots,x_{n-1}][x_n]
(where S is either QQ, ZZ, or ZZ/p) and a maximal ideal M in
S[x_1,\ldots,x_{n-1}] , horrocks computes a unimodular matrix U over
(S[x_1,\ldots,x_{n-1}]_M)[x_n]  which solves the unimodular row problem for f.
That is, f*U is of the form |1 0 ... 0|.
+-----------------------------------------------------------------------------+
|i1 : S = ZZ[x]                                                               |
|                                                                             |
|o1 = S                                                                       |
|                                                                             |
|o1 : PolynomialRing                                                          |
+-----------------------------------------------------------------------------+
|i2 : M = ideal(2,x)                                                          |
|                                                                             |
|o2 = ideal (2, x)                                                            |
|                                                                             |
|o2 : Ideal of S                                                              |
+-----------------------------------------------------------------------------+
|i3 : R = ZZ[x,y]                                                             |
|                                                                             |
|o3 = R                                                                       |
|                                                                             |
|o3 : PolynomialRing                                                          |
+-----------------------------------------------------------------------------+
|i4 : f = matrix{{y^2+x^2*y+x,3*y+1,x^2}}                                     |
|                                                                             |
|o4 = | x2y+y2+x 3y+1 x2 |                                                    |
|                                                                             |
|             1      3                                                        |
|o4 : Matrix R  <-- R                                                         |
+-----------------------------------------------------------------------------+
|i5 : U = horrocks(f,y,M)                                                     |
|                                                                             |
|o5 = | (-9)/(3x2-9x-1)       (9y+3)/(3x2-9x-1)                               |
|     | (3x2+3y-1)/(3x2-9x-1) (-3x2y-3y2-3x)/(3x2-9x-1)                       |
|     | 0                     0                                               |
|     ------------------------------------------------------------------------|
|     9x2/(3x2-9x-1)            |                                             |
|     (-3x4-3x2y+x2)/(3x2-9x-1) |                                             |
|     1                         |                                             |
|                                                                             |
|                    3             3                                          |
|o5 : Matrix (frac R)  <-- (frac R)                                           |
+-----------------------------------------------------------------------------+

It is worth noting that M can be chosen to be an extension of a maximal ideal
from  S[x_1,\ldots,x_{n-1}] to the ring R.  We repeat the above example with
this convention.
+-----------------------------------------------------------------------------+
|i6 : R = ZZ[x,y]                                                             |
|                                                                             |
|o6 = R                                                                       |
|                                                                             |
|o6 : PolynomialRing                                                          |
+-----------------------------------------------------------------------------+
|i7 : f = matrix{{y^2+x^2*y+x,3*y+1,x^2}}                                     |
|                                                                             |
|o7 = | x2y+y2+x 3y+1 x2 |                                                    |
|                                                                             |
|             1      3                                                        |
|o7 : Matrix R  <-- R                                                         |
+-----------------------------------------------------------------------------+
|i8 : M = ideal(2,x)                                                          |
|                                                                             |
|o8 = ideal (2, x)                                                            |
|                                                                             |
|o8 : Ideal of R                                                              |
+-----------------------------------------------------------------------------+
|i9 : U = horrocks(f,y,M)                                                     |
|                                                                             |
|o9 = | (-9)/(3x2-9x-1)       (9y+3)/(3x2-9x-1)                               |
|     | (3x2+3y-1)/(3x2-9x-1) (-3x2y-3y2-3x)/(3x2-9x-1)                       |
|     | 0                     0                                               |
|     ------------------------------------------------------------------------|
|     9x2/(3x2-9x-1)            |                                             |
|     (-3x4-3x2y+x2)/(3x2-9x-1) |                                             |
|     1                         |                                             |
|                                                                             |
|                    3             3                                          |
|o9 : Matrix (frac R)  <-- (frac R)                                           |
+-----------------------------------------------------------------------------+

One can check that U is unimodular over  (\mathbb{Z}[x]_{(2,x)})[y]  (i.e. the
determinant is a unit in this ring), and that U solves the unimodular row
problem for f (i.e. f*U = |1 0 0|).
+------------------------------------+
|i10 : det U                         |
|                                    |
|           -3                       |
|o10 = ------------                  |
|        2                           |
|      3x  - 9x - 1                  |
|                                    |
|o10 : frac R                        |
+------------------------------------+
|i11 : f*U                           |
|                                    |
|o11 = | 1 0 0 |                     |
|                                    |
|                     1             3|
|o11 : Matrix (frac R)  <-- (frac R) |
+------------------------------------+

Before applying horrocks one must guarantee that the first entry in the
unimodular row is monic in the given variable.  This can be accomplished, for
example, by using the method changeVar.  One can also use the
method getMaxIdeal, to construct a maximal ideal to localize
at.  We demonstrate the use of these methods in the next example.
+-----------------------------------------------------------------------------+
|i12 : R = ZZ/11[x,y]                                                         |
|                                                                             |
|o12 = R                                                                      |
|                                                                             |
|o12 : PolynomialRing                                                         |
+-----------------------------------------------------------------------------+
|i13 : f = matrix{{4*x^2-4*x*y+2*y^2+3*x-2*y+3,-2*x^2+2*x*y-4*y^2-2*x-2,-5*x^2|
|                                                                             |
|o13 = | 4x2-4xy+2y2+3x-2y+3 -2x2+2xy-4y2-2x-2 -5x2-4xy-5y2+4x+3y+5 |         |
|                                                                             |
|              1      3                                                       |
|o13 : Matrix R  <-- R                                                        |
|-----------------------------------------------------------------------------|
|-4*x*y-5*y^2+4*x+3*y+5}}                                                     |
+-----------------------------------------------------------------------------+
|i14 : isUnimodular f                                                         |
|                                                                             |
|o14 = true                                                                   |
+-----------------------------------------------------------------------------+
|i15 : M = getMaxIdeal(ideal(0_R),{x})                                        |
|                                                                             |
|o15 = ideal x                                                                |
|                                                                             |
|o15 : Ideal of R                                                             |
+-----------------------------------------------------------------------------+
|i16 : (N,subs,invSubs) = changeVar(f,{x,y})                                  |
|                                                                             |
|o16 = (| -5 0 0 |, | x y |, | x y |)                                         |
|       | 0  1 0 |                                                            |
|       | 0  0 1 |                                                            |
|                                                                             |
|o16 : Sequence                                                               |
+-----------------------------------------------------------------------------+
|i17 : g = sub(f*N,subs)                                                      |
|                                                                             |
|o17 = | 2x2-2xy+y2-4x-y-4 -2x2+2xy-4y2-2x-2 -5x2-4xy-5y2+4x+3y+5 |           |
|                                                                             |
|              1      3                                                       |
|o17 : Matrix R  <-- R                                                        |
+-----------------------------------------------------------------------------+
|i18 : U = horrocks(g,y,M)                                                    |
|                                                                             |
|o18 = | (4x2-3xy-x-2y-2)/(x4+2x2+4x-3)                                       |
|      | (-2x2+2xy+4x+5y)/(x4+2x2+4x-3)                                       |
|      | 0                                                                    |
|      -----------------------------------------------------------------------|
|      (-4x3+4x2y+3xy2-3x2-xy+2y2-3x+1)/(x4+2x2+4x-3)                         |
|      (-4x3+4x2y-2xy2-2x2+xy-5y2-5x+5y-2)/(x4+2x2+4x-3)                      |
|      0                                                                      |
|      -----------------------------------------------------------------------|
|      (-2x4+x3y-3x2y2-4xy3+x3-3x2y-4xy2+y3-4x2-4xy-4y2+2x+5y-1)/(x4+2x2+4x-3)|
|      (x4+2x3y-2x2y2-xy3-5x3-5x2y+xy2+3y3+5x2+2xy-4y2+2x-3y)/(x4+2x2+4x-3)   |
|      1                                                                      |
|      -----------------------------------------------------------------------|
|      |                                                                      |
|      |                                                                      |
|      |                                                                      |
|                                                                             |
|                     3             3                                         |
|o18 : Matrix (frac R)  <-- (frac R)                                          |
+-----------------------------------------------------------------------------+

Again we can check that U is unimodular over
((\mathbb{Z}/11\mathbb{Z})[x]_{(x)})[y]  and that U solves the unimodular row
problem for g.
+------------------------------------+
|i19 : det U                         |
|                                    |
|           - 2x - 5                 |
|o19 = -----------------             |
|       4     2                      |
|      x  + 2x  + 4x - 3             |
|                                    |
|o19 : frac R                        |
+------------------------------------+
|i20 : g*U                           |
|                                    |
|o20 = | 1 0 0 |                     |
|                                    |
|                     1             3|
|o20 : Matrix (frac R)  <-- (frac R) |
+------------------------------------+

Caveat
======

horrocks may give undesired results if the given ideal is not actually maximal.

See also
========

  * changeVar -- computes a change of variables which make
    the first entry of a unimodular row monic in a specified variable
  * getMaxIdeal -- computes a maximal ideal containing a
    given ideal in a polynomial ring

Ways to use horrocks:
=====================

  * "horrocks(Matrix,RingElement,Ideal)"

For the programmer
==================

The object horrocks, is a method function with options (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in QuillenSuslin.m2:2241:0.

isProjective -- determines if a given module is projective with constant rank over a Noetherian ring
****************************************************************************************************

  * Usage:
        isProjective M
  * Inputs:
      * M, a module (Macaulay2Doc),  a finitely generated module
        over a Noetherian ring.
  * Outputs:
      * a Boolean value (Macaulay2Doc),

Description
===========

This method determines if the given R-module is projective with constant rank
by considering the ideal of minors of its presentation matrix.  In particular,
if \phi is the presentation matrix of the module M, let I_t(\phi) be the ideal
in R generated by the t \times\ t minors of \phi.  If there exists an r such
that I_r(\phi) = R and I_{r+1}(\phi) = 0, then we know that M is necessarily
projective of constant rank (see Proposition 1.4.10 of Bruns-Herzog below).
The method isProjective calls on maxMinors, to compute the
ideal of minors I_r(\phi) such that I_r(\phi) \neq 0 and I_{r+1}(\phi) = 0. If
I_r(\phi) is the whole ring, then the module M is projective with constant
rank.

Reference:
  * W. Bruns and J. Herzog. Cohen-Macaulay Rings. Cambridge Studies in Advanced
    Mathematics, 39. Cambridge University Press, Cambridge, 1993. xii+403 pp.
    ISBN: 0-521-41068-1.
+---------------------------------------------------+
|i1 : R = QQ[x,y,z]                                 |
|                                                   |
|o1 = R                                             |
|                                                   |
|o1 : PolynomialRing                                |
+---------------------------------------------------+
|i2 : P = 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 : isProjective ker P                            |
|                                                   |
|o3 = true                                          |
+---------------------------------------------------+
|i4 : M = matrix{{-y,-z^2,0},{x,0,-z^2},{0,x^2,x*y}}|
|                                                   |
|o4 = | -y -z2 0   |                                |
|     | x  0   -z2 |                                |
|     | 0  x2  xy  |                                |
|                                                   |
|             3      3                              |
|o4 : Matrix R  <-- R                               |
+---------------------------------------------------+
|i5 : isProjective cokernel M                       |
|                                                   |
|o5 = false                                         |
+---------------------------------------------------+
|i6 : I = ideal(x^2,x*y,z^2)                        |
|                                                   |
|             2        2                            |
|o6 = ideal (x , x*y, z )                           |
|                                                   |
|o6 : Ideal of R                                    |
+---------------------------------------------------+
|i7 : isProjective module I                         |
|                                                   |
|o7 = false                                         |
+---------------------------------------------------+
|i8 : isProjective R^3                              |
|                                                   |
|o8 = true                                          |
+---------------------------------------------------+
|i9 : isProjective module ideal x                   |
|                                                   |
|o9 = true                                          |
+---------------------------------------------------+

Caveat
======

If the method outputs false, this only implies the module in question is not
projective with constant rank.  However, if the ring is a domain, then all
finitely generated projective modules have constant rank.  In this scenario,
isProjective outputs true if and only if the module is projective.

See also
========

  * maxMinors -- computes the ideal generated by the maximal
    non-vanishing minors of a given matrix

Ways to use isProjective:
=========================

  * "isProjective(Module)"

For the programmer
==================

The object isProjective, is a method function (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in QuillenSuslin.m2:2288:0.

isUnimodular -- determines if a given matrix is unimodular
**********************************************************

  * Usage:
        isUnimodular M
  * Inputs:
      * M, a matrix (Macaulay2Doc),  a matrix over a polynomial
        ring
  * Outputs:
      * a Boolean value (Macaulay2Doc),

Description
===========

An  m \times \ n  matrix over a polynomial ring is unimodular if its maximal
minors generate the entire ring.  If  m \leq \ n  then this property is
equivalent to the matrix being right-invertible and if  m \geq \ n  then this
property is equivalent to the matrix being left-invertible.
+------------------------------------------------------------+
|i1 : R = QQ[x,y,z]                                          |
|                                                            |
|o1 = R                                                      |
|                                                            |
|o1 : PolynomialRing                                         |
+------------------------------------------------------------+
|i2 : A = 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 A                                         |
|                                                            |
|o3 = true                                                   |
+------------------------------------------------------------+
|i4 : B = matrix{{x*y+x*z+y*z-1},{x^2+y^2}, {y^2+z^2}, {z^2}}|
|                                                            |
|o4 = | xy+xz+yz-1 |                                         |
|     | x2+y2      |                                         |
|     | y2+z2      |                                         |
|     | z2         |                                         |
|                                                            |
|             4      1                                       |
|o4 : Matrix R  <-- R                                        |
+------------------------------------------------------------+
|i5 : isUnimodular B                                         |
|                                                            |
|o5 = true                                                   |
+------------------------------------------------------------+
|i6 : I = ideal(x^2,x*y,z^2)                                 |
|                                                            |
|             2        2                                     |
|o6 = ideal (x , x*y, z )                                    |
|                                                            |
|o6 : Ideal of R                                             |
+------------------------------------------------------------+
|i7 : isUnimodular presentation module I                     |
|                                                            |
|o7 = false                                                  |
+------------------------------------------------------------+

See also
========

  * minors (Macaulay2Doc) -- ideal generated by
    minors

Ways to use isUnimodular:
=========================

  * "isUnimodular(Matrix)"

For the programmer
==================

The object isUnimodular, is a method function (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in QuillenSuslin.m2:2317:0.

maxMinors -- computes the ideal generated by the maximal non-vanishing minors of a given matrix
***********************************************************************************************

  * Usage:
        maxMinors M
  * Inputs:
      * M, a matrix (Macaulay2Doc),  with entries in a ring R.
  * Outputs:
      * an ideal (Macaulay2Doc), the ideal generated by maximal
        non-vanishing minors of the matrix M.

Description
===========

Let I_t(M) be the ideal in R generated by the t \times\ t minors of M.  If
there exists an r such that I_r(M) is non-zero and I_{r+1}(\phi) = 0, then
maxMinors M gives I_r(M).
+------------------------------------+
|i1 : R = QQ[x,y]                    |
|                                    |
|o1 = R                              |
|                                    |
|o1 : PolynomialRing                 |
+------------------------------------+
|i2 : M = matrix{{x,0},{-y,x},{0,-y}}|
|                                    |
|o2 = | x  0  |                      |
|     | -y x  |                      |
|     | 0  -y |                      |
|                                    |
|             3      2               |
|o2 : Matrix R  <-- R                |
+------------------------------------+
|i3 : maxMinors M                    |
|                                    |
|             2         2            |
|o3 = ideal (x , -x*y, y )           |
|                                    |
|o3 : Ideal of R                     |
+------------------------------------+

This method returns the unit ideal as the ideal of maximal minors of the zero
matrix.
+----------------------+
|i4 : N = matrix{{0_R}}|
|                      |
|o4 = 0                |
|                      |
|             1      1 |
|o4 : Matrix R  <-- R  |
+----------------------+
|i5 : maxMinors N      |
|                      |
|o5 = ideal 1          |
|                      |
|o5 : Ideal of R       |
+----------------------+

See also
========

  * minors (Macaulay2Doc) -- ideal generated by
    minors

Ways to use maxMinors:
======================

  * "maxMinors(Matrix)"

For the programmer
==================

The object maxMinors, is a method function (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in QuillenSuslin.m2:2348:0.

patch -- patch together local solutions to eliminate a variable
***************************************************************

  * Usage:
        patch(L,var)
  * Inputs:
      * L, a list (Macaulay2Doc),  a list of local solutions to the
        unimodular row problem for some unimodular row f
      * var, a ring element (Macaulay2Doc),  the current
        variable to eliminate
  * Optional inputs (Macaulay2Doc),:
      * Verbose (missing documentation) => an integer (Macaulay2Doc),
        default value 0,  which controls the level of output of the method (0,
        1, 2, 3, or 4)
  * Outputs:
      * a matrix (Macaulay2Doc),  a unimodular matrix U so that
        f*U is the same as evaluating f when var = 0

Description
===========

Given a unimodular row f over a polynomial ring  R[x_1,\ldots,x_n] (where  R
is either QQ, ZZ, or ZZ/p) one can compute a collection of matrices
\{U_i\}^r_{i=1} and maximal ideals  m_1,\ldots,m_r so that:

1. Each  U_i  is unimodular over  (R[x_1,\ldots,x_{n-1}]_{m_i})[x_n] ,

2. Each  U_i solves the unimodular row problem for f in
(R[x_1,\ldots,x_{n-1}]_{m_i})[x_n], and

3. Letting  d_i  denote the common denominator of the entries of U_i  in
R[x_1,\ldots,x_{n-1}] , we have  (d_1,\ldots,d_r) = R[x_1,\ldots,x_{n-1}].

One can accomplish this, for example, by repeatedly using getMaxIdeal,
and horrocks, as in the following example.
+-----------------------------------------------------------------------------+
|i1 : R = ZZ[x,y]                                                             |
|                                                                             |
|o1 = R                                                                       |
|                                                                             |
|o1 : PolynomialRing                                                          |
+-----------------------------------------------------------------------------+
|i2 : f = matrix{{y^3+2*x*y^2,3*y+1,x^3}}                                     |
|                                                                             |
|o2 = | 2xy2+y3 3y+1 x3 |                                                     |
|                                                                             |
|             1      3                                                        |
|o2 : Matrix R  <-- R                                                         |
+-----------------------------------------------------------------------------+
|i3 : isUnimodular f                                                          |
|                                                                             |
|o3 = true                                                                    |
+-----------------------------------------------------------------------------+
|i4 : m1 = getMaxIdeal(ideal(0_R),{x})                                        |
|                                                                             |
|o4 = ideal (2, x)                                                            |
|                                                                             |
|o4 : Ideal of R                                                              |
+-----------------------------------------------------------------------------+
|i5 : L1 = horrocks(f,y,m1)                                                   |
|                                                                             |
|o5 = | 27/(6x-1)                  (-27y-9)/(6x-1)                            |
|     | (-18xy-9y2+6x+3y-1)/(6x-1) (18xy2+9y3)/(6x-1)                         |
|     | 0                          0                                          |
|     ------------------------------------------------------------------------|
|     (-27x3)/(6x-1)                   |                                      |
|     (18x4y+9x3y2-6x4-3x3y+x3)/(6x-1) |                                      |
|     1                                |                                      |
|                                                                             |
|                    3             3                                          |
|o5 : Matrix (frac R)  <-- (frac R)                                           |
+-----------------------------------------------------------------------------+
|i6 : m2 = getMaxIdeal(sub(ideal(6*x-1),R),{x})                               |
|                                                                             |
|o6 = ideal (x - 1, 5)                                                        |
|                                                                             |
|o6 : Ideal of R                                                              |
+-----------------------------------------------------------------------------+
|i7 : L2 = horrocks(f,y,m2)                                                   |
|                                                                             |
|o7 = | 0    0          1             |                                       |
|     | 0    1          0             |                                       |
|     | 1/x3 (-3y-1)/x3 (-2xy2-y3)/x3 |                                       |
|                                                                             |
|                    3             3                                          |
|o7 : Matrix (frac R)  <-- (frac R)                                           |
+-----------------------------------------------------------------------------+
|i8 : sub(ideal(6*x-1,x^3),R) == ideal(1_R)                                   |
|                                                                             |
|o8 = true                                                                    |
+-----------------------------------------------------------------------------+
|i9 : L = {L1,L2}                                                             |
|                                                                             |
|o9 = {| 27/(6x-1)                  (-27y-9)/(6x-1)                           |
|      | (-18xy-9y2+6x+3y-1)/(6x-1) (18xy2+9y3)/(6x-1)                        |
|      | 0                          0                                         |
|     ------------------------------------------------------------------------|
|     (-27x3)/(6x-1)                   |, | 0    0          1             |}  |
|     (18x4y+9x3y2-6x4-3x3y+x3)/(6x-1) |  | 0    1          0             |   |
|     1                                |  | 1/x3 (-3y-1)/x3 (-2xy2-y3)/x3 |   |
|                                                                             |
|o9 : List                                                                    |
+-----------------------------------------------------------------------------+

Once we have constructed a list L of local solutions of the unimodular row
problem for f, we can use patch to create a matrix U so that the product fU is
the same as f evaluated at y=0.
+-----------------------------------------------------------------------------+
|i10 : U = patch(L,y)                                                         |
|                                                                             |
|o10 = | 45349632x8y3+7558272x7y3+1259712x6y3+419904x6y2-1944x3y2-648x3y      |
|      | -30233088x9y4-15116544x8y5+10077696x9y3-2519424x7y5-419904x6y5-      |
|      | -10077696x6y3-93312x4y2                                              |
|      -----------------------------------------------------------------------|
|      +3y+1                                                                  |
|      279936x7y3+93312x7y2+1296x4y3+648x3y4-2xy2-y3                          |
|                                                                             |
|      -----------------------------------------------------------------------|
|      2916x2y+486xy+81y                             0 |                      |
|      -1944x3y2-972x2y3+648x3y-162xy3-27y3+9y2-3y+1 0 |                      |
|      -648y                                         1 |                      |
|                                                                             |
|              3      3                                                       |
|o10 : Matrix R  <-- R                                                        |
+-----------------------------------------------------------------------------+
|i11 : isUnimodular U                                                         |
|                                                                             |
|o11 = true                                                                   |
+-----------------------------------------------------------------------------+
|i12 : f*U                                                                    |
|                                                                             |
|o12 = | 0 1 x3 |                                                             |
|                                                                             |
|              1      3                                                       |
|o12 : Matrix R  <-- R                                                        |
+-----------------------------------------------------------------------------+
|i13 : sub(f,{y => 0})                                                        |
|                                                                             |
|o13 = | 0 1 x3 |                                                             |
|                                                                             |
|              1      3                                                       |
|o13 : Matrix R  <-- R                                                        |
+-----------------------------------------------------------------------------+

See also
========

  * getMaxIdeal -- computes a maximal ideal containing a
    given ideal in a polynomial ring
  * horrocks -- computes a local solution to the unimodular
    row problem over a localization at a maximal ideal

Ways to use patch:
==================

  * "patch(List,RingElement)"

For the programmer
==================

The object patch, is a method function with options (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in QuillenSuslin.m2:2394:0.

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

  * Usage:
        M = qsAlgorithm U
  * Inputs:
      * U, a matrix (Macaulay2Doc),  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 (Macaulay2Doc),:
      * Verbose (missing documentation) => an integer (Macaulay2Doc),
        default value 0,  which controls the level of output of the method (0,
        1, 2, 3, or 4)
      * CheckUnimodular => a Boolean value (Macaulay2Doc),
        default value false,  which gives the user the option to check whether
        the matrix is unimodular
  * Outputs:
      * M, a matrix (Macaulay2Doc),  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+|
|                                                                             |
|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                                                        |
|-----------------------------------------------------------------------------|
|20*x^3, 6*x^-1+29-4*x-20*x^2,2+4*x+20*x^2}}                                  |
+-----------------------------------------------------------------------------+
|i11 : M = qsAlgorithm U                                                      |
|                                                                             |
|o11 = | -2/3x3+62/3x2+20/3x-31-8x-1        -2x+3x-1       6x-18x-1        |  |
|      | -2/3x4+64/3x3-44/3x2-27x+77/3+8x-1 -2x2+2x+2-3x-1 6x2-6x-12+18x-1 |  |
|      | -1/3x2+1/3x+1/3                    0              3               |  |
|                                                                             |
|              3      3                                                       |
|o11 : Matrix R  <-- R                                                        |
+-----------------------------------------------------------------------------+
|i12 : det M                                                                  |
|                                                                             |
|o12 = -3                                                                     |
|                                                                             |
|o12 : R                                                                      |
+-----------------------------------------------------------------------------+
|i13 : U*M                                                                    |
|                                                                             |
|o13 = | 1 0 0 |                                                              |
|      | 0 1 0 |                                                              |
|                                                                             |
|              2      3                                                       |
|o13 : Matrix R  <-- R                                                        |
+-----------------------------------------------------------------------------+

See also
========

  * completeMatrix -- completes a unimodular matrix over
    a polynomial ring or Laurent polynomial ring to a square invertible matrix

Ways to use qsAlgorithm:
========================

  * "qsAlgorithm(Matrix)"

For the programmer
==================

The object qsAlgorithm, is a method function with options (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in QuillenSuslin.m2:2449:0.

qsIsomorphism -- computes an isomorphism between a free module and a given projective module
********************************************************************************************

  * Usage:
        qsIsomorphism M
  * Inputs:
      * M, a module (Macaulay2Doc),  a projective module 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 (Macaulay2Doc),:
      * Verbose (missing documentation) => an integer (Macaulay2Doc),
        default value 0,  which controls the level of output of the method (0,
        1, 2, 3, or 4)
      * CheckProjective => a Boolean value (Macaulay2Doc),
        default value false,  which gives the user the option to check whether
        the module is projective
  * Outputs:
      * M, a matrix (Macaulay2Doc),  which is an isomorphism from
        a free module to the given projective module M

Description
===========

Given a projective module M over a polynomial ring with coefficients in QQ, ZZ,
or ZZ/p with p a prime integer, this method uses algorithms of Logar-Sturmfels
and Fabianska-Quadrat to compute an isomorphism from a free module F to the
projective module M.  The following gives examples of constructing such
isomorphisms in the cases where the module is a cokernel, kernel, image, or
coimage of a unimodular matrix.
+----------------------------------------------------------------------------+
|i1 : R = ZZ/101[x,y,z]                                                      |
|                                                                            |
|o1 = R                                                                      |
|                                                                            |
|o1 : PolynomialRing                                                         |
+----------------------------------------------------------------------------+
|i2 : f = 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 f                                                         |
|                                                                            |
|o3 = true                                                                   |
+----------------------------------------------------------------------------+
|i4 : P1 = coker transpose f -- Construct the cokernel of the transpose of f.|
|                                                                            |
|o4 = cokernel {-3} | x2y+1 |                                                |
|              {-1} | x+y-2 |                                                |
|              {-2} | 2xy   |                                                |
|                                                                            |
|                            3                                               |
|o4 : R-module, quotient of R                                                |
+----------------------------------------------------------------------------+
|i5 : isProjective P1                                                        |
|                                                                            |
|o5 = true                                                                   |
+----------------------------------------------------------------------------+
|i6 : rank P1                                                                |
|                                                                            |
|o6 = 2                                                                      |
+----------------------------------------------------------------------------+
|i7 : phi1 = qsIsomorphism P1                                                |
|                                                                            |
|o7 = {-3} | 50x 0 |                                                         |
|     {-1} | 0   1 |                                                         |
|     {-2} | -1  0 |                                                         |
|                                                                            |
|                    2                                                       |
|o7 : Matrix P1 <-- R                                                        |
+----------------------------------------------------------------------------+
|i8 : isIsomorphism phi1                                                     |
|                                                                            |
|o8 = true                                                                   |
+----------------------------------------------------------------------------+
|i9 : image phi1 == P1                                                       |
|                                                                            |
|o9 = true                                                                   |
+----------------------------------------------------------------------------+
|i10 : P2 = ker f -- Construct the kernel of f.                              |
|                                                                            |
|o10 = image {3} | 0         x+y-2             y2-2y           |             |
|            {1} | xy        -x2y-xy2+2xy-1    -xy3+2xy2-y     |             |
|            {2} | 50x+50y+1 -50xy-50y2-x-2y+2 -50y3-2y2+2y-50 |             |
|                                                                            |
|                              3                                             |
|o10 : R-module, submodule of R                                              |
+----------------------------------------------------------------------------+
|i11 : isProjective P2                                                       |
|                                                                            |
|o11 = true                                                                  |
+----------------------------------------------------------------------------+
|i12 : rank P2                                                               |
|                                                                            |
|o12 = 2                                                                     |
+----------------------------------------------------------------------------+
|i13 : phi2 = qsIsomorphism P2                                               |
|                                                                            |
|o13 = {3} | 0 0 |                                                           |
|      {4} | 1 0 |                                                           |
|      {5} | 0 1 |                                                           |
|                                                                            |
|                     2                                                      |
|o13 : Matrix P2 <-- R                                                       |
+----------------------------------------------------------------------------+
|i14 : isIsomorphism phi2                                                    |
|                                                                            |
|o14 = true                                                                  |
+----------------------------------------------------------------------------+
|i15 : image phi2 == P2                                                      |
|                                                                            |
|o15 = true                                                                  |
+----------------------------------------------------------------------------+
|i16 : P3 = image f -- Construct the image of f.                             |
|                                                                            |
|o16 = image | x2y+1 x+y-2 2xy |                                             |
|                                                                            |
|                              1                                             |
|o16 : R-module, submodule of R                                              |
+----------------------------------------------------------------------------+
|i17 : isProjective P3                                                       |
|                                                                            |
|o17 = true                                                                  |
+----------------------------------------------------------------------------+
|i18 : rank P3                                                               |
|                                                                            |
|o18 = 1                                                                     |
+----------------------------------------------------------------------------+
|i19 : phi3 = qsIsomorphism P3                                               |
|                                                                            |
|o19 = {3} | -1   |                                                          |
|      {1} | 0    |                                                          |
|      {2} | -50x |                                                          |
|                                                                            |
|                     1                                                      |
|o19 : Matrix P3 <-- R                                                       |
+----------------------------------------------------------------------------+
|i20 : isIsomorphism phi3                                                    |
|                                                                            |
|o20 = true                                                                  |
+----------------------------------------------------------------------------+
|i21 : image phi3 == P3                                                      |
|                                                                            |
|o21 = true                                                                  |
+----------------------------------------------------------------------------+
|i22 : P4 = coimage f -- Construct the coimage of f.                         |
|                                                                            |
|o22 = cokernel {3} | 0         x+y-2             y2-2y           |          |
|               {1} | xy        -x2y-xy2+2xy-1    -xy3+2xy2-y     |          |
|               {2} | 50x+50y+1 -50xy-50y2-x-2y+2 -50y3-2y2+2y-50 |          |
|                                                                            |
|                             3                                              |
|o22 : R-module, quotient of R                                               |
+----------------------------------------------------------------------------+
|i23 : isProjective P4                                                       |
|                                                                            |
|o23 = true                                                                  |
+----------------------------------------------------------------------------+
|i24 : rank P4                                                               |
|                                                                            |
|o24 = 1                                                                     |
+----------------------------------------------------------------------------+
|i25 : phi4 = qsIsomorphism P4                                               |
|                                                                            |
|o25 = {3} | -1   |                                                          |
|      {1} | 0    |                                                          |
|      {2} | -50x |                                                          |
|                                                                            |
|                     1                                                      |
|o25 : Matrix P4 <-- R                                                       |
+----------------------------------------------------------------------------+
|i26 : isIsomorphism phi4                                                    |
|                                                                            |
|o26 = true                                                                  |
+----------------------------------------------------------------------------+
|i27 : image phi4 == P4                                                      |
|                                                                            |
|o27 = true                                                                  |
+----------------------------------------------------------------------------+

See also
========

  * computeFreeBasis -- computes a free basis of a
    projective module
  * qsAlgorithm -- computes a solution to the unimodular
    matrix problem

Ways to use qsIsomorphism:
==========================

  * "qsIsomorphism(Module)"

For the programmer
==================

The object qsIsomorphism, is a method function with options (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in QuillenSuslin.m2:2504:0.