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
This amounts to decide if b belongs to the ideal generated by the ai.
in Rk that are solutions of the homogeneous equation The simplest case, when k = 1 amounts to find a system of generators of the annihilator of a1.
The article considers the main rings for which linear algebra is effective.
In fact, this article is restricted to Noetherian integral domains because of the following result.
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.
There are algorithms to solve all the problems addressed in this article over the integers.
More generally, linear algebra is effective on a principal ideal domain if there are algorithms for addition, subtraction and multiplication, 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 a and b in the principal ideal domain, there is an algorithm computing a unimodular matrix such that (This algorithm is obtained by taking for s and t the coefficients of Bézout's identity, and for u and v the quotient of −b and a by as + bt; this choice implies that the determinant of the square matrix is 1.)
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.
In this case, the extended Euclidean algorithm may be used for computing the above unimodular matrix; see Polynomial greatest common divisor § Bézout's identity and extended GCD algorithm for details.
Linear algebra is effective on a polynomial ring
Proofs that linear algebra is effective on polynomial rings and computer implementations are presently all based on Gröbner basis theory.