This question is tangentially related to LA, but it seemed more fitting than "MATRICES LULZ". Basically, my question is, how can one determine the determinant of a n x n square matrix formulaically as opposed to heuristically?
Bear in mind, this is worth 25% of your final grade.
Also, in b4 steamwin.
Name:
Anonymous2007-10-26 19:26
Heuristically? You must be new to math.
A relatively fast (O(n^3)), easy way to get the determinant of a matrix A is to do Gaussian Elimination on the matrix. Start out with a helper variable d = 1. Every time you swap two rows, multiply d by -1. Every time you multiply a row by c =/= 0, multiply d by c. Every time you add a (non-zero) multiple of a row to another row, leave d alone. Then the determinant equals d * det A' . Since A' is in reduced row echelon form, its determinant equals 1 or 0. Also, wikipedia.
Name:
Anonymous2007-10-26 19:42
how do you solve for a determinant heuristically?
Name:
Anonymous2007-10-26 20:00
I guess you want the 'seed vector' method as opposed to the 'solve the characteristic polynomial' method.
Um, I forget.
Name:
Anonymous2007-10-26 20:35
det(A) = Sum[s in Sn){sig(s)Product[1<=i<= n]a(i,s(i))}
Where Sn is permutation group of n elements, sig(s) is the signature function on s in Sn.
At least, this is the formal definition of determinant. You can go on to show that it is the only "volume form" for columns of matrices, and that it corresponds to one's workable algorithms for obtaining the det.
Name:
Anonymous2007-10-26 23:07
If A is sparse or structured you can find det(A) in subcubic time (e.g., Toeplitz can be done in O(n log n) using so-called "superfast" solvers, though the overhead constant is really big) using a variant of the Berlekamp-Massey algorithm and Krylov subspaces. It's in a 1986 paper by Weidemann in one of the IEEE journals, or check out von zur Gathen and Gerhard's _Modern Computer Algebra_. More generally it's called "black-box linear algebra" and is used quite a bit these days.