Determinants and Permanents

  

 

Input description: An matrix M.

Problem description: What is the determinant |M| or the permanent perm(M) of the matrix m?

Discussion: Determinants of matrices provide a clean and useful abstraction in linear   algebra that can used to solve a variety of problems:

• Testing whether a matrix is singular, meaning that the matrix does not have an inverse. A matrix M is singular iff |M| = 0.   
• Testing whether a set of d points lies on a plane in fewer than d dimensions.     If so, the system of equations they define is singular, so |M| = 0.
• Testing whether a point lies to the left or right of a line or plane.     This problem reduces to testing whether the sign of a determinant is positive or negative, as discussed in Section .
• Computing the area or volume of a triangle, tetrahedron, or other simplicial complex. These quantities are a function of the magnitude of the determinant, as discussed in Section .   

The determinant of a matrix M is defined as the sum over all n! possible permutations of the n columns of M:

where is the number of pairs of elements out of order (called inversions) in permutation .    

A direct implementation of this definition yields an O(n!) algorithm, as does the cofactor expansion method we learned in high school.   However, better algorithms are available to evaluate determinants based on LU-decomposition. They are discussed in Section .   The determinant of M is simply the product of the diagonal elements of the LU-decomposition of M, which can be found in time.

A closely related function, called the permanent,   arises often in combinatorial problems.   For example, the permanent of the adjacency matrix of a graph G counts the number of perfect matchings in G.    The permanent of a matrix M is defined by

differing from the determinant only in that all products are positive.

Surprisingly, it is NP-hard to compute the permanent, even though the determinant can easily be computed in time.   The fundamental difference is that , while . Fortunately, there are permanent algorithms that prove to be considerably faster than the O(n!) definition, running in time. Thus finding the permanent of a matrix is not out of the realm of possibility.

Implementations: The linear algebra package LINPACK contains a variety of Fortran routines for computing determinants, optimized for different data types and matrix structures. It can be obtained from Netlib, as discussed in Section . A C++ program to compute determinants in time is embedded in LEDA (see Section ).       

Nijenhuis and Wilf [NW78] provide an efficient Fortran routine to compute the permanent of a matrix. See Section .

Notes: Cramer's rule reduces the problems of matrix inversion and solving linear systems to that of computing determinants. However, algorithms based on LU-determination are faster. See [BM53] for an exposition on Cramer's rule.  

Determinants can be computed in time using fast   matrix multiplication, as shown in [AHU83]. Section discusses such algorithms. A fast algorithm for computing the sign of the determinant,     an important problem for performing robust geometric computations, is due to Clarkson [Cla92].

The problem of computing the permanent was shown to be #P-complete by Valiant [Val79], where #P is the   class of problems solvable on a ``counting'' machine in polynomial time. A counting machine returns the number of distinct solutions to a problem. Counting the number of Hamiltonian cycles in a graph is a #P-complete problem that is trivially NP-hard (and presumably harder),   since any count greater than zero proves that the graph is Hamiltonian. Counting problems can be #P-complete even if the corresponding decision problem can be solved in polynomial time, as shown by the permanent and perfect matchings.

Minc [Min78] is the definitive work on permanents. A variant of an -time algorithm due to Ryser for computing the permanent is presented in [NW78]. Recently, probabilistic algorithms have been developed for estimating the permanent [FJ95].

Related Problems: Solving linear systems (see page ), matching (see page ), geometric primitives (see page ).