Problem with matrix characterisric equations
Paul Fackler
det(u^2A+uB+C)=0
where A, B and C are given n by n matrices, for the 2n values of u.
In my application, the problem is actually a bit more specialized, in
that A and B are both diagonal, with A having strictly positive
elements. Also C has strictly negative diagonal elements, strictly
positive off-diagonal elements and is rowwise strictly diagonally
dominant.
Many cases of interest are even more specialize, with both A and B of
the form aI and bI (where a and b are scalars and I is the order n
identity matrix). In fact, in some special cases that I can solve by
hand, it turns out that the u are the roots of u^2a+ub+d=0 where d is a
sum of certain elements in C. I don't know how general this result is,
however.
Any insights into numerical or analytical solutions would be of help.
Thanks,
Paul
--
Paul L. Fackler
Department of Agricultural and Resource Economics
North Carolina State University
Raleigh, NC 27695-8109
919-515-4535
paul_f...@ncsu.edu
www4.ncsu.edu/~pfackler
Peter Spellucci
In article <3E3177FA...@gte.net>,
Paul Fackler <hartman...@gte.net> writes:
>I would like to solve the following
>det(u^2A+uB+C)=0
>where A, B and C are given n by n matrices, for the 2n values of u.
>
this assumes A invertible (this is given in your case, as described below)
>In my application, the problem is actually a bit more specialized, in
>that A and B are both diagonal, with A having strictly positive
hence A, B hermitian, A positive definite
>elements. Also C has strictly negative diagonal elements, strictly
>positive off-diagonal elements and is rowwise strictly diagonally
>dominant.
hence C is the negative of a M-Matrix
and therefore is invertible. this implies that 0 is not an eigenvalue
>
>Many cases of interest are even more specialize, with both A and B of
>the form aI and bI (where a and b are scalars and I is the order n
>identity matrix).
this case can be done completely analytically:
let
T*C*inv(T) = diag(lambda_i) +J be the Jordan normal form of C
with lambda_i the eigenvalues of C
then, multiplying det(u^2*a*I +u*b*I+C) by det(T) and det(inv(T))
from the left and the right and using the determinant product theorem we get
product_{i=1 to n} (u^2*a+u*b+lambda_i)=0
yielding the 2n eigenvalues.
the other cases are not that easy.
you can always reduce this problem to an ordinary eigenvalue problem
of a matrix of doubled size:
[ O I ] [x] [x]
= lambda*
[ -inv(A)*B -inv(A)*C ] [y] [y]
if n is not too large, this could be routinely solved by the QR/QL algorithm.
but this is not necessarily a good idea.
there is a very nice overview article exactly on this problem
The Quadratic Eigenvalue Problem
by Francoise Tisseur and Karl Meerbergen
in
SIAM Review 43, pp 235-286 , 2001
which discusses the properties of this problem and possible solution methods.
hope this helps
peter
Zdislav V. Kovarik
On Fri, 24 Jan 2003, Paul Fackler wrote:
> I would like to solve the following
> det(u^2A+uB+C)=0
> where A, B and C are given n by n matrices, for the 2n values of u.
>
> In my application, the problem is actually a bit more specialized, in
> that A and B are both diagonal, with A having strictly positive
> elements. Also C has strictly negative diagonal elements, strictly
> positive off-diagonal elements and is rowwise strictly diagonally
> dominant.
>
> Many cases of interest are even more specialize, with both A and B of
> the form aI and bI (where a and b are scalars and I is the order n
> identity matrix). In fact, in some special cases that I can solve by
> hand, it turns out that the u are the roots of u^2a+ub+d=0 where d is a
> sum of certain elements in C. I don't know how general this result is,
> however.
>
> Any insights into numerical or analytical solutions would be of help.
>
> Thanks,
> Paul
There is a way how to reduce it to a linear generalized
eigenvalue problem -- of double dimension (the price of it):
Define
P =
[ A 0 ]
[ B C ]
Q =
[ 0 I ]
[ -C 0 ]
then we look for det(u*P - Q) = 0
If A is invertible, we have a genuine eigenvalue problem
det (u*I - R) = 0
where I is a (2*n x 2*n) identity, and (inv denoting inverse)
R =
[ 0 inv(A) ]
[-C -B*inv(A)]
How did the (P,Q) form come up? You re-write the condition
(u^2*A + u*B + C) * x = 0
as
u*A*x - y = 0
u*y + u*B*x + C*x = 0
and arrange it in a block matrix equation, with
generalized eigenvector
[ x ]
[ y ]
Hope it helps,
ZVK(Slavek).
Peter Boettcher
> I would like to solve the following
> det(u^2A+uB+C)=0
> where A, B and C are given n by n matrices, for the 2n values of u.
>
> In my application, the problem is actually a bit more specialized, in
> that A and B are both diagonal, with A having strictly positive
> elements. Also C has strictly negative diagonal elements, strictly
> positive off-diagonal elements and is rowwise strictly diagonally
> dominant.
>
> Many cases of interest are even more specialize, with both A and B of
> the form aI and bI (where a and b are scalars and I is the order n
> identity matrix). In fact, in some special cases that I can solve by
> hand, it turns out that the u are the roots of u^2a+ub+d=0 where d is a
> sum of certain elements in C. I don't know how general this result is,
> however.
>
> Any insights into numerical or analytical solutions would be of help.
This looks kinda like an eigenvalue problem. Hmm...
How about POLYEIG? Ignoring all your conditions, this seems to do a
decent job. I don't know how good it might be numerically.
u=polyeig(C,B,A)
--
Peter Boettcher <boet...@ll.mit.edu>
MIT Lincoln Laboratory
MATLAB FAQ: http://www.mit.edu/~pwb/cssm/
Bobby Cheng
For some recent research result, have a look at
http://www.ma.man.ac.uk/~ftisseur/papers.html
Perturbation Theory for Homogeneous Polynomial Eigenvalue Problems (Tisseur
and Dedieu), Linear Algebra Appl., 358:71-74, 2003.
--
Bobby Cheng
The MathWorks, Inc.
http://www.mathworks.com
"Peter Boettcher" <boet...@ll.mit.edu> wrote in message
news:tr4r7yw...@coyote.llan.ll.mit.edu...