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

8 views (last 30 days)
Feng Cheng Chang
Feng Cheng Chang on 28 Oct 2014
Commented: Feng Cheng Chang on 31 Oct 2014
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.
  9 Comments
John D'Errico
John D'Errico on 30 Oct 2014
Edited: John D'Errico on 30 Oct 2014
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
Feng Cheng Chang on 31 Oct 2014
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 ].

Sign in to comment.

Accepted Answer

SK
SK on 29 Oct 2014
Edited: SK on 30 Oct 2014
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].
  3 Comments
SK
SK on 31 Oct 2014
Edited: SK on 31 Oct 2014
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
Feng Cheng Chang on 31 Oct 2014
Thank you, SK, for correcting a very critical typing error.
Also I would like to thank RS for his nice suggestion.

Sign in to comment.

More Answers (1)

Roger Stafford
Roger Stafford on 30 Oct 2014
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.

Categories

Find more on Sparse Matrices in Help Center and File Exchange

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!