8. APPENDIX: The Algorithm

For any strict subset J of $\{ 1, \ldots ,r\} , \ k = card(J)$, we have to apply the following sequence of procedures. Again, we assume for simplicity $J=J_0= \{1 , \ldots ,k \}$. If J allows no splitting, we can omit the test for its complement J'.

First prepare the input matrix Q according to (5.2):
$L := \ \mbox{\bf prepare} (Q,k)$
INPUT: Q - a representation matrix of the module, k - an integer.
OUTPUT: L=A,B,C,D - a list of matrices presenting the blocks of a good
presentation matrix (B is a zero matrix).

Q := std_base(Q)
Q := min_base(Q,k)
L := find_blocks(Q,k)
return L

The next procedure computes generators of the module of J-row reductions of Q:

$\tilde{L} := \ \mbox{\bf list\_of\_reductions} (L)$
INPUT: L=A,B,C,D - a list of matrices.
OUTPUT: $\tilde{L}=N_1, \ldots ,N_q$ - a list of constant matrices corresponding to generators of ${\cal N}^J_Q$.

$\tilde{A} :=$ ko_hom(A,cols(C)+cols(D))
$\tilde{C} :=$ kontra_hom(concat(C,D),rows(A))
$\tilde{D} :=$ syz(concat( $\tilde{A},\tilde{C}$))
$\tilde{D} :=$ sub_matrix( $\tilde{D}[1..$cols $( \tilde{A}),1..$cols $( \tilde{D})]$)
i := 1
WHILE i<=cols($\tilde{D}$) DO

$\tilde{T} :=$ matrix_of_column $(\tilde{D}[i]$,cols(A),cols(C))
$N := \tilde{T}$ modulo maxideal
IF $(N \neq 0) \ \tilde{L} := \tilde{L},N$
next i

END
return $\tilde{L}$

Here ko_hom computes the matrix of the map defined by inserting the matrix in the first place of the Hom-functor and kontra_hom does the same with the second argument.

Next we will test J-row-minimality and possibly find a row-reduction of Q:

$Q,bool,break := \ \mbox{\bf find\_reduction} (L, \tilde{L})$
INPUT: L=A,B,C,D - a list of block matrices of Q,
$\tilde{L}=N_1, \ldots ,N_q$ - a list of constant matrices
OUTPUT: Q - a presentation matrix,
bool= FALSE if Q was J-row-minimal,
break= FALSE if there is no unique J-row-minimal.

bool := FALSE
break := TRUE
N_* := unit_matrix(rows( $N_i )) + \sum Z_i N_i$
i := 1
WHILE i<=cols($\tilde T$) DO

minor := minor_of_first_rows(N_*,i)
minor := std_base(minor)
IF ( $minor \neq 1 ) \ \{bool :=$ TRUE; EXIT}
next i

END
IF (bool) minor := radical(minor)
IF (is_not_linear(minor)) break:= FALSE
IF (break) z:= find_zero(minor)
N := N_*(z)
A,B := A*N
$Q := \left( \begin{array}{cc} A & B \\ C & D \end{array} \right)$
return Q,bool,break

In the main loop a J-row-minimal presentation matrix is iterated or we obtain the answer, according to Proposition 13, that there is no J-row-splitting of the module.

$Q,bool := {\bf row\_minimize}(Q,k)$
INPUT: as above
OUTPUT: Q - a matrix being J-row-minimal if bool = TRUE
or Q does not have a unique J-row-minimal presenatation matrix otherwise.

bool := TRUE
break := TRUE
WHILE bool and break DO

L := prepare(Q,k)
$\tilde{L}$ := list_of_reductions(L)
Q,bool,break := find_reduction( $L,\tilde{L}$)

END
return Q,break

If break = TRUE, a final test, which uses Corollary 8, must be preformed to determine whether the presentation matrix allows a J-splitting. Otherwise we shall take the next subset J.

$Q_0,bool := {\bf splitting\_test}(Q,k)$
INPUT: as above
OUTPUT: Q₀ - a block diagonal presentation matrix if bool = TRUE

L := prepare(Q,k)
$\tilde{A}$ := kontra_hom(A,rows(D))
$\tilde{D}$ := ko_hom(D,cols(A))
$\tilde{E}$ := concat( $\tilde{A},\tilde{D}$)
$\tilde{C}$ := matrix_to_vector(C)
bool := is_liftable( $\tilde{E},\tilde{C}$)
$Q_0 := \left( \begin{array}{cc} A & 0 \\ 0 & D \end{array} \right)$
return Q₀,bool

Remarks:

1.

It may happen that the procedure find_reduction will not give a result in a reasonable amount of time for J, but for the complement J'. Therefore, it is worth finding good strategies for the algorithm.

2.

The procedures and algorithms described here are implemented in the library module.lib of the Computer Algebra system SINGULAR [GPS97]. See the accompanying documentation for more details. module.lib will be included in a forthcoming new release of SINGULAR and, in the meantime, may be obtained directly from the authors.