The Algorithm Design Manual
About the Book
Programming Challenges

The Stony Brook Algorithm Repository

Steven Skiena
Stony Brook University
Dept. of Computer Science

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.


Implementations

  • LAPACK and LINPACK -- Linear Algebra PACKages (FORTRAN) (rating 10)
  • LAPACK++: LAPACK in C++ (C++) (rating 10)
  • JScience: comprehensive Java library for the scientific community. (Java) (rating 9)
  • JAMA : A Java Matrix Package (Java) (rating 9)
  • Alexander Barvinok C++ code (C++) (rating 8)
  • Nijenhuis and Wilf: Combinatorial Algorithms (FORTRAN) (rating 5)

  • Recommended Books

    Matrix Computations by Gene H. Golub and Charles F. Van Loan Numerical Recipes in Fortran 90 by William H. Press, Saul A. Teukolsky, William T. Vetterling, and Brian P. Flannery Numerical Recipes in Fortran 77 by William H. Press, Saul A. Teukolsky, William T. Vetterling, and Brian P. Flannery
    Numerical Recipes in Pascal by William H. Press, Saul A. Teukolsky, William T. Vetterling, and Brian P. Flannery Numerical Recipes in C by William H. Press, Saul A. Teukolsky, William T. Vetterling, and Brian P. Flannery Data Structures and Algorithms by A. Aho and J. Hopcroft and J. Ullman
    Permanents by H. Minc Combinatorial Algorithms for Computers and Calculators by A. Nijenhuis and H. Wilf A survey of modern algebra by G. Birkhoff and S. MacLane

    Related Problems


      
    Robust Geometric Primitives
      
    Solving Linear Equations
      
    Matching



    This page last modified on 2008-07-10 .
    www.algorist.com