 Forum index » Science and Technology » Math » num-analysis
Author Message
Jeremy Watts
science forum Guru Wannabe

Joined: 24 Mar 2005
Posts: 239 Posted: Wed Jul 19, 2006 10:45 am    Post subject: Re: jordan decomposition and generalized eigenvectors "Helmut Jarausch" <jarausch@igpm.rwth-aachen.de> wrote in message
news:44BE063B.50905@igpm.rwth-aachen.de...
 Quote: Jeremy Watts wrote: ok, firstly excuse the length of this post and the fact that it is cross posted.... (i really didnt know the most appropriate NG to send it to....) anyway, i am using an algorithm to perform a jordan decomposition taken from 'schaums outlines for matrix operations'. the algorithm states on p.82 that to form a canonical basis (this being the first step in forming a jordan decomposition) , then :- Step 1. Denote the multiplicity of lambda as m , and determine the smallest positive integer p for which the rank of (A - lambda I )^p equals n-m , where n denotes the number of rows (and columns in A), lambda denotes an eigenvalue of A and I is the identity matrix. Step 2. For each integer k between 1 and p, inclusive, compute the 'eigenvalue rank number Nk' as :- Nk = rank(A - lambda I)^(k-1) - rank(A - lambdaI)^k Each Nk is the number of generalized eigenvectors of rank k that will appear in the canonical basis Step 3. Determine a generalized eigenvector of rank p, and construct the chain generated by this vector. Each of these vectors is part of the canonical basis. Step 4. Reduce each positive Nk (k = 1,2,...,p) by 1. If all Nk are zero then stop; the procedure is complete for this particular eigenvalue. If not then continue to Step 5. Step 5. Find the highest value of k for which Nk is not zero, and determine a generalized eigenvector of that rank which is linearly independent of all previously determined generalized eigenvectors associated with lambda. Form the chain generated by this vector, and include it in the basis. Return to Step 4. Now, the matrix I am using the above procedure on is :- 0 0 1 0 i 0 -9+6i 0 1 0 A = 0 0 8 i 1 0 0 0 8 0 0 2i 0 -9 8 Now the eigenvalues and multiplicities are :- -9+6i with multiplicity 1 8 with multiplicity 3 0 with multiplicity 1 Starting with -9+6i and going through the procedure then i make the value of p in step 1 as p = 5. This immediately arouses my suspicions as it looks too high, as Step 3 not only fails to find a generalized eigenvector of rank 5, but also even if it existed, the vector plus its chain would be of length 5, and so fill the entire canonical basis with the vectors generated by just the first eigenvalue . By the way I am using the definition of a 'generalized eigenvector' as the one given in the same book, on the same page in fact as the above procedure, which is :- "A vector Xm is a generalized eigenvector of rank m for the square matrix A and associated eigenvalue lambda if :- (A - lambda I)^m Xm = 0 but (A - lambda I)^(m-1)Xm =/= 0 So, firstly does anyone agree that a generalized eigenvector of rank 5 cannot exist for the matrix A with the eigenvalue -9+6i , and if so what is going wrong here generally? The Jordan form is known to be notoriously instable. Therefore it shouldn't be used in numerical calculations.

you can say that again... it wasnt long after posting this that i realised
the problem
was me truncating the eigen value. i was using something like -8.99999...
+ 5.99999i...
to something like 30 decimal places!!! i thought that being this close to
the true
value would make no difference, but in fact it had a catastrophic effect on
the value of
the rank obtained in step 1. the true value should be 1 of course (as
peter pointed out)
but even having a number incredibly close to the real eigenvalue produced an
erroneous value of 5.....

anyway thanks to you and peter for responding.

by the way do either of you know whether there exist any iterative methods
to find a jordan decomposition?

 Quote: In most cases (e.g. systems of ODEs) the extremely stable 'Schur' form is an alternative. This gives an orthogonal(!) matrix U and an upper triangular matrix T s.t. U'*A*U = T (where ' denotes the Hermitian of a matrix = transposed and complex conjugated). For your matrix I get (with Scilab (free)) [U,T]=schur(A) T = 0 1. i 0 0 0 8. 1. 0 i 0 0 8. 2.i - 9. 0 0 0 - 9. + 6.i 1. 0 0 0 0 8. U = 1. 0 0 0 0 0 0 0 1. 0 0 1. 0 0 0 0 0 0 0 1. 0 0 1. 0 0 -- Helmut Jarausch Lehrstuhl fuer Numerische Mathematik RWTH - Aachen University D 52056 Aachen, Germany Helmut Jarausch
science forum beginner

Joined: 08 Jul 2005
Posts: 49 Posted: Wed Jul 19, 2006 10:15 am    Post subject: Re: jordan decomposition and generalized eigenvectors Jeremy Watts wrote:
 Quote: ok, firstly excuse the length of this post and the fact that it is cross posted.... (i really didnt know the most appropriate NG to send it to....) anyway, i am using an algorithm to perform a jordan decomposition taken from 'schaums outlines for matrix operations'. the algorithm states on p.82 that to form a canonical basis (this being the first step in forming a jordan decomposition) , then :- Step 1. Denote the multiplicity of lambda as m , and determine the smallest positive integer p for which the rank of (A - lambda I )^p equals n-m , where n denotes the number of rows (and columns in A), lambda denotes an eigenvalue of A and I is the identity matrix. Step 2. For each integer k between 1 and p, inclusive, compute the 'eigenvalue rank number Nk' as :- Nk = rank(A - lambda I)^(k-1) - rank(A - lambdaI)^k Each Nk is the number of generalized eigenvectors of rank k that will appear in the canonical basis Step 3. Determine a generalized eigenvector of rank p, and construct the chain generated by this vector. Each of these vectors is part of the canonical basis. Step 4. Reduce each positive Nk (k = 1,2,...,p) by 1. If all Nk are zero then stop; the procedure is complete for this particular eigenvalue. If not then continue to Step 5. Step 5. Find the highest value of k for which Nk is not zero, and determine a generalized eigenvector of that rank which is linearly independent of all previously determined generalized eigenvectors associated with lambda. Form the chain generated by this vector, and include it in the basis. Return to Step 4. Now, the matrix I am using the above procedure on is :- 0 0 1 0 i 0 -9+6i 0 1 0 A = 0 0 8 i 1 0 0 0 8 0 0 2i 0 -9 8 Now the eigenvalues and multiplicities are :- -9+6i with multiplicity 1 8 with multiplicity 3 0 with multiplicity 1 Starting with -9+6i and going through the procedure then i make the value of p in step 1 as p = 5. This immediately arouses my suspicions as it looks too high, as Step 3 not only fails to find a generalized eigenvector of rank 5, but also even if it existed, the vector plus its chain would be of length 5, and so fill the entire canonical basis with the vectors generated by just the first eigenvalue . By the way I am using the definition of a 'generalized eigenvector' as the one given in the same book, on the same page in fact as the above procedure, which is :- "A vector Xm is a generalized eigenvector of rank m for the square matrix A and associated eigenvalue lambda if :- (A - lambda I)^m Xm = 0 but (A - lambda I)^(m-1)Xm =/= 0 So, firstly does anyone agree that a generalized eigenvector of rank 5 cannot exist for the matrix A with the eigenvalue -9+6i , and if so what is going wrong here generally?

The Jordan form is known to be notoriously instable.
Therefore it shouldn't be used in numerical calculations.
In most cases (e.g. systems of ODEs) the extremely stable 'Schur' form is an
alternative. This gives an orthogonal(!) matrix U and an upper triangular
matrix T s.t. U'*A*U = T (where ' denotes the Hermitian of a matrix =
transposed and complex conjugated).
For your matrix I get (with Scilab (free))

[U,T]=schur(A)
T =

0 1. i 0 0
0 8. 1. 0 i
0 0 8. 2.i - 9.
0 0 0 - 9. + 6.i 1.
0 0 0 0 8.
U =

1. 0 0 0 0
0 0 0 1. 0
0 1. 0 0 0
0 0 0 0 1.
0 0 1. 0 0

--
Helmut Jarausch

Lehrstuhl fuer Numerische Mathematik
RWTH - Aachen University
D 52056 Aachen, Germany Peter Spellucci
science forum Guru

Joined: 29 Apr 2005
Posts: 702 Posted: Wed Jul 19, 2006 10:10 am    Post subject: Re: jordan decomposition and generalized eigenvectors In article <Y1avg.35738\$1g.26846@newsfe1-win.ntli.net>,
"Jeremy Watts" <jwatts1970@hotmail.com> writes:
 Quote: ok, firstly excuse the length of this post and the fact that it is cross posted.... (i really didnt know the most appropriate NG to send it to....) anyway, i am using an algorithm to perform a jordan decomposition taken from 'schaums outlines for matrix operations'. the algorithm states on p.82 that to form a canonical basis (this being the first step in forming a jordan decomposition) , then :- Step 1. Denote the multiplicity of lambda as m , and determine the smallest positive integer p for which the rank of (A - lambda I )^p equals n-m , where n denotes the number of rows (and columns in A), lambda denotes an eigenvalue of A and I is the identity matrix. Step 2. For each integer k between 1 and p, inclusive, compute the 'eigenvalue rank number Nk' as :- Nk = rank(A - lambda I)^(k-1) - rank(A - lambdaI)^k Each Nk is the number of generalized eigenvectors of rank k that will appear in the canonical basis Step 3. Determine a generalized eigenvector of rank p, and construct the chain generated by this vector. Each of these vectors is part of the canonical basis. Step 4. Reduce each positive Nk (k = 1,2,...,p) by 1. If all Nk are zero then stop; the procedure is complete for this particular eigenvalue. If not then continue to Step 5. Step 5. Find the highest value of k for which Nk is not zero, and determine a generalized eigenvector of that rank which is linearly independent of all previously determined generalized eigenvectors associated with lambda. Form the chain generated by this vector, and include it in the basis. Return to Step 4. Now, the matrix I am using the above procedure on is :- 0 0 1 0 i 0 -9+6i 0 1 0 A = 0 0 8 i 1 0 0 0 8 0 0 2i 0 -9 8 Now the eigenvalues and multiplicities are :- -9+6i with multiplicity 1 8 with multiplicity 3 0 with multiplicity 1 Starting with -9+6i and going through the procedure then i make the value of p in step 1 as p = 5. This immediately arouses my suspicions as it looks too

this is a misunderstanding:
you have a simple eigenvalue, multiplicity =1
rank deficiency of A-lambda*I =1
hence there is a (normal) eigenvector only
hth
peter

be warned: all this is o.k. if you compute anything formally,
roundoff error free. it is absolutely senseless to follow this
approach if you compute numerically. this begins already with
distinguishing multiple eigenvalues and clusters of very nearby eigenvalues
continues with rank determination (under roundoff, many singular matrices
appear as invertible) and the instability of computing the Jordan chain.
if you really must do that numerically, then consult
Golub&van Loan, there a method is described. but also here you will
finally need to know the _strucuture_ of J beforehand in order to get
a save method

 Quote: high, as Step 3 not only fails to find a generalized eigenvector of rank 5, but also even if it existed, the vector plus its chain would be of length 5, and so fill the entire canonical basis with the vectors generated by just the first eigenvalue . By the way I am using the definition of a 'generalized eigenvector' as the one given in the same book, on the same page in fact as the above procedure, which is :- "A vector Xm is a generalized eigenvector of rank m for the square matrix A and associated eigenvalue lambda if :- (A - lambda I)^m Xm = 0 but (A - lambda I)^(m-1)Xm =/= 0 So, firstly does anyone agree that a generalized eigenvector of rank 5 cannot exist for the matrix A with the eigenvalue -9+6i , and if so what is going wrong here generally? thanks Jeremy Watts
science forum Guru Wannabe

Joined: 24 Mar 2005
Posts: 239 Posted: Tue Jul 18, 2006 6:48 pm    Post subject: jordan decomposition and generalized eigenvectors ok, firstly excuse the length of this post and the fact that it is cross posted.... (i really didnt know the most appropriate NG to send it to....) anyway, i am using an algorithm to perform a jordan decomposition taken from 'schaums outlines for matrix operations'. the algorithm states on p.82 that to form a canonical basis (this being the first step in forming a jordan decomposition) , then :- Step 1. Denote the multiplicity of lambda as m , and determine the smallest positive integer p for which the rank of (A - lambda I )^p equals n-m , where n denotes the number of rows (and columns in A), lambda denotes an eigenvalue of A and I is the identity matrix. Step 2. For each integer k between 1 and p, inclusive, compute the 'eigenvalue rank number Nk' as :- Nk = rank(A - lambda I)^(k-1) - rank(A - lambdaI)^k Each Nk is the number of generalized eigenvectors of rank k that will appear in the canonical basis Step 3. Determine a generalized eigenvector of rank p, and construct the chain generated by this vector. Each of these vectors is part of the canonical basis. Step 4. Reduce each positive Nk (k = 1,2,...,p) by 1. If all Nk are zero then stop; the procedure is complete for this particular eigenvalue. If not then continue to Step 5. Step 5. Find the highest value of k for which Nk is not zero, and determine a generalized eigenvector of that rank which is linearly independent of all previously determined generalized eigenvectors associated with lambda. Form the chain generated by this vector, and include it in the basis. Return to Step 4. Now, the matrix I am using the above procedure on is :- 0 0 1 0 i 0 -9+6i 0 1 0 A = 0 0 8 i 1 0 0 0 8 0 0 2i 0 -9 8 Now the eigenvalues and multiplicities are :- -9+6i with multiplicity 1 8 with multiplicity 3 0 with multiplicity 1 Starting with -9+6i and going through the procedure then i make the value of p in step 1 as p = 5. This immediately arouses my suspicions as it looks too high, as Step 3 not only fails to find a generalized eigenvector of rank 5, but also even if it existed, the vector plus its chain would be of length 5, and so fill the entire canonical basis with the vectors generated by just the first eigenvalue . By the way I am using the definition of a 'generalized eigenvector' as the one given in the same book, on the same page in fact as the above procedure, which is :- "A vector Xm is a generalized eigenvector of rank m for the square matrix A and associated eigenvalue lambda if :- (A - lambda I)^m Xm = 0 but (A - lambda I)^(m-1)Xm =/= 0 So, firstly does anyone agree that a generalized eigenvector of rank 5 cannot exist for the matrix A with the eigenvalue -9+6i , and if so what is going wrong here generally? thanks  Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
 The time now is Tue Mar 26, 2019 4:25 am | All times are GMT Forum index » Science and Technology » Math » num-analysis
 Jump to: Select a forum-------------------Forum index|___Science and Technology    |___Math    |   |___Research    |   |___num-analysis    |   |___Symbolic    |   |___Combinatorics    |   |___Probability    |   |   |___Prediction    |   |       |   |___Undergraduate    |   |___Recreational    |       |___Physics    |   |___Research    |   |___New Theories    |   |___Acoustics    |   |___Electromagnetics    |   |___Strings    |   |___Particle    |   |___Fusion    |   |___Relativity    |       |___Chem    |   |___Analytical    |   |___Electrochem    |   |   |___Battery    |   |       |   |___Coatings    |       |___Engineering        |___Control        |___Mechanics        |___Chemical

 Topic Author Forum Replies Last Post Similar Topics possible to use Generalized Method of Moments for this pr... comtech Math 1 Thu Jul 20, 2006 12:49 am jordan decomposition and generalized eigenvectors Jeremy Watts Undergraduate 0 Tue Jul 18, 2006 6:49 pm symmetry in eigenvectors Al1131 Math 3 Mon Jul 17, 2006 1:09 pm Matrix functions via EVD decomposition ~Glynne num-analysis 7 Sat Jul 15, 2006 5:51 am Tensor Decomposition xyz91234@yahoo.com Math 2 Mon Jul 10, 2006 3:49 am