For a fixed positive integer ''n'', there is a unique determinant function for the ''n''×''n'' matrices over any Commutative Ring ''R''. In particular, this function exists when ''R'' is the Field of Real or Complex Number s.
|
| |
\begin{vmatrix} a & b & c\d & e & f\g & h & i \end{vmatrix}\,
|
| |
"http://wwwinformationdelightinfo/information/entry/tetrahedron" class="copylinks">Tetrahedron , given its vertices '''a''', '''b''', '''c''', and '''d''', is (1/6)·det('''a''' &minus '''b''', '''b''' &minus '''c''', '''c''' &minus '''d'''), or any other combination of pairs of vertices that form a simply connected Graph
|
An ''n'' × ''n'' square matrix ''A'' may be thought of as the coordinate representation of a
Linear Transformation of an ''n''-dimensional
Vector Space ''V''. Given any linear transformation
:
we can define the determinant of ''A'' as the determinant of any matrix representation of ''A''. This is a
Well-defined notion (i.e. independent of a choice of
Basis ) since the determinant is invariant under similarity transformations.
As one might expect, it is possible to define the determinant of a linear transformation in a coordinate-free manner. If ''V'' is an ''n''-dimensional vector space, then one can construct its top
Exterior Power Λ
''n''''V''. This is a one-dimensional vector space whose elements are written
:
where each ''v''
''i'' is a vector in ''V'' and the
Wedge Product ∧ is antisymmetric (i.e. ''u''∧''v'' = −''v''∧''u''). Any linear transformation ''A'' : ''V'' → ''V'' induces a linear transformation of Λ
''n''''V'' as follows:
:
Since Λ
''n''''V'' is one-dimensional this operation is just multiplication by some scalar that depends on ''A''. This scalar is called the of ''A''. That is, we define det(''A'') by the equation
:
One can check that this definition agrees with the coordinate-dependent definition given above.
- The naive method of implementing an algorithm to compute the determinant is to use Laplace's formula for expansion by cofactors. This approach is extremely inefficient in general, however, as it is Of Order ''n''! (''n'' Factorial ) for an ''n''×''n'' matrix ''M''.
- An improvement to order ''n''3 can be achieved by using LU Decomposition to write ''M'' = ''LU'' for triangular matrices ''L'' and ''U''. Now, det ''M'' = det ''LU'' = det ''L'' det ''U'', and since ''L'' and ''U'' are triangular the determinant of each is simply the product of its diagonal elements. Alternatively one can perform the Cholesky Decomposition if possible or the QR Decomposition and find the determinant in a similar fashion.
- Since the definition of the determinant does not need divisions, a question arises: do fast algorithms exist that do not need divisions? This is especially interesting for matrices over rings. Indeed algorithms with run-time proportional to ''n''4 exist. An algorithm of Mahajan and Vinay, and Berkowitz is based on Closed Ordered Walk s (short ''clow''). It computes more products than the determinant definition requires, but some of these products cancel and the sum of these products can be computed more efficiently. The final algorithm looks very much like an iterated product of triangular matrices.
- What is not often discussed is the so-called "bit complexity" of the problem, i.e. how many bits of accuracy you need to store for intermediate values. For example, using Gaussian Elimination , you can reduce the matrix to upper triangular form, then multiply the main diagonal to get the determinant (this is essentially a special case of the LU decomposition as above), but a quick calculation will show that the bit size of intermediate values could potentially become exponential. One could talk about when it is appropriate to round intermediate values, but an elegant way of calculating the determinant uses the Bareiss Algorithm , an exact division method based on Sylvester's Identity to give a run time of order ''n''3 and bit complexity roughly the bit size of the original entries in the matrix times n.
Historically, determinants were considered before matrices. Originally, a determinant was defined as a property of a (1750) added to the theory, treating the subject in relation to sets of equations. The recurrent law was first announced by
Bezout (1764).
It was (1772) gave the general method of expanding a determinant in terms of its
complementary
Minor s: Vandermonde had already given a
special case. Immediately following,
Lagrange (1773) treated
determinants of the second and third order. Lagrange was the first
to apply determinants to questions outside
Elimination Theory ; he proved
many special cases of general identities.
Gauss (1801) made the next advance. Like Lagrange, he made much use of determinants in the
Theory Of Numbers . He introduced the word '' (Laplace had used ''resultant''), though not in the present signification, but rather as applied to the
Discriminant of a
Quantic . Gauss also arrived at the notion of reciprocal (inverse) determinants, and came very near the multiplication theorem.
The next contributor of importance is
Binet (1811, 1812), who formally
stated the theorem relating to the product of two matrices of
columns and
rows, which for the special case of
reduces
to the multiplication theorem. On the same day (Nov. 30, 1812) that
Binet presented his paper to the Academy,
Cauchy also presented one
on the subject. (See
Cauchy-Binet Formula .) In this he used the word '' in its
present sense, summarized and simplified what was then known on the
subject, improved the notation, and gave the multiplication theorem
with a proof more satisfactory than Binet's. With him begins the theory in its generality.
The next important figure was
Jacobi (from 1827). He early used the functional determinant which Sylvester later called the
Jacobian , and in his memoirs in ''
Crelle '' for 1841 he specially treats this subject, as well as the class of alternating functions which Sylvester has called ''alternants''. About the time of Jacobi's last memoirs,
Sylvester (1839) and
Cayley began their work.
The study of special forms of determinants has been the natural result of the completion of the general theory. Axisymmetric determinants have been studied by
Lebesgue ,
Hesse , and Sylvester;
Persymmetric determinants by Sylvester and
Hankel ;
Circulant s by
Catalan ,
Spottiswoode ,
Glaisher , and Scott; skew determinants and
Pfaffian s, in connection with the theory of
Orthogonal Transformation , by Cayley; continuants by Sylvester;
Wronskian s (so called by
Muir ) by
Christoffel and
Frobenius ; compound determinants by Sylvester,
Reiss , and
Picquet ; Jacobians and
Hessian s by Sylvester; and symmetric gauche determinants by
Trudi . Of the text-books on the subject Spottiswoode's was the first. In America, Hanus (1886), Weld (1893), and Muir/Metzler (1933) published treatises.
