2
$\begingroup$

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.

  • 0
    It's been a while since I played with this method. I'll need to think about this...2012-05-01

1 Answers 1

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.