Linear equation over a ring
In algebra, linear equations and systems of linear equations over a field are widely studied. "Over a field" means that the coefficients of the equations and the solutions that one is looking for belong to a given field, commonly the real or the complex numbers. This article is devoted to the same problems where "field" is replaced by "commutative ring", or, typically "Noetherian integral domain".
In the case of a single equation, the problem splits in two parts. First, the ideal membership problem, which consists, given a non homogeneous equation
with and b in a given ring R, to decide if it has a solution with in R, and, if any, to provide one. This amounts to decide if b belongs to the ideal generated by the ai. The simplest instance of this problem is, for k = 1 and b = 1, to decide if a is a unit in R.
The syzygy problem consists, given k elements in R, to provide a system of generators of the module of the syzygies of that is a system of generators of the submodule of those elements in Rk that are solution of the homogeneous equation
The simplest case, when k = 1 amounts to find a system of generators of the annihilator of a1.
Given a solution of the ideal membership problem, one obtains all the solutions by adding to it the elements of the module of syzygies. In other words, all the solutions are provided by the solution of these two partial problems.
In the case of several equations, the same decomposition into subproblems occurs. The first problem becomes the submodule membership problem. The second one is also called the syzygy problem.
A ring such that there are algorithms for the arithmetic operations (addition, subtraction, multiplication) and for the above problems may be called a computable ring, or effective ring. One may also say that linear algebra on the ring is effective.
The article considers the main rings for which linear algebra is effective.
To be able of solving 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 Noetherian rings, 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, as it is done for the systems of linear equations over a field.
Properties of effective rings
Let R be an effective commutative ring.
- There is an algorithm for testing if an element a is a zero divisor: this amounts to solve the linear equation ax = 0.
- There is an algorithm for testing if an element a is a unit, and if it is, computing its inverse: this amounts to solve the linear equation ax = 1.
- Given an ideal I generated by a1, ..., ak, there is an algorithm for testing if two elements of R have the same image in R/I, and linear algebra is effective over R/I: testing the equality of the images of a and b amounts to solve the equation a = b + a1z1 + ⋅⋅⋅ + akzk; for solving a linear system over R/I, it suffices to write it over R and to add to one side of the ith equation a1zi,1 + ⋅⋅⋅ + akzi,k (for i = 1, ...), where the zi,j are new unknowns.
Linear equations 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.
The same solution applies to the same problems over a principal ideal domain, with the following modifications.
The notion of unimodular matrix of integers must be extended by calling unimodular a matrix over a integral domain whose determinant is a unit. This means that the determinant is invertible and implies that unimodular matrices are the invertible matrices such all entries of the inverse matrix belong to the domain.
To have an algorithmic solution of linear systems, a solution for a single linear equation in two unknowns is clearly required. In the case of the integers, such a solution is provided by extended Euclidean algorithm. Thus one needs that, for the considered principal ideal domain, there is an algorithm with a similar specification as the extended Euclidean algorithm. That is, given a and b in the principal ideal domain, there is an algorithm computing a unimodular matrix
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. See polynomial greatest common divisor#Bézout's identity and extended GCD algorithm for details.
- Hermann, Grete (1926), "Die Frage der endlich vielen Schritte in der Theorie der Polynomideale", Mathematische Annalen, 95: 736–788, doi:10.1007/BF01206635. English translation in Communications in Computer Algebra 32/3 (1998): 8–30.
- David A. Cox; John Little; Donal O'Shea (1997). Ideals, Varieties, and Algorithms (second ed.). Springer-Verlag. ISBN 0-387-94680-2. Zbl 0861.13012.
- Aschenbrenner, Matthias (2004). "Ideal membership in polynomial rings over the integers" (PDF). J. Amer. Math. Soc. AMS. 17: 407–441. Retrieved 23 October 2013.