🚀 go-pugleaf

Excerpts from netnews.sci.math.num-analysis: 13-Dec-92 Determinants A.
Lakshmikumaran@andrew (1278)

> I am interested in an efficient routine to compute the determinant of a matrix
> of size n (n < 100), when only one of the terms of the determinant has been 
> changed; in terms of the determinant of the original matrix.

> To make it more clear,

> Step 1: I have this matrix G and i need to compute its determinant
> once. (this is quite easy since there are canned routines for this)

> Step 2: But then i just change only of its elements and compute its
> determinant.
> (Let G' be the new matrix)

> Step 2 is repeated quite a few times and each time G' differs from G at
> just a single
> element. So does any of you know about any public domain routine which could
> perform step 2 more efficiently than just by computing the determinant? (like
> finding the determinant of G' in terms of determinant of G and the
> changed element).

> I looked into different techniques of evaluating the determinant. One
> method was
> to expand the determinant into a sum of n! terms and just grouping the
> (n-1)! terms corresponding to the changed term. But my feeling was this would
> be more time consuming than computing the determinant itself (which is of
> order n**3 if LU factorisation is used). Correct me if i am wrong and 
> is there any simpler technique to compute the determinant in such a case?

> Thanks

> Anand

I thought it would be a better idea to describe the motivation behind my
interest
in such a situation as described above. Probably I don't need to concern myself
with the above problem.

The main motivation behind that was to solve a "non-linear eigenvalue"
problem. 
(I am not sure if i could it call it so, since i have never come across such a
terminology before). I mean, the matrix itself is dependent on the eigenvalues.
Something like G(lambda) = 0.0 where G is a square matix of order n.
(For example: 
IF it was a "linear" eigenvalue problem, then G(lambda) = lambda*I - A.)
And i intend to solve the problem by a Newton Raphson routine. So i need to
find the differential of the determinant of G(lambda) with respect to lambda.

f(lambda) = det(G(lambda))

df(lambda)/dlambda = d/dlambda (det(G(lambda)))

(And i came up with an expression for the same which goes something like this).

If G(lambda) = gij(lambda)	i = 1..n,  j = 1...n  (gij is the i-j th
element of G)

then

df(lambda)/dlambda = (sum I = 1..n)(sum J = 1..n) det(GIJ (lambda))
						- n(n-1)*det(G(lambda))

where 

GIJ(lambda) = dgij/dlambda		if I = i, J = j

		   = gij				if I not equal to i and J not equal to j

(what this means is that GIJ is same as G except that the I-J th element of GIJ
is replaced by the correponding derivative.).

Thus my basic motivation is to find the differential of a determinant in terms
of the determinant of the differentials. If there exists any better way
of dealing
with this problem than the technique which I am using above, then i
wouldn't need 
to find n**2 determinants.

The other option that i have is to use some standard canned package like
MINPACK
in netlib to solve the nonlinear problem G(lambda) = 0.0 and let MINPACK
find the
differential by using some sort of difference procedure.

Anand