Givens-Rotation from the Right Side (used in QZ-Algorithm)

i need to get a Givens-Rotation, which zeros a matrix entry when multiplied from the right side. I did already look at this Topic https://math.stackexchange.com/questions/945736/givens-rotation-from-right-side but i could not really understand the process of getting there.

Some more details: I have to matrices, A and B and i Need to get their Eigenvalues using the QZ-Algorithm. I get B to triagonal form using Givens-Rotations from left. These transformations are applied to A from the left side, too. After B is in triagonal form, i want to get A in triagonal form, too. Therefore i need Givens-Rotations from Right so that it does not destroy the zeros of Matrix B (Or is there another possibility to do this?)

As an equation:

$$\begin{bmatrix}a&b\\c&d\end{bmatrix}\cdot\begin{bmatrix}e&f\\g&h\end{bmatrix}=\begin{bmatrix}ae+bg&af+bh\\ce+dg&cf+dh\end{bmatrix}$$

with

$$ce+dg=0$$

How to find appropriate e,f,g,h ?

Can anybody provide me some hints how to achieve this?

Thank you very much in advance!

EDIT: Im pretty sure it works like this: $$\begin{bmatrix} a&b \end{bmatrix}\cdot\begin{bmatrix} c&-s\\ s&c \end{bmatrix}=\begin{bmatrix} 0&r \end{bmatrix}$$

with

$$r = \sqrt{a^2+b^2}$$ $$c = \frac{b}{r}$$ $$s = \frac{-a}{r}$$

Can anyone approve this?

EDIT2: Consider a simple 3x3-Matrix which i am trying to triangularize using These givens-rotation from the right.

I can Zero out elements (3,1) and (2,1) using the same rotation-Matrix $G$ with different Parameters $c$ and $s$. So i can create a Zero like this

$\begin{bmatrix}*&*&*\\*&*&*\\a&b&*\end{bmatrix}\cdot\begin{bmatrix}c&-s&0\\s&c&0\\0&0&1\end{bmatrix}=\begin{bmatrix}*&*&*\\*&*&*\\0&*&*\end{bmatrix}$ BUT also like that $\begin{bmatrix}*&*&*\\a&b&*\\*&*&*\end{bmatrix}\cdot\begin{bmatrix}c&-s&0\\s&c&0\\0&0&1\end{bmatrix}=\begin{bmatrix}*&*&*\\0&*&*\\*&*&*\end{bmatrix}$ for the same Rotation Matrix $G$. This makes it impossible for me to Zero out the elements iteratively, as the second Rotation will destroy the Zero created in the first one.

It is no Problem to Zero out all elements in the last row except the one in the right bottom edge (as each Zero is created by another Rotation Matrix $G$).

But how can i achieve to Zero out the elements mentioned in my example, when using the same Rotation Matrix $G$ which destroys already created zero-elements?

Please, any help is greatly appreciated!

• For future reference, an edit like your "EDIT2" is probably better posed as a second question. As it is currently, it should be left alone because the question has an accepted answer. – Geoff Oxberry Jul 20 '15 at 7:17
• WOW! Thank you a LOT for your detailed reply! Finally i got the hint needed to Zero out element (2,1) :-) – Roland Jul 20 '15 at 18:28
• Just checked your procedure. It really works! Thank you a lot! – Roland Jul 20 '15 at 18:33

1 Answer

You are correct. With the choice $$\begin{eqnarray*}r&=&\sqrt{a^2+b^2}\\[.6em]c&=&\frac{b}{r}\\[.6em]s&=&\frac{-a}{r}\end{eqnarray*}$$ a Givens rotation from the right yields $$\begin{pmatrix}a&b\end{pmatrix} \begin{pmatrix}c&-s\\s&c\end{pmatrix} = \begin{pmatrix}ac+bs&-as+bc\end{pmatrix} = \begin{pmatrix}0&r\end{pmatrix}\,,$$ because $$ac+bs=a\frac{b}{r}+b\frac{-a}{r}=\frac{ab}{r}-\frac{ab}{r}=0$$ and $$-as+bc=-a\frac{-a}{r}+b\frac{b}{r}=\frac{a^2+b^2}{r}=\frac{r^2}{r}=r\,.$$ Just take care that $r\neq0$.

Concerning EDIT2:

You can only zero out both elements $(3,1)$ and $(2,1)$ in your example with the same Givens rotation matrix if the matrix looks like this: $$\begin{pmatrix}*&*&*\\a&b&*\\a&b&*\end{pmatrix}$$ And in that case, multiplying your Givens rotation matrix from the right yields $$\begin{pmatrix}*&*&*\\a&b&*\\a&b&*\end{pmatrix} \begin{pmatrix}c&-s&0\\s&c&0\\0&0&1\end{pmatrix} = \begin{pmatrix}*&*&*\\0&r&*\\0&r&*\end{pmatrix}\,,$$ and you have brought both elements to zero simultaneously. If the rows 2 and 3 are not both $\begin{pmatrix}a&b&*\end{pmatrix}$, you need different rotations, i.e., different $c$, $s$, and $r$ values.

What you do in practice to bring a matrix on upper triangle shape, is to start with the lowest row and bring all elements but the last to zero: $$\begin{pmatrix}*&*&*\\*&*&*\\a_1&b_1&*\end{pmatrix} \begin{pmatrix}c_1&-s_1&0\\s_1&c_1&0\\0&0&1\end{pmatrix} = \begin{pmatrix}*&*&*\\*&*&*\\0&r_1&*\end{pmatrix} = \begin{pmatrix}*&*&*\\*&*&*\\0&a_2&b_2\end{pmatrix}$$ and $$\begin{pmatrix}*&*&*\\*&*&*\\0&a_2&b_2\end{pmatrix} \begin{pmatrix}1&0&0\\0&c_2&-s_2\\0&s_2&c_2\end{pmatrix} = \begin{pmatrix}*&*&*\\*&*&*\\0&0&r_2\end{pmatrix}\,.$$

Now, we shall see that a row vector $\begin{pmatrix}0&0&*\end{pmatrix}$ is invariant under Givens rotations from the right which targets the first column: $$\begin{pmatrix}0&0&*\end{pmatrix} \begin{pmatrix}c&-s&0\\s&c&0\\0&0&1\end{pmatrix} = \begin{pmatrix}0 \cdot (c+s)&0 \cdot (c-s)&1 \cdot *\end{pmatrix}\,.$$

This allows us to bring the element $(2,1)$ to zero without changing the last row: $$\begin{pmatrix}*&*&*\\a_3&b_3&*\\0&0&r_2\end{pmatrix} \begin{pmatrix}c_3&-s_3&0\\s_3&c_3&0\\0&0&1\end{pmatrix} = \begin{pmatrix}*&*&*\\0&r_3&*\\0&0&r_2\end{pmatrix}\,,$$ and we have reached the upper triangle shape by applying three (different) Givens rotations from the right.

• Please, be so Kind and have a look at my second Edit. Thank you very much in advance. – Roland Jul 19 '15 at 0:19