About the Book

The Stony Brook Algorithm Repository

Steven Skiena
Stony Brook University
Dept. of Computer Science

• By Language
  • C
  • C++
  • C#
  • Java
  • FORTRAN
  • Python
  • Mathematica
  • Pascal
  • ADA
  • Lisp
  • Binary
• By Problem
  • 1.1 Data Structures
    • Dictionaries
    • Priority Queues
    • Suffix Trees and Arrays
    • Graph Data Structures
    • Set Data Structures
    • Kd-Trees
  • 1.2 Numerical Problems
    • Solving Linear Equations
    • Bandwidth Reduction
    • Matrix Multiplication
    • Determinants and Permanents
    • Constrained and Unconstrained Optimization
    • Linear Programming
    • Random Number Generation
    • Factoring and Primality Testing
    • Arbitrary Precision Arithmetic
    • Knapsack Problem
    • Discrete Fourier Transform
  • 1.3 Combinatorial Problems
    • Sorting
    • Searching
    • Median and Selection
    • Generating Permutations
    • Generating Subsets
    • Generating Partitions
    • Generating Graphs
    • Calendrical Calculations
    • Job Scheduling
    • Satisfiability
  • 1.4 Graph Problems -- polynomial-time problems
    • Connected Components
    • Topological Sorting
    • Minimum Spanning Tree
    • Shortest Path
    • Transitive Closure and Reduction
    • Matching
    • Eulerian Cycle / Chinese Postman
    • Edge and Vertex Connectivity
    • Network Flow
    • Drawing Graphs Nicely
    • Drawing Trees
    • Planarity Detection and Embedding
  • 1.5 Graph Problems -- hard problems
    • Clique
    • Independent Set
    • Vertex Cover
    • Traveling Salesman Problem
    • Hamiltonian Cycle
    • Graph Partition
    • Vertex Coloring
    • Edge Coloring
    • Graph Isomorphism
    • Steiner Tree
    • Feedback Edge/Vertex Set
  • 1.6 Computational Geometry
    • Robust Geometric Primitives
    • Convex Hull
    • Triangulation
    • Voronoi Diagrams
    • Nearest Neighbor Search
    • Range Search
    • Point Location
    • Intersection Detection
    • Bin Packing
    • Medial-Axis Transformation
    • Polygon Partitioning
    • Simplifying Polygons
    • Shape Similarity
    • Motion Planning
    • Maintaining Line Arrangements
    • Minkowski Sum
  • 1.7 Set and String Problems
    • Set Cover
    • Set Packing
    • String Matching
    • Approximate String Matching
    • Text Compression
    • Cryptography
    • Finite State Machine Minimization
    • Longest Common Substring
    • Shortest Common Superstring
• Algorithm Links
  • Algorithm Lectures
  • Algorithm Design Manual Information
  • CSE 373 Course page
  • NIST Dictory of Algorithms and Data Structures
  • World of Mathematics
  • Programming Challenges
  • Graduate Study Opportuinties

1.2.4 Determinants and Permanents

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:

• 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.
• Computing the area or volume of a triangle, tetrahedron, or other simplicial complex. These quantities are a function of the magnitude of the determinant.

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.

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