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

This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s