Friday, September 16, 2005

The elegance of mathematics

I’ve been trying to count the number of elementary operations f(k) needed to compute the determinant of a k x k matrix of real elements.

This is the general form for the number of elementary operations:


Since this is a recursive function, we need to define the first case, which is the trivial case of a one-element matrix: f(1) = 0. The determinant is simply the value of the element, and no operations are necessary to arrive at this conclusion.

Now for the bragging bit. I managed to reduce the recursive function into a more manageable function that can be computed without knowledge of f(k-1).



Further investigation and lucky breaks has revealed that f(k) converges to e*k! (e = 2.172818…) very rapidly. At k=18, it is accurate to within 15 significant figures. At k=19, the accuracy is at least 30 significant figures.


The elegance behind mathematics is such that it is possible to convince people that there is a higher being.



Appendix

Re-expressing the function by removing k! from the summation:




Interestingly, the constant e can also be defined as such:




But the series is a sum of infinitely many terms, as compared to f(k) which has only k terms. Thus a finite series such as that found in f(k) does not actually equal e, but converges towards e.

Comparing the definition of e with f(k):




The growth rate of the factorial term is so fast that it very rapidly overwhelms the (k-1) term, and thus (k-1) can be dropped from the approximation. To illustrate the difference in scale using k=15:
k-1 = 15-1 = 14
k! = 15 x 14 x 13 x … x 2 x 1 = 1.3 x 10^12 (there are 13 digits in this number)


Labels:

2 Comments:

Blogger Dzof said...

I think you have to be a little careful in your reasoning when you say:

sum(from n=0 to k-2) (k! / n!)
tends to
e.k! (as k tends to infinity)

Note that
[(lim x->infinity) of x.f(x)]
is not necessarily the same as
x. [(lim x->infinity) of f(x)]
(for example if f(x) = 1/x)

2:28 am, September 17, 2005  
Blogger Lao Chen said...

dzof:
Thanks for pointing that out. It would be something interesting to investigate (learn).

9:48 pm, September 18, 2005  

Post a Comment

<< Home