A Koszul decomposition for the computation of linear syzygies (Q5929732)

In explicit terms, the paper deals with the following problem: Given an \((m \times n)\)-matrix \((L_{i,j})\) of linear forms in a polynomial ring \(R := K[x_1, \ldots, x_r]\), calculate the vector space of all tuples \((l_1, \ldots, l_n)\) of linear forms in \(R\) such that \(\sum_{j=1}^n L_{i,j} l_j = 0\) for all \(i\). The columns of the matrix \((L_{i,j})\) generate a ``linear'' submodule \(M\) of the free module \(R^m\), and the solutions of the above equations are called the linear syzygies of \(M\). Continuing this process, one obtains the linear strand of \(M\), which gives a subcomplex of a free resolution of \(M\). The linear strand bears some information about the structure of \(M\). In the paper under review, the authors propose a new algorithm for computing linear syzygies. They analyze the matrix \(S\) associated to the \(K\)-linear system given by the above equations. \(S\) has two crucial properties: sparsity and block structure. The authors develop their algorithm by first considering the case \(m = 1\) as a model. In this case the solution is known to be given by the Koszul complex. A careful analysis of the behavior of the matrix \(S\) yields a semi-combinatorial algorithm that can be generalized to the case \(m > 1\).