Linear equation over a ring

To be able to solve the syzygy problem, it is necessary that the module of syzygies is finitely generated, because it is impossible to output an infinite list. Therefore, the problems considered here make sense only for a Noetherian ring, or at least a coherent ring. In fact, this article is restricted to Noetherian integral domains because of the following result. :Given a Noetherian integral domain, if there are algorithms to solve the ideal membership problem and the syzygies problem for a single equation, then one may deduce from them algorithms for the similar problems concerning systems of equations. This theorem is useful to prove the existence of algorithms. However, in practice, the algorithms for the systems are designed directly. A field is an effective ring as soon one has algorithms for addition, subtraction, multiplication, and computation of multiplicative inverses. In fact, solving the submodule membership problem is what is commonly called solving the system, and solving the syzygy problem is the computation of the null space of the matrix of a system of linear equations. The basic algorithm for both problems is Gaussian elimination. Properties of effective rings Let be an effective commutative ring. • There is an algorithm for testing if an element is a zero divisor: this amounts to solving the linear equation . • There is an algorithm for testing if an element is a unit, and if it is, computing its inverse: this amounts to solving the linear equation . • Given an ideal generated by , • there is an algorithm for testing if two elements of have the same image in : testing the equality of the images of and amounts to solving the equation ; • linear algebra is effective over : for solving a linear system over , it suffices to write it over and to add to one side of the th equation (for ), where the are new unknowns. • Linear algebra is effective on the polynomial ring R[x_1, \ldots, x_n] if and only if one has an algorithm that computes an upper bound of the degree of the polynomials that may occur when solving linear systems of equations: if one has solving algorithms, their outputs give the degrees. Conversely, if one knows an upper bound of the degrees occurring in a solution, one may write the unknown polynomials as polynomials with unknown coefficients. Then, as two polynomials are equal if and only if their coefficients are equal, the equations of the problem become linear equations in the coefficients, that can be solved over an effective ring. == Over the integers or a principal ideal domain ==

There are algorithms to solve all the problems addressed in this article over the integers. In other words, linear algebra is effective over the integers; see Linear Diophantine system for details. More generally, linear algebra is effective on a principal ideal domain if there are algorithms for addition, subtraction and multiplication, and • Solving equations of the form , that is, testing whether is a divisor of , and, if this is the case, computing the quotient , • Computing Bézout's identity, that is, given and , computing and such that is a greatest common divisor of and . It is useful to extend to the general case the notion of a unimodular matrix by calling unimodular a square matrix whose determinant is a unit. This means that the determinant is invertible and implies that the unimodular matrices are exactly the invertible matrices such all entries of the inverse matrix belong to the domain. The above two algorithms imply that given and in the principal ideal domain, there is an algorithm computing a unimodular matrix : \begin{bmatrix} s&t\\u&v \end{bmatrix} such that : \begin{bmatrix} s&t\\u&v \end{bmatrix} \begin{bmatrix} a\\b \end{bmatrix} = \begin{bmatrix}\gcd(a,b)\\0 \end{bmatrix}. (This algorithm is obtained by taking for and the coefficients of Bézout's identity, and for and the quotient of and by ; this choice implies that the determinant of the square matrix is .) Having such an algorithm, the Smith normal form of a matrix may be computed exactly as in the integer case, and this suffices to apply the described in Linear Diophantine system for getting an algorithm for solving every linear system. The main case where this is commonly used is the case of linear systems over the ring of univariate polynomials over a field. In this case, the extended Euclidean algorithm may be used for computing the above unimodular matrix; see for details. ==Over polynomials rings over a field==

Linear algebra is effective on a polynomial ring k[x_1, \ldots, x_n] over a field . This has been first proved in 1926 by Grete Hermann. The algorithms resulting from Hermann's results are only of historical interest, as their computational complexity is too high for allowing effective computer computation. Proofs that linear algebra is effective on polynomial rings and computer implementations are presently all based on Gröbner basis theory. == References ==