Find s, such that det(A+s*D) = d.

Given a non-sigular matrix A, an arbitrary matrix D, and a real or complex number d, I want to see any short-cut to find the numerical number s, such that M = A+s*D, and det(M) = d. Specially, the matrix M is singular if d = 0.

[John D'Errico]

Use of the determinant is a TERRIBLE way to solve any problem in general. While it is mathematically valid, it ignores the fact that computation using floating point numbers in a finite precision is not mathematics.

Anyway, there is no reason to presume that s is unique for any given value of d. It need not be so for general matrices A and D.

And if you insist on solving the problem as you have posed it, I'm not sure why it is you expect some magical solution to exist that does not involve a rootfinder.

[Feng Cheng Chang]

I am not so sure why it is so terrible to use the determinant in mathematics.

Anyway I found that s is unique for d = 0. For example:

A = rand(5), D = ones(5), and det(A+s*D) = 0, if s = -1/sum(sum(inv(A))).

The value of s is not unique if d != 0, and it involves polynominal rootfinding.

I am pretty sure I can get the results by applying rootfinding.

Thank you very much for mentioning about the rootfinding

[SK]

Why do you say s is unique for d == 0 ? It is most definitely not unique, whether or not d is zero. See my post below.

[SK]

Generally you avoid computing determinants (using the recursive formula) whenever possible because of the large string of multiplications - which is often inefficient. For random determinants, you may not see so much error, but even a slight bias in your errors will lead to garbage if the matrix is large enough.

[Feng Cheng Chang]

Sorry, I should say that for any n,

A = rand(n), D = ones(n), d = det(A+D*s) = 0.

where s is unique, determined by

s = -1/sum(sum(inv(A)).

In general, s is not unique for d = 0 !

[John D'Errico]

1. s is NOT unique for any general d, INCLUDING zero. It MAY be so. And the matrix you chose may have it so. However, I picked a different one for a test case, and found that the plot of det(A+s*D) was not monotone, in fact, it crossed the axes at 3 points. So there were 3 distinct solutions for that case.

Of course, feel free not to believe me. But then I wonder what inference I should make of this plot?

It seems to cross zero for three distinct values of s. But then, what do I know?

The matrices I chose in that example were random 5x5 matrices. You said this applies for any general matrix, so I picked that order. Using symbolic tools (reasonable here since the matrices were only 5x5)...

sympoly s
det(A+s*D)
ans =
    -5.80856344609985 - 53.5024923077258*s + 53.130597064771*s^2 + 72.7248763204719*s^3 + 0.67894325278629*s^4 - 14.2544491127619*s^5

roots(ans)
ans =
          2.4670662498904 +                     0i
        -1.48313778219639 +     0.595028644066688i
        -1.48313778219639 -     0.595028644066688i
        0.646831879916377 +                     0i
      -0.0999922959160047 +                     0i

I guess it LOOKS like there are three real roots, but again, I may be wrong. (By the way, this is a better way to solve the problem than to use a general zero finder, as long as the matrices are small.)

As far as det being a poor thing to use, I did NOT say that in regards to mathematics. What I did say was that computer programming is NOT mathematics! Yes, it is often related, and it looks like mathematics. But the intrusion of floating point arithmetic makes many things that are valid to do in mathematics no longer a good idea. Use of the determinant is one of them. A couple of reasons off the top of my head are:

1. Determinants are computationally a nasty thing to do, at least if you use symbolic tools, especially if you use a recursive algorithm as many are taught in school. MATLAB uses an LU factorization for computation of a numerical determinant, so it is more stable as well as faster than the other methods.

2. Determinants are poorly behaved in terms of scaling, since it is frightfully easy to make a matrix determinant as small or as large as you want, merely by scaling your matrix. Remember that for an nxn matrix,

det(k*A) = det(A)*k^n

So it is terribly easy to have a matrix determinant that is wildly less than eps, yet the matrix is strictly non-singular.

[Feng Cheng Chang]

Thank you very much for your length comments. I will try my best.

I still believe that s is unique for d = det(A+D*s) = 0, if D = ones(n), and s = -1/sum(sum(inv(A))).

Let us have an example: A = magic(5), D = ones(5), then we get s = 13, det(M) = det(A+D*S) = 0. Can you find any other s sch that det(M) = 0 ?

[John D'Errico]

I just showed a simple example, generated from random matrices that contradicted your belief.

This has nothing to do with belief. A single contradiction is sufficient to prove your belief is worth nothing. That some specific matrix has a unique solution is irrelevant. As I have shown, this can be solved as a polynomial roots problem, but that polynomial has no reason to be always monotonic.

[Feng Cheng Chang]

I would like to know what your simple example is. Any way I still believe the following:

Given a nxn non-singular matrix A, and D = ones(n) in

 det(A+D*s) = 0

s is uniquely found to be

 s = -1/r(1),
 r = eig(D*inv(A))

where r(1) is the only non-zero element in a vector r.

For example,

 r = eig(ones(7)*inv(magic(7)))'

=> 0.02439 0 0 0 0 0 0

By the way I found that

eig(ones(n))   =>    [ n, 0, 0, ......., 0 ].

Answer 1

[SK]

Since A is non-singular, we can write (warning: below is math, not code)

    M = A + s*D
=>  M/A = I + sD/A     (where D/A stands for D*inv(A))
=>  lambda*M/A = lambda*I - D/A     (where lambda = -1/s)

Therefore you need to solve the eigenvalue problem:

    (lambda*I - D/A)*v = 0

for lambda. You can find lambda using:

   lambda = eig(D/A)

setting s = -1./lambda, you have n solutions (with multiplicity) for d = 0, where n is the size of A.

NOTE: Don't try to find eigen vectors (you dont need them here anyway) using Matlab's eig(), since it wont work if eigenvalues are repeated.

Now for non-zero d, we want:

   d/det(A) = det(I + s*D/A)

since det(D/A) = product(lambda), we have to choose s so that

    product_over_i(1 + s*lambda(i)) = d/det(A)

So your "short-cut" procedure is:

1. Find vector of eigenvalues, lambda, of D/A
2. Solve prod(1 + s*lambda) = d/det(A)

(1) should not be a problem even for very large matrices.

I'm not sure about (2) unless n is not too large. You could try the roots() or fzero() functions in Matlab. Note that if you use roots(), you will have to compute the coefficients of the polynomial first from the product in (2) and you may lose a lot of precision in computing the coefficients themselves. I think it would be better to use fzero().

Also note that there are n solutions in general, so you'll have to find a way to choose the solution based on your needs and also make an appropriate initial guess.

[edited to correct sign error].

[Feng Cheng Chang]

Thank you very much for your answer. In fact I have already gotten the results followed the hint from Dr. john D'Errico. Here is the process similar to what you derived:

r = roots([-d/det(A),zeros(1,size(A,1))],poly(D*inv(A)));
s = -1/r(1);
M = A+D*s;
dM = det(M);

Then dM = d, within floating point error. And s is not unique, r must be non-zero root.

[SK]

OK. I guess you mean:

r = roots( [-d/det(A),zeros(1,size(A,1))] + poly(D*inv(A)) );

Also as Roger Stafford has suggested you can use fsolve:

D = rand(5);
A = rand(5);
d = 1;
lambda = eig(D/A);
c = d/det(A);

hcx2vec = @(F) [real(F); imag(F)];
hfunc = @(s) hcx2vec(prod(1 + complex(s(1), s(2))*lambda) - c);

s_init = -1/lambda(1);
s = fsolve(hfunc, hcx2vec(s_init));

Check:

det(A + complex(s(1), s(2))*D)

You could also choose s_init to be say -1/lambda(i) for any i.

I just mention it because as the matrix A gets larger, its determinant can become huge or tiny resulting in unacceptable loss of precision very quickly. For example, with A = rand(50), you still get acceptable results, but with A = rand(100), you have no chance. With fsolve you can tweak the tolerances - so it may help. Perhaps it is also possible to scale/normalize the problem in some way.

Regards.

[Feng Cheng Chang]

Thank you, SK, for correcting a very critical typing error.

Also I would like to thank RS for his nice suggestion.

Answer 2

[Roger Stafford]

If d is real and only real roots are being sought for s, you can simply write a function that accepts a scalar value s and computes det(A+s*D)-d, and then call on matlab's 'fzero' to adjust s to seek a zero value.

If d is complex or you are also seeking complex roots, you can instead call on 'fsolve', calling on your function with the separate real and imaginary parts of s and giving the separate real and imaginary parts of det(A+s*D)-d as a result.

Note that in general there will be n solutions to your equation where your matrices are n-by-n in size, since your equation is actually an nth-degree polynomial equation in s. However, it does not look easy to compute the coefficients of such a polynomial, so it would be difficult to use the 'roots' function.