Potentially nilpotent matrices over finite fields: K.N. Vander Meulen and A. Van Tuyl

Adam Van Tuyl

Department of Mathematics and Statistics
McMaster University
Hamilton, ON, Canada
L8S 4L8
vantuyl@math.mcmaster.ca

Using computer algebra programs to find potentially nilpotent matrices

In a paper with Kevin N. Vander Meulen

Zero-nonzero patterns for nilpotent matrices over finite fields (with K.N. Vander Meulen)
The Electronic Journal of Linear Algebra 18 (2009) 628-648.

we initiated an investigation into which zero-nonzero patterns are potentially nilpotent over a field F, with a special emphasis on the case that the field is a finite field with p elements, where p is a prime.

As part of this project, we showed that one can use techniques from commutative algebra, most notably, ideal saturation and Groebner bases, to elminate some zero-nonzero patterns as being potentially nilpotent over any field.

As promised in our paper (Remark 3.6), one can make use of computational commutative algebra programs like CoCoA and Macaulay 2 to carry out the computational aspects of these methods. What one will find below is a brief introduction to both programs, and how to use these programs to compute examples. In particular, we provide the necessary syntax to compute the examples in our paper. It is hoped that these methods will encourage future experimentation.

Feel free to borrow and change the code. If you find anything, we would be interested in hearing about your results!

CoCoA

CoCoA, which is based at the University of Genoa, stands for Computations in Commutative Algebra. It is freely available for a number of different platforms; see the download page for more information.

In what follows, we use CoCoA in computing some of the examples in our paper.

Our first example comes from Example 3.1 and 3.8. This example shows how to define an ideal, how to change the field of coefficients, and how to compute the ideal saturation.

-------------------------------------------------------
---           ___/       ___/         \             ---
--           /     _ \  /     _ \    , \             --
--           \    |   | \    |   |  ___ \            --
---          ____, __/  ____, __/ _/    _\          ---
-------------------------------------------------------
--     Version      : 4.5                            --
--     Online Help  : type  ?   or   ?keyword        --
--     Web site     : http://cocoa.dima.unige.it     --
-------------------------------------------------------

-------------------------------
-- The current ring is R ::= Q[x,y,z];
-------------------------------

Use R::=Q[z[1..6]];  -- polynomial ring with coefficients in Q in 6 variables
IA:=Ideal(z[1] + z[6], z[2]z[3] + z[4]z[5] - z[1]z[6], -z[1]z[4]z[5] - z[2]z[3]z[6]);
J:=Ideal(z[1]z[2]z[3]z[4]z[5]z[6]);
Saturation(IA,J);


Ideal(z[1] + z[6], z[2]z[3] + 1/2z[6]^2, z[4]z[5] + 1/2z[6]^2)  -- since this is not Ideal(1)
                                                                -- the matrix may or may not
                                                                -- be potentially nilpotent over Q
-------------------------------



Use R::=Z/(2)[z[1..6]]; -- polynomial ring over finite field Z/(2)
IA:=Ideal(z[1] + z[6], z[2]z[3] + z[4]z[5] - z[1]z[6], -z[1]z[4]z[5] - z[2]z[3]z[6]);
J:=Ideal(z[1]z[2]z[3]z[4]z[5]z[6]);
Saturation(IA,J);
Ideal(1)  -- because the output is Ideal(1), by Theorem 3.5, the matrix
          -- A that defines IA is not potentially nilpotent over any
          -- extenstion of Z/(2)
-------------------------------

Below is Example 3.9; it shows how to compute the colon operation I:J.


Use R::=Z/(2)[z[1..5]];
IA:=Ideal(z[1] + z[2] + z[5], 
          z[1]z[2] + z[3]z[4] + z[1]z[5] + z[2]z[5], 
          z[1]z[3]z[4] + z[1]z[2]z[5]);
J:=Ideal(z[1]z[2]z[3]z[4]z[5]);
IA:J;  -- colon operation
Ideal(z[1] + z[2] + z[5], z[2]^2 + z[5]^2, z[3]z[4] + z[2]z[5])
-------------------------------
Saturation(IA,J);
Ideal(1)
-------------------------------

The following example corresponds to Example 3.10 in our paper.


Use R::=Q[z[1..11]];
IA:=Ideal(-z[1] + z[5], -z[2]z[4] + z[1]z[5], z[6]z[7]z[9] - z[3]z[8]z[11], 
          -z[3]z[4]z[7]z[9] + z[1]z[6]z[7]z[9] + z[3]z[5]z[8]z[11] - z[2]z[6]z[8]z[11] 
          + z[3]z[7]z[10]z[11], -z[3]z[5]z[7]z[10]z[11] + z[2]z[6]z[7]z[10]z[11]);
J:=Ideal(z[1]z[2]z[3]z[4]z[5]z[6]z[7]z[8]z[9]z[10]z[11]);
Saturation(IA,J);
Ideal(1)
-------------------------------

In our final example, which corresponds to Example 3.13, we show how one can find the Groebner basis using CoCoA.

Use R::=Q[z[1..6]];
IA:=Ideal(z[1] + z[3] + z[6], -z[1]z[3] - z[1]z[6] - z[3]z[6], z[2]z[4]z[5] + z[1]z[3]z[6]);
GBasis(IA);
[z[1] + z[3] + z[6], z[3]^2 + z[3]z[6] + z[6]^2, z[2]z[4]z[5] + z[6]^3]
-------------------------------

Macaulay 2

Another free computer algebra system is Macaulay 2, whose main authors are Dan Grayson and Mike Stillman. The Macaulay 2 web page describes how to download and install the program. The free book gives a good overview of the type of computations one can compute in Macaulay 2.

Below, we repeat the above examples, but now using Macaulay 2's syntax.


+ M2 --no-readline --print-width 79
Macaulay 2, version 1.1
with packages: Classic, Core, Elimination, IntegralClosure, LLLBases, Parsing,
               PrimaryDecomposition, SchurRings, TangentCone

i1 : r =QQ[z_1..z_6];  -- polynomial ring with coefficients in Q in 6 variables

i2 : iA =ideal(z_1 + z_6, z_2*z_3 + z_4*z_5 - z_1*z_6, -z_1*z_4*z_5 - z_2*z_3*z_6)

o2 = ideal (z  + z , z z  + z z  - z z , - z z z  - z z z )
             1    6   2 3    4 5    1 6     1 4 5    2 3 6

o2 : Ideal of r

i3 : j=ideal(z_1*z_2*z_3*z_4*z_5*z_6)

o3 = ideal(z z z z z z )
            1 2 3 4 5 6

o3 : Ideal of r

i4 : saturate(iA,j)

                              2           2
o4 = ideal (z  + z , 2z z  + z , 2z z  + z )
             1    6    4 5    6    2 3    6

o4 : Ideal of r

i5 : r =ZZ/(2)[z_1..z_6];  -- polynomial ring with coefficients in ZZ/(2) in 6 variables

i6 : iA =ideal(z_1 + z_6, z_2*z_3 + z_4*z_5 - z_1*z_6, -z_1*z_4*z_5 
          - z_2*z_3*z_6)

o6 = ideal (z  + z , z z  + z z  + z z , z z z  + z z z )
             1    6   2 3    4 5    1 6   1 4 5    2 3 6

o6 : Ideal of r

i7 : j=ideal(z_1*z_2*z_3*z_4*z_5*z_6)

o7 = ideal(z z z z z z )
            1 2 3 4 5 6

o7 : Ideal of r

i8 : saturate(iA,j)

o8 = ideal 1

o8 : Ideal of r

Below is Example 3.9; it shows how to compute the colon operation I:J.


i9 : r=ZZ/(2)[z_1..z_5];

i10 : iA=ideal(z_1 + z_2 + z_5, 
                z_1*z_2 + z_3*z_4 + z_1*z_5 + z_2*z_5, 
                z_1*z_3*z_4 + z_1*z_2*z_5)

o10 = ideal (z  + z  + z , z z  + z z  + z z  + z z , z z z  + z z z )
              1    2    5   1 2    3 4    1 5    2 5   1 3 4    1 2 5

o10 : Ideal of r

i11 : j=ideal(z_1*z_2*z_3*z_4*z_5)

o11 = ideal(z z z z z )
             1 2 3 4 5

o11 : Ideal of r

i12 : iA:j  -- colon operation

                                         2    2
o12 = ideal (z  + z  + z , z z  + z z , z  + z )
              1    2    5   3 4    2 5   2    5

o12 : Ideal of r

i13 : saturate(iA,j)

o13 = ideal 1

o13 : Ideal of r

Here is how one would compute Example 3.10 with Macaulay 2:

i14 : r=QQ[z_1..z_11];

i15 : iA=ideal(-z_1 + z_5, -z_2*z_4 + z_1*z_5, z_6*z_7*z_9 - z_3*z_8*z_11, 
                -z_3*z_4*z_7*z_9 + z_1*z_6*z_7*z_9 + z_3*z_5*z_8*z_11 - z_2*z_6*z_8*z_11 
                + z_3*z_7*z_10*z_11, -z_3*z_5*z_7*z_10*z_11 + z_2*z_6*z_7*z_10*z_11);

o15 : Ideal of r

i16 : j=ideal(z_1*z_2*z_3*z_4*z_5*z_6*z_7*z_8*z_9*z_10*z_11)

o16 = ideal(z z z z z z z z z z  z  )
             1 2 3 4 5 6 7 8 9 10 11

o16 : Ideal of r

i17 : saturate(iA,j)

o17 = ideal 1

o17 : Ideal of r

Finally, here is how one would calculated the Groebner basis in Example 3.13.


i18 : r =QQ[z_1..z_6]

o18 = r

o18 : PolynomialRing

i19 : iA=ideal(z_1 + z_3 + z_6, -z_1*z_3 - z_1*z_6 - z_3*z_6, z_2*z_4*z_5 + z_1*z_3*z_6);

o19 : Ideal of r

i20 : gens gb iA

o20 = | z_1+z_3+z_6 z_3^2+z_3z_6+z_6^2 z_2z_4z_5+z_6^3 |

              1       3
o20 : Matrix r  <--- r