1.2.4 Determinants and Permanents

Problem Input | Problem Output

INPUT                    OUTPUT


Input Description: An n x n matrix M.

Problem: What is the determinant |M| or the permanent Perm(M) for matrix m?

Excerpt from The Algorithm Design Manual: Determinants of matrices provide a clean and useful abstraction in linear algebra that can used to solve a variety of problems:

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 best books available for this problem are Matrix Computations by Gene H. Golub and Charles F. Van Loan, and Numerical Recipes in C , Fortran 77 , Fortran 90 , or Pascal , by William H. Press, Saul A. Teukolsky, William T. Vetterling, and Brian P. Flannery. Programs from these books in C and Fortran are also available.


Implementations

  • () (rating 8)
  • Nijenhuis and Wilf: Combinatorial Algorithms (FORTRAN) (rating 4)
  • Combinatorica (Mathematica) (rating 4)
  • LEDA - A Library of Efficient Data Types and Algorithms (C++) (rating 2)

    Related Problems

  • Robust Geometric Primitives
  • Solving Linear Equations
  • Matching


    Previous Problem Next Problem

    View the graph for this file

    Bulletin Board
    About ``The Algorithm Design Manual''.
    Send us Mail
    The Stony Brook Algorithm Repository -- go to front page

    This page last modified on Wed Mar 07, 2001 .