In
algebra
Algebra () is one of the broad areas of mathematics. Roughly speaking, algebra is the study of mathematical symbols and the rules for manipulating these symbols in formulas; it is a unifying thread of almost all of mathematics.
Elementary a ...
,
linear equation
In mathematics, a linear equation is an equation that may be put in the form
a_1x_1+\ldots+a_nx_n+b=0, where x_1,\ldots,x_n are the variables (or unknowns), and b,a_1,\ldots,a_n are the coefficients, which are often real numbers. The coefficie ...
s and
systems of linear equations
In mathematics, a system of linear equations (or linear system) is a collection of one or more linear equations involving the same variables.
For example,
:\begin
3x+2y-z=1\\
2x-2y+4z=-2\\
-x+\fracy-z=0
\end
is a system of three equations in t ...
over a
field
Field may refer to:
Expanses of open ground
* Field (agriculture), an area of land used for agricultural purposes
* Airfield, an aerodrome that lacks the infrastructure of an airport
* Battlefield
* Lawn, an area of mowed grass
* Meadow, a grass ...
are widely studied. "Over a field" means that the
coefficient
In mathematics, a coefficient is a multiplicative factor in some term of a polynomial, a series, or an expression; it is usually a number, but may be any expression (including variables such as , and ). When the coefficients are themselves ...
s of the
equation
In mathematics, an equation is a formula that expresses the equality of two expressions, by connecting them with the equals sign . The word ''equation'' and its cognates in other languages may have subtly different meanings; for example, in ...
s and the solutions that one is looking for belong to a given field, commonly the
real
Real may refer to:
Currencies
* Brazilian real (R$)
* Central American Republic real
* Mexican real
* Portuguese real
* Spanish real
* Spanish colonial real
Music Albums
* ''Real'' (L'Arc-en-Ciel album) (2000)
* ''Real'' (Bright album) (2010) ...
or the
complex numbers. This article is devoted to the same problems where "field" is replaced by "
commutative ring
In mathematics, a commutative ring is a ring in which the multiplication operation is commutative. The study of commutative rings is called commutative algebra. Complementarily, noncommutative algebra is the study of ring properties that are not ...
", or, typically "
Noetherian In mathematics, the adjective Noetherian is used to describe objects that satisfy an ascending or descending chain condition on certain kinds of subobjects, meaning that certain ascending or descending sequences of subobjects must have finite lengt ...
integral domain
In mathematics, specifically abstract algebra, an integral domain is a nonzero commutative ring in which the product of any two nonzero elements is nonzero. Integral domains are generalizations of the ring of integers and provide a natural se ...
".
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 in a given
ring , to decide if it has a solution with
in , and, if any, to provide one. This amounts to decide if belongs to the
ideal generated by the . The simplest instance of this problem is, for and , to decide if is a
unit
Unit may refer to:
Arts and entertainment
* UNIT, a fictional military organization in the science fiction television series ''Doctor Who''
* Unit of action, a discrete piece of action (or beat) in a theatrical presentation
Music
* ''Unit'' (a ...
in .
The syzygy problem consists, given elements
in , to provide a system of generators of the
module of the
syzygies of
that is a system of generators of the
submodule
In mathematics, a module is a generalization of the notion of vector space in which the field of scalars is replaced by a ring. The concept of ''module'' generalizes also the notion of abelian group, since the abelian groups are exactly the m ...
of those elements
in that are solutions of the homogeneous equation
:
The simplest case, when amounts to find a system of generators of the
annihilator of .
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
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...
s 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.
Generalities
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
In mathematics, a Noetherian ring is a ring that satisfies the ascending chain condition on left and right ideals; if the chain condition is satisfied only for left ideals or for right ideals, then the ring is said left-Noetherian or right-Noeth ...
, or at least a
coherent ring
In mathematics, a (left) coherent ring is a ring in which every finitely generated left ideal is finitely presented.
Many theorems about finitely generated modules over Noetherian rings can be extended to finitely presented modules over cohe ...
. In fact, this article is restricted to Noetherian
integral domain
In mathematics, specifically abstract algebra, an integral domain is a nonzero commutative ring in which the product of any two nonzero elements is nonzero. Integral domains are generalizations of the ring of integers and provide a natural se ...
s 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
Field may refer to:
Expanses of open ground
* Field (agriculture), an area of land used for agricultural purposes
* Airfield, an aerodrome that lacks the infrastructure of an airport
* Battlefield
* Lawn, an area of mowed grass
* Meadow, a grass ...
is an effective ring as soon one has algorithms for addition, subtraction, multiplication, and computation of
multiplicative inverse
In mathematics, a multiplicative inverse or reciprocal for a number ''x'', denoted by 1/''x'' or ''x''−1, is a number which when multiplied by ''x'' yields the multiplicative identity, 1. The multiplicative inverse of a fraction ''a''/'' ...
s. 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
In mathematics, the kernel of a linear map, also known as the null space or nullspace, is the linear subspace of the domain of the map which is mapped to the zero vector. That is, given a linear map between two vector spaces and , the kernel of ...
of the
matrix
Matrix most commonly refers to:
* ''The Matrix'' (franchise), an American media franchise
** ''The Matrix'', a 1999 science-fiction action film
** "The Matrix", a fictional setting, a virtual reality environment, within ''The Matrix'' (franchis ...
of a
system of linear equations
In mathematics, a system of linear equations (or linear system) is a collection of one or more linear equations involving the same variables.
For example,
:\begin
3x+2y-z=1\\
2x-2y+4z=-2\\
-x+\fracy-z=0
\end
is a system of three equations in t ...
. The basic algorithm for both problems is
Gaussian elimination
In mathematics, Gaussian elimination, also known as row reduction, is an algorithm for solving systems of linear equations. It consists of a sequence of operations performed on the corresponding matrix of coefficients. This method can also be used ...
.
Properties of effective rings
Let be an effective commutative ring.
*There is an algorithm for testing if an element is a
zero divisor
In abstract algebra, an element of a ring is called a left zero divisor if there exists a nonzero in such that , or equivalently if the map from to that sends to is not injective. Similarly, an element of a ring is called a right zero ...
: this amounts to solving the linear equation .
*There is an algorithm for testing if an element is a
unit
Unit may refer to:
Arts and entertainment
* UNIT, a fictional military organization in the science fiction television series ''Doctor Who''
* Unit of action, a discrete piece of action (or beat) in a theatrical presentation
Music
* ''Unit'' (a ...
, 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
In mathematics, especially in the field of algebra, a polynomial ring or polynomial algebra is a ring (which is also a commutative algebra) formed from the set of polynomials in one or more indeterminates (traditionally also called variabl ...