determinant

determinant

[dih-tur-muh-nuhnt]
determinant, a polynomial expression that is inherent in the entries of a square matrix. The size n of the square matrix, as determined from the number of entries in any row or column, is called the order of the determinant. If the entry in row i and column j is denoted as aij, then, for n=2, the determinant is a11a22-a12a21. For example, the second-order determinanthas the value (1×4)-(2×3)=4-6=-2. Its absolute value is the area of the parallelogram spanned by its row vectors. Third order determinants are similarly related to volumes. A determinant of order n is indicated by ~~pipe~;aij~~pipe~;, where i and j each take on the values 1, 2, 3, … n. Its non-vanishing detects invertibility of the matrix. Its value is the sum of all terms S(π)a1π(1) … anπ(n), where π ranges over all permutations of (1, 2, … n) and S(π)=±1 is a sign called the signature of π. This value may be found more easily by expanding the determinant by minors. The minor Aij of an element aij of an nth-order determinant is the determinant of order (n-1) formed by deleting the ith row and the jth column of the original determinant. For example, in the determinantthe element a21, whose value is 3, has the minor

In expanding a determinant by minors, first the minor of every element in a particular row or column is formed. Products are derived by multiplying each minor by its corresponding element. A plus sign is placed in front of each product if the sum of the row number and column number of its element is even, and a minus sign if the sum is odd. Finally, the signed products are added algebraically. For example, expanding the above determinant by its second row yields:

Determinants of higher order can be evaluated by successive expansions of this type. By choosing rows of columns containing zeros, some terms can be eliminated. There are various rules for transforming a given determinant, which can be used to obtain a row or column most of whose elements are zeros. Determinants have many applications in mathematics and other fields, e.g., in the solution of simultaneous linear equations.

In linear algebra, a numerical value associated with a matrix having the same number of rows as columns. It is particularly useful in solving systems of (linear) equations and in the study of vectors. For a two-by-two matrix, the determinant is the product of the upper left and lower right terms minus the product of the lower left and upper right terms. Determinants of larger matrices involve more complicated arithmetic combinations of the terms and are usually solved using a calculator or computer.

Learn more about determinant with a free trial on Britannica.com.

In algebra, a determinant is a function depending on n that associates a scalar, det(A), to every n×n square matrix A. The fundamental geometric meaning of a determinant is as the scale factor for volume when A is regarded as a linear transformation. Determinants are important both in calculus, where they enter the substitution rule for several variables, and in multilinear algebra.

For a fixed nonnegative 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 numbers.

Vertical bar notation

The determinant of a matrix A is also sometimes denoted by |A|. This notation can be ambiguous since it is also used for certain matrix norms and for the absolute value. However, often the matrix norm will be denoted with double vertical bars (e.g., ||A||) and may carry a subscript as well. Thus, the vertical bar notation for determinant is frequently used (e.g., Cramer's rule and minors).

For example, for matrix

A = begin{bmatrix} a & b & cd & e & fg & h & i end{bmatrix}, the determinant det(A) might be indicated by |A| or more explicitly as
|A| = begin{vmatrix} a & b & cd & e & fg & h & i end{vmatrix}., That is, the square braces around the matrices are replaced with elongated vertical bars.

Determinants of 2-by-2 matrices

The 2×2 matrix,

A = begin{bmatrix} a & bc & d end{bmatrix},

has determinant

det(A)=ad-bc.,

The interpretation when the matrix has real number entries is that this gives the oriented area of the parallelogram with vertices at (0,0), (a,b), (a + c, b + d), and (c,d). The oriented area is the same as the usual area, except that it is negative when the vertices are listed in clockwise order.

The assumption here is that a linear transformation is applied to row vectors as the vector-matrix product x^T A^T, where x is a column vector. The parallelogram in the figure is obtained by multiplying matrix A (which stores the co-ordinates of our parallelogram) with each of the row vectors begin{bmatrix} 0 & 0 end{bmatrix}, begin{bmatrix} 1 & 0 end{bmatrix}, begin{bmatrix} 1 & 1 end{bmatrix} and begin{bmatrix}0 & 1end{bmatrix} in turn. These row vectors define the vertices of the unit square. With the more common matrix-vector product Ax, the parallelogram has vertices at begin{bmatrix} 0 0 end{bmatrix}, begin{bmatrix} a c end{bmatrix}, begin{bmatrix} a+b c+d end{bmatrix} and begin{bmatrix} b d end{bmatrix} (note that Ax = (x^T A^T)^T).

A formula for larger matrices will be given below.

Determinants of 3-by-3 matrices

The 3×3 matrix:

A=begin{bmatrix}a&b&c
d&e&fg&h&iend{bmatrix}. Using the cofactor expansion on the first row of the matrix we get:
begin{align}
det(A) &= abegin{vmatrix}e&fh&iend{vmatrix} -bbegin{vmatrix}d&fg&iend{vmatrix} +cbegin{vmatrix}d&eg&hend{vmatrix} &= aei-afh-bdi+bfg+cdh-ceg &= (aei+bfg+cdh)-(gec+hfa+idb), end{align}

which can be remembered as the sum of the products of three diagonal north-west to south-east lines of matrix elements, minus the sum of the products of three diagonal south-west to north-east lines of elements when the copies of the first two columns of the matrix are written beside it as below:

begin{matrix} color{red}a & color{red}b & color{red}c & a & b d & color{red}e & color{red}f & color{red}d & e g & h & color{red}i & color{red}g & color{red}h end{matrix} quad - quad begin{matrix} a & b & color{blue}c & color{blue}a & color{blue}b d & color{blue}e & color{blue}f & color{blue}d & e color{blue}g & color{blue}h & color{blue}i & g & h end{matrix}

Note that this mnemonic does not carry over into higher dimensions.

Applications

Determinants are used to characterize invertible matrices (i.e., exactly those matrices with non-zero determinants), and to explicitly describe the solution to a system of linear equations with Cramer's rule. They can be used to find the eigenvalues of the matrix A through the characteristic polynomial

p(x) = det(xI - A) ,

where I is the identity matrix of the same dimension as A.

One often thinks of the determinant as assigning a number to every sequence of n vectors in Bbb{R}^n, by using the square matrix whose columns are the given vectors. With this understanding, the sign of the determinant of a basis can be used to define the notion of orientation in Euclidean spaces. The determinant of a set of vectors is positive if the vectors form a right-handed coordinate system, and negative if left-handed.

Determinants are used to calculate volumes in vector calculus: the absolute value of the determinant of real vectors is equal to the volume of the parallelepiped spanned by those vectors. As a consequence, if the linear map f: Bbb{R}^n rightarrow Bbb{R}^n is represented by the matrix A, and S is any measurable subset of Bbb{R}^n, then the volume of f(S) is given by left| det(A) right| times operatorname{volume}(S). More generally, if the linear map f: Bbb{R}^n rightarrow Bbb{R}^m is represented by the m-by-n matrix A, and S is any measurable subset of Bbb{R}^{n}, then the m-dimensional volume of f(S) is given by sqrt{det(A^mathrm{T} A)} times operatorname{volume}(S). By calculating the volume of the tetrahedron bounded by four points, they can be used to identify skew lines.

The volume of any tetrahedron, given its vertices a, b, c, and d, is (1/6)·|det(a − bb − c, c − d)|, or any other combination of pairs of vertices that form a simply connected graph.

General definition and computation

The formal extension to arbitrary dimensions was made by Levi-Civita, using a pseudo-tensor symbol (Levi-Civita symbol). Anyway, for practical purposes, the definition of the determinant can be given from the following theorem.

Theorem. Let Mn(K) denote the set of all n times n matrices over the field K. There exists exactly one function

F : M_n(K) longrightarrow K

with the two properties:

One can then define the determinant as the unique function with the above properties.

In proving the above theorem, one also obtains the Leibniz formula:

det(A) = sum_{sigma in S_n} sgn(sigma) prod_{i=1}^n A_{i,sigma(i)}.

Here the sum is computed over all permutations sigma of the numbers {1,2,...,n}. S_n denotes the set of all n! permutations of the set S = {1,2,...,n}. sgn(sigma) denotes the signature of the permutation sigma: +1 if sigma is an even permutation and −1 if it is odd. sigma can also denote the signature of the number of inversions of the product of the permutation which is the approach used in some textbooks.

This formula contains n! (factorial) summands, and it is therefore impractical to use it to calculate determinants for large n.

For small matrices, one obtains the following formulas:

  • if A is a 1-by-1 matrix, then det(A) = A_{1,1}. ,
  • if A is a 2-by-2 matrix, then det(A) = A_{1,1}A_{2,2} - A_{2,1}A_{1,2}. ,
  • for a 3-by-3 matrix A, the formula is more complicated and the shape of the Sarrus' scheme:

begin{align}
det(A) &= A_{1,1}A_{2,2}A_{3,3} + A_{1,3}A_{2,1}A_{3,2} + A_{1,2}A_{2,3}A_{3,1} & quad {} - A_{1,3}A_{2,2}A_{3,1} - A_{1,1}A_{2,3}A_{3,2} - A_{1,2}A_{2,1}A_{3,3}. end{align}

It is also possible to consider 0-by-0 matrices. There is only one 0-by-0 matrix and its determinant is one.

In general, determinants can be computed using Gaussian elimination using the following rules:

  • If A is a triangular matrix, i.e. A_{i,j} = 0 , whenever i > j or, alternatively, whenever i < j, then det(A) = A_{1,1} A_{2,2} cdots A_{n,n} , (the product of the diagonal entries of A).
  • If B results from A by interchanging two rows or columns, then det(B) = -det(A). ,
  • If B results from A by multiplying one row or column with the number c, then det(B) = c,det(A). ,
  • If B results from A by adding a multiple of one row to another row, or a multiple of one column to another column, then det(B) = det(A). ,

Explicitly, starting out with some matrix, use the last three rules to convert it into a triangular matrix, then use the first rule to compute its determinant.

It is also possible to expand a determinant along a row or column using Laplace's formula, which is efficient for relatively small matrices. To do this along row i, say, we write

det(A) = sum_{j=1}^n A_{i,j}C_{i,j} = sum_{j=1}^n A_{i,j} (-1)^{i+j} M_{i,j}

where the C_{i,j} represent the matrix cofactors, i.e. C_{i,j} is (-1)^{i+j} times the minor M_{i,j}, which is the determinant of the matrix that results from A by removing the i-th row and the j-th column.

Example

Suppose we want to compute the determinant of

A = begin{bmatrix}-2&2&-3
-1& 1& 3 2 &0 &-1end{bmatrix}.

We can go ahead and use the Leibniz formula directly:

det(A), =, (-2cdot 1 cdot -1) + (-3cdot -1 cdot 0) + (2cdot 3cdot 2)
- (-3cdot 1 cdot 2) - (-2cdot 3 cdot 0) - (2cdot -1 cdot -1)
=, 2 + 0 + 12 - (-6) - 0 - 2 = 18.,

Alternatively, we can use Laplace's formula to expand the determinant along a row or column. It is best to choose a row or column with many zeros, so we will expand along the second column:

det(A), =, (-1)^{1+2}cdot 2 cdot det begin{bmatrix}-1&3 2 &-1end{bmatrix} + (-1)^{2+2}cdot 1 cdot det begin{bmatrix}-2&-3 2&-1end{bmatrix}
=, (-2)cdot((-1)cdot(-1)-2cdot3)+1cdot((-2)cdot(-1)-2cdot(-3))
=, (-2)(-5)+8 = 18.,

A third way (and the method of choice for larger matrices) would involve the Gauss algorithm. When doing computations by hand, one can often shorten things dramatically by cleverly adding multiples of columns or rows to other columns or rows; this does not change the value of the determinant, but may create zero entries which simplifies the subsequent calculations. In this example, adding the second column to the first one is especially useful:

begin{bmatrix}0&2&-3
0 &1 &3 2 &0 &-1end{bmatrix}

and this determinant can be quickly expanded along the first column:

det(A), =, (-1)^{3+1}cdot 2cdot det begin{bmatrix}2&-3 1&3end{bmatrix}
=, 2cdot(2cdot3-1cdot(-3)) = 2cdot 9 = 18.,

Properties

The determinant is a multiplicative map in the sense that

det(AB) = det(A)det(B) , for all n-by-n matrices A and B.
This is generalized by the Cauchy-Binet formula to products of non-square matrices.

It is easy to see that det(rI_n) = r^n , and thus

det(rA) = det(rI_n cdot A) = r^n det(A) , for all n-by-n matrices A and all scalars r.

A matrix over a commutative ring R is invertible if and only if its determinant is a unit in R. In particular, if A is a matrix over a field such as the real or complex numbers, then A is invertible if and only if det(A) is not zero. In this case we have

det(A^{-1}) = det(A)^{-1}. ,

Expressed differently: the vectors v1,...,vn in Rn form a basis if and only if det(v1,...,vn) is non-zero.

A matrix and its transpose have the same determinant:

det(A^mathrm{T}) = det(A). ,

The determinants of a complex matrix and of its conjugate transpose are conjugate:

det(A^*) = det(A)^*. ,
(Note the conjugate transpose is identical to the transpose for a real matrix)

The determinant of a matrix A exhibits the following properties under elementary matrix transformations of A:

  1. Exchanging rows or columns multiplies the determinant by −1.
  2. Multiplying a row or column by m multiplies the determinant by m.
  3. Adding a multiple of a row or column to another leaves the determinant unchanged.

This follows from the multiplicative property and the determinants of the elementary matrix transformation matrices.

If A and B are similar, i.e., if there exists an invertible matrix X such that A = X^{-1} B X, then by the multiplicative property,

det(A) = det(B). ,

This means that the determinant is a similarity invariant. Because of this, the determinant of some linear transformation T : VV for some finite dimensional vector space V is independent of the basis for V. The relationship is one-way, however: there exist matrices which have the same determinant but are not similar.

If A is a square n-by-n matrix with real or complex entries and if λ1,...,λn are the (complex) eigenvalues of A listed according to their algebraic multiplicities, then

det(A) = lambda_{1}lambda_{2} cdots lambda_{n}.,

This follows from the fact that A is always similar to its Jordan normal form, an upper triangular matrix with the eigenvalues on the main diagonal.

Useful identities

Sylvester's determinant theorem states that for any m-by-n matrices A and B,

left.det(I_m + A B^T) = det(I_n + B^T A)right. .

For the case of (column) vectors a and b, this equality becomes

left.det(I + a b^T) = 1 + b^T aright. .

With X a nonsingular m-by-m matrix, this last expression generalizes to

det(X + a b^T) = det(X) (1 + b^T X^{-1} a) .

Block matrices

Suppose, A, B, C, D are ntimes n, ntimes m, mtimes n, mtimes m matrices respectively. Then

detbegin{pmatrix}A& 0 C& Dend{pmatrix} = detbegin{pmatrix}A& B 0& Dend{pmatrix} = det(A) det(D) .
This can be seen from the Leibniz formula. Employing the following identity
begin{pmatrix}A& B C& Dend{pmatrix} = begin{pmatrix}A& 0 C& Iend{pmatrix} begin{pmatrix}I& A^{-1} B 0& D - C A^{-1} Bend{pmatrix}
leads to
detbegin{pmatrix}A& B C& Dend{pmatrix} = det(A) det(D - C A^{-1} B) .
Similar identity with det(D) factored out can be derived analogously.

If d_{ij} are diagonal matrices, then

detbegin{pmatrix}d_{11} & ldots & d_{1c} vdots & & vdots d_{r1} & ldots & d_{rc} end{pmatrix} =
det begin{pmatrix}det(d_{11}) & ldots & det(d_{1c}) vdots & & vdots det(d_{r1}) & ldots & det(d_{rc}) end{pmatrix}.

Relationship to trace

From this connection between the determinant and the eigenvalues, one can derive a connection between the trace function, the exponential function, and the determinant:

det(exp(A)) = exp(operatorname{tr}(A)).

Performing the substitution scriptstyle A ,mapsto, log A in the above equation yields

det(A) = exp(operatorname{tr}(log A)),

which is closely related to the Fredholm determinant. Similarly,

operatorname{tr}(A) = log(det(exp A)).

For n-by-n matrices there are the relationships:

Case n = 1: left.det(A) = operatorname{tr}(A)right.

Case n = 2: left.
det(A) = frac{1}{2} left( operatorname{tr}(A)^2 - operatorname{tr}(A^2) right)right.

Case n = 3: left.
det(A) = frac{1}{6} left( operatorname{tr}(A)^3 - 3 operatorname{tr}(A)operatorname{tr}(A^2) + 2 operatorname{tr}(A^3) right)right.

Case n = 4: left.
det(A) = frac{1}{24} left( operatorname{tr}(A)^4 - 6operatorname{tr}(A)^2operatorname{tr}(A^2) + 3operatorname{tr}(A^2)^2 + 8operatorname{tr}(A)operatorname{tr}(A^3) - 6operatorname{tr}(A^4) right)right.

ldots

which are closely related to Newton's identities.

Derivative

The determinant of real square matrices is a polynomial function from Bbb{R}^{n times n} to Bbb{R}, and as such is everywhere differentiable. Its derivative can be expressed using Jacobi's formula:

d ,det(A) = operatorname{tr}(operatorname{adj}(A) ,dA)

where adj(A) denotes the adjugate of A. In particular, if A is invertible, we have

d ,det(A) = det(A) ,operatorname{tr}(A^{-1} ,dA).

In component form, these are

frac{partial det(A)}{partial A_{ij}}
= operatorname{adj}(A)_{ji} = det(A)(A^{-1})_{ji}.

When epsilon is a small number these are equivalent to

det(A + epsilon X) - det(A)
= operatorname{tr}(operatorname{adj}(A) X) epsilon + {O}(epsilon^2) = det(A) ,operatorname{tr}(A^{-1} X) epsilon + {O}(epsilon^2).

The special case where A is equal to the identity matrix I yields

det(I + epsilon X) = 1 + operatorname{tr}(X) epsilon +O(epsilon^2).

A useful property in the case of 3 x 3 matrices is the following:

A may be written as A = begin{bmatrix}bar{a} & bar{b} & bar{c}end{bmatrix} where bar{a}, bar{b}, bar{c} are vectors, then the gradient over one of the three vectors may be written as the cross product of the other two:

nabla_bar{a}det(A) = bar{b} times bar{c}
nabla_bar{b}det(A) = bar{c} times bar{a}
nabla_bar{c}det(A) = bar{a} times bar{b}.

Abstract formulation

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

A:Vto V,
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 ΛnV. This is a one-dimensional vector space whose elements are written

v_1 wedge v_2 wedge cdots wedge v_n
where each vi is a vector in V and the wedge product ∧ is antisymmetric (i.e., uu = 0). Any linear transformation A : VV induces a linear transformation of ΛnV as follows:
v_1 wedge v_2 wedge cdots wedge v_n mapsto Av_1 wedge Av_2 wedge cdots wedge Av_n.
Since ΛnV is one-dimensional this operation is just multiplication by some scalar that depends on A. This scalar is called the determinant of A. That is, we define det(A) by the equation
Av_1 wedge Av_2 wedge cdots wedge Av_n = (det A),v_1 wedge v_2 wedge cdots wedge v_n.
One can check that this definition agrees with the coordinate-dependent definition given above.

Algorithmic implementation

  • 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 n3 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 n4 exist. An algorithm of Mahajan and Vinay, and Berkowitz is based on closed ordered walks (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 n3 and bit complexity roughly the bit size of the original entries in the matrix times n.

History

Historically, determinants were considered before matrices. Originally, a determinant was defined as a property of a system of linear equations. The determinant "determines" whether the system has a unique solution (which occurs precisely if the determinant is non-zero). In this sense, determinants were first used in Chinese math textbook The Nine Chapters on the Mathematical Art (九章算術, Chinese scholars, around the 3rd century BC). In Europe, two-by-two determinants were considered by Cardano at the end of the 16th century and larger ones by Leibniz and, in Japan, by Seki about 100 years later.

In Japan, determinants were introduced to study elimination of variables in systems of higher-order algebraic equations. They used it to give short-hand representation for the resultant. After the first work by Seki in 1683, Laplace's formula was given by two independent groups of scholars: Tanaka, Iseki (算法発揮,Sampo-Hakki, published in 1690) and Seki, Takebe, Takebe (大成算経, taisei-sankei, written at least before 1710). However, doubts have been raised about how much they recognized the determinant as an independent object.

In Europe, Cramer (1750) added to the theory, treating the subject in relation to sets of equations. The recurrent law was first announced by Bézout (1764).

It was Vandermonde (1771) who first recognized determinants as independent functions. Laplace (1772) gave the general method of expanding a determinant in terms of its complementary minors: 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 of 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 determinants (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 m columns and n rows, which for the special case of m = n reduces to the multiplication theorem. On the same day (November 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 determinant 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; circulants by Catalan, Spottiswoode, Glaisher, and Scott; skew determinants and Pfaffians, in connection with the theory of orthogonal transformation, by Cayley; continuants by Sylvester; Wronskians (so called by Muir) by Christoffel and Frobenius; compound determinants by Sylvester, Reiss, and Picquet; Jacobians and Hessians 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.

See also

References

External links

Search another word or see determinanton Dictionary | Thesaurus |Spanish
Copyright © 2014 Dictionary.com, LLC. All rights reserved.
  • Please Login or Sign Up to use the Recent Searches feature
FAVORITES
RECENT

;