## Application Snippet: Enumeration of Spanning Trees.

This week in my linear algebra class, I started discussing determinants.  We defined/recalled the definition of the determinant of a $latex 2\times 2$ matrix and then defined determinants of higher order square matrices inductively, using cofactor expansion about the first row.

Requiring the students to have( and use) a calculator capable of matrix operations has kept technology and computation parallel with theory in the class, and I jumped on the opportunity to discuss how slow the computation of determinants can be when done by this definition.  The fact that the definition is inductive means that the computation can be carried out by recursion.  But since the cofactor expansion about the first row of an $latex n\times n$ involves computing determinants of $latex (n-1)\times (n-1)$ submatrices, you can quickly explain why it takes more than $latex n!$ floating point operations in general to compute a determinant.  One thing you should get…

View original post 887 more words