Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am currently studying the QR algorithm described in Computing the eigenvalues of a companion matrix and have come to something that has me scratching my head. I'm trying to work this method out on the companion matrix of a degree nine polynomial,

c0 + c1*t + c2*t2 + c3*t3 + c4*t4 + c5*t5 + c6*t6 + c7*t7 + c8*t8 + c9*t9

The companion matrix of this function would be

| 0 0 0 0 0 0 0 0 0 -c0 |
| 1 0 0 0 0 0 0 0 0 -c1 |
| 0 1 0 0 0 0 0 0 0 -c2 |
| 0 0 1 0 0 0 0 0 0 -c3 |
| 0 0 0 1 0 0 0 0 0 -c4 |
| 0 0 0 0 1 0 0 0 0 -c5 |
| 0 0 0 0 0 1 0 0 0 -c6 |
| 0 0 0 0 0 0 1 0 0 -c7 |
| 0 0 0 0 0 0 0 1 0 -c8 |
| 0 0 0 0 0 0 0 0 1 -c9 |

In the method described, the companion matrix is represented as a unitary matrix U plus two vectors, u and v. The unitary matrix U is represented as a matrix with all subdiagonal entries as well as entry 1, n (the upper right most entry) equal to one and all other entries zero.

| 0 0 0 0 0 0 0 0 0 1 |
| 1 0 0 0 0 0 0 0 0 0 |
| 0 1 0 0 0 0 0 0 0 0 |
| 0 0 1 0 0 0 0 0 0 0 |
| 0 0 0 1 0 0 0 0 0 0 |
| 0 0 0 0 1 0 0 0 0 0 |
| 0 0 0 0 0 1 0 0 0 0 |
| 0 0 0 0 0 0 1 0 0 0 |
| 0 0 0 0 0 0 0 1 0 0 |
| 0 0 0 0 0 0 0 0 1 0 |

and the two vectors, u and v, as

uT = |c0 + 1, c1, c2, c3, c4, c5, c6, c7, c8, c9 |

vT = | 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 |

The unitary matrix is factorized with three sets of givens rotations - one to remove the "low rank" part (which I assume is the entries below the second subdiagonal), one to remove the second subdiagonal, and one to remove the first subdiagonal.

The problem is that the majority of these entries eliminated are already zero. At first, I assumed this was just something that would only be the case for the first iteration of the method, but then I saw that the first sequence of givens rotations, the ones used to eliminate the low rank portion of the unitary matrix (of which all entries are null), were to be used to eliminate all but the first three elements of u. However, because the givens rotations act on already null entries, the result, I'd assume, would be an identity matrix, or "trivial Givens rotation", meaning that these rotations would be unable to eliminate any elements in the vector.

I really hate to ask a question as broad as "what did I do wrong?", but I'm at a loss for any solutions. I though I had misinterpreted the unitary matrix and tried directly calculating the it in the way described in the document myself, U = H - uvH (with H being the initial companion matrix), but came up with the same result. I'm sorry if enough details haven't been provided, and am more than willing to go into further detail if needed. Thank you for reading this question.

Update: I'm sorry if me editing this again is getting annoying. I'm just trying my best to make this question as clear as possible.

share|improve this question
    
I think you are on to the fact that to "eliminate" an entry already zero, the trivial Givens rotation (identity) is what is needed. Does anything else need explanation? –  hardmath Mar 31 '12 at 21:11
    
Thank you for your answer. If the 'trivial Givens rotation' is an identity matrix, I don't think it'd be able to eliminate the values in the vector u. What's puzzling to me is that all but three of the first three values of the vector must be equal to zero, and are supposed to be eliminated by the sequence of trivial Givens rotations. –  Dizzy Mar 31 '12 at 21:29
    
With the view count approaching fifty and not a single official answer since this question's creation, I'm lead to believe this question is just as puzzling to the rest of the users of this forum as it is to me. I'm beginning to suspect there may have been an error in the document I'm reading from, and, while I really hate to come to this conclusion, it won't do any good to endlessly read over and over these slides while leaving this question active. If someone decides to propose this as an answer and users generally support this conclusion, I will accept the answer and move on. –  Dizzy Apr 1 '12 at 4:18
    
Does it get any easier to understand what's going on if you try it for something a little smaller than degree 9? –  Gerry Myerson Apr 1 '12 at 6:15
    
Not quite. Down to degree four, the low rank portion of the matrix remains null. Once the degree falls below four, there is no longer a low rank part to eliminate and the problem actually differs from the scenario described in the slides. In this case, all but the first three (and only) elements of the vector u are equal to zero, as desired, but I'm still unsure as to how to apply the algorithm to cases of higher degree. –  Dizzy Apr 1 '12 at 6:43

1 Answer 1

I may have been over thinking this. It may have been possible to simply replace the initial low rank Givens rotations with Givens rotations intended to eliminate the elements of the vector u, as the already null entries will be unchanged. This may have been what hardmath was approaching, but I'm not sure.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.