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

${\displaystyle a_{1}x_{1}+\cdots +a_{k}x_{k}=b}$

with ${\displaystyle a_{1},\ldots ,a_{k}}$ and b in a given ring R, to decide if it has a solution with ${\displaystyle x_{1},\ldots ,x_{k}}$ in R, and, if any, to provide one. This amounts to decide if b belongs to the ideal generated by the a_i. 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 ${\displaystyle a_{1},\ldots ,a_{k}}$ in R, to provide a system of generators of the module of the syzygies of ${\displaystyle (a_{1},\ldots ,a_{k}),}$ that is a system of generators of the submodule of those elements ${\displaystyle (x_{1},\ldots ,x_{k})}$ in R^k that are solutions of the homogeneous equation

${\displaystyle a_{1}x_{1}+\cdots +a_{k}x_{k}=0.}$

The simplest case, when k = 1 amounts to find a system of generators of the annihilator of a₁.

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.