Community

Trying to get to the USAMO in 2010? Our AIME Problem Series can help you get there! Click here to enroll today!
Login Register Memberlist Search AoPS Blogs Contests Galleries Forum Index
The time now is Thu Dec 03, 2009 9:55 am
All times are UTC - 8
View posts since last visit
View unanswered posts
Seeking Help On Characteristic Polynomials
Moderators: College Playground Moderators
Post new topic   Reply to topic View previous topicView next topic
4 Posts • Page 1 of 1
Author Message
ArtOfSpace
New Member
New Member

Offline
Joined: 08 Aug 2005
Posts: 6
Location: Europe
Solomon Islands

To rate posts you must be logged in
#1
Seeking Help On Characteristic Polynomials

Can anyone please show me how to compute for " the Characterirstic Polynomial" of a higher degree greater than 3....? Say for instance, a given 4X4 Matrix or 5X5 Matrix A.

I am fine with up to 3 degree of Polyniomial but having difficulties with order 4 or higher.... Adding to that, here is an an example with the solution, which I got out from a book. A given 4x4 Matrix A, The Charact. Polynom.., det[(1 1 2 0), (0 13 14 18), (0 -6 -6 -9), (0 -5 -6 -6)]. The Solution shown is (lamda - 1)^2 (lamda)^2.

Show me how you get to this.....as that is what I have hard times upon. Also notice, [(1 - lamda) (13 - lamda) (-6 - lamda) (-6 - lamda)] on the main diagonal of A.

Is their a much easier way, a general approach and handy to use method to computer for characteristic polynomials of higher orders...? If so, please state:- my book is just a collection of symbols and can't follow up sometimes.

I need your great help ASAP...........!
_________________
Its a great feeling among universal minds.

PostPosted: Mon Aug 29, 2005 1:05 am  Back to top 
  ProfilePM
towersfreak2006
Birch & Swinnerton Dyer
Birch & Swinnerton Dyer


Offline
Joined: 15 Apr 2004
Posts: 2798
Location: College Station, TX or Cambridge, MA
United States

To rate posts you must be logged in
#2
The characteristic polynomial for an n by n matrix A is just \det(A-I_n\lambda). In particular, the one you seek is:
f(\lambda)
= \left|
\begin{array}{cccc}
1-\lambda & 1 & 2 & 0 \\
0 & 13-\lambda & 14 & 18\\
0 & -...

PostPosted: Mon Aug 29, 2005 4:59 pm  Back to top 
  ProfilePMAIMMSNBlogAlbum
jmerry
Birch & Swinnerton Dyer
Birch & Swinnerton Dyer


Offline
Joined: 12 Jun 2004
Posts: 7523
Location: Seattle
United States

To rate posts you must be logged in
#3
ArtOfSpace wrote:
Is their a much easier way, a general approach and handy to use method to computer for characteristic polynomials of higher orders...? If so, please state:- my book is just a collection of symbols and can't follow up sometimes.

Not really. The previous post provided a definition, but computing determinants isn't particularly efficient, and doing it with polynomial entries is even worse. Here are several proposed algorithms:

1: Calculate the determinant of xI-A, using Gaussian elimination (integral domain version)
Order: O(n^4)?
Notes: very complicated to implement and run; requires lots of row interchanges, and far more operations than the standard version.

2: Calculate \det(xI-A) for n specific values of x, then interpolate a polynomial (with appropriate leading coefficient).
Order: O(n^4)
Notes: more operations than the previous (worse constant), but very reliable, easily implemented, and numerically sound.

3: Choose v randomly, and express A with respect to the basis v, Av, A^2v,\dots,A^{n-1}v. This matrix is in companion form, so we can read off the coefficients of the characteristic polynomial from the last column.
Order: O(n^3) (O(n^3) to calculate the basis, and O(n^3) to solve the system and calculate the last column of the transformed matrix)
Notes: Won't work if the minimum polynomial of A has degree less than n (probability 0), won't work if we started in a nontrivial invariant subspace (probability 0), numerically bad if we started close to an invariant subspace, so we might have to try a different starting point. On the other hand, it's only O(n^3) if it works.

If you're dealing with relatively small matrices like 4\times 4 and 5\times5, something like method 2 is probably best. For very large matrices, method 3 has an advantage.

PostPosted: Mon Aug 29, 2005 6:02 pm  Back to top 
  ProfilePM
ArtOfSpace
New Member
New Member

Offline
Joined: 08 Aug 2005
Posts: 6
Location: Europe
Solomon Islands

To rate posts you must be logged in
#4
Hmmmm....I've seen something like that but stop short on tackling it. I thing I have some work to do on what you both proposed....

Thanks...,
_________________
Its a great feeling among universal minds.

PostPosted: Tue Aug 30, 2005 3:52 am  Back to top 
  ProfilePM
Display posts from previous:   Sort by:   
4 Posts • Page 1 of 1
Post new topic   Reply to topic View previous topicView next topic
Jump to:  

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum
You cannot post calendar events in this forum


© Copyright 2008 AoPS Incorporated. All Rights Reserved. • FoundationPrivacyContact Us