next up previous contents index CD CD Algorithms
Next: Constrained and Unconstrained Optimization Up: Numerical Problems Previous: Matrix Multiplication

Determinants and Permanents



Input description: An tex2html_wrap_inline27121 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:

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


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

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 gif.   The determinant of M is simply the product of the diagonal elements of the LU-decomposition of M, which can be found in tex2html_wrap_inline27141 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 tex2html_wrap_inline27143 time.   The fundamental difference is that tex2html_wrap_inline27145 , while tex2html_wrap_inline27147 . Fortunately, there are permanent algorithms that prove to be considerably faster than the O(n!) definition, running in tex2html_wrap_inline27151 time. Thus finding the permanent of a tex2html_wrap_inline27153 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 gif. A C++ program to compute determinants in tex2html_wrap_inline27155 time is embedded in LEDA (see Section gif).       

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

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 tex2html_wrap_inline27157 time using fast   matrix multiplication, as shown in [AHU83]. Section gif 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 tex2html_wrap_inline27159 -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 gif), matching (see page gif), geometric primitives (see page gif).      

next up previous contents index CD CD Algorithms
Next: Constrained and Unconstrained Optimization Up: Numerical Problems Previous: Matrix Multiplication

Mon Jun 2 23:33:50 EDT 1997