Topics: The Givens Rotation
Assumes: Basic Familiarity with Matrices
Last edit: November 5th, 2023 - John Halleck, Minor .
Prior edit:August 9th, 2023 - John Halleck, Reinserted more of the original source.
James Wallace Givens, Jr. (1910-1993), writing as Wallace Givens, introduced the Givens rotation in "Computation of Plane Unitary Rotations Transforming a General Matrix to Triangular Form", Journal of the Society for Industrial and Applied Mathematics Vol. 6, No. 1 (Mar., 1958), pp. 26-50.
Terminology aside: By the usual mathematical conventon, if someone named "Bullwinkle" invented
a rotation, it would be called "The Bullwinkle Rotation".
For the same reason, Givens' rotation is called "The Givens Rotation".
Unfortunately, his name ends in an "s" sound, leading to an amazing number of arguments on the Internet
that falsely claim it should be the "The Given's rotation" (which would be a rotation attributed to someone
named "Given", and not one named "Givens")
THIS POST IS MISSING THE ENTIRE FIRST PART THAT USED TO BE HERE... I'm working on reconstructing the post, sorry for the inconvenience. [Thursday, the 30th of June, 2023]
*** TODO: This section needs a lot more work. ***
Much of mathematics can be thought of in many different ways. The Givens rotation is a prime example of this. I'll start with a diagram of what we we are rotating.
NOTE: This right triangle is arranged so that X increases to the right, and Y increases towards the top, which is the standard convention for coordinates nowadays. In ancient Greece (not having invented coordinate systems) they drew it often with the point to the right, as many do today. TODO: Explain why pointing it to the right leads to a common set of errors.
Graphicly, we are going to rotate the hypotenuse down to the X axis. I.E. we are going to rotate the long side to the bottom. TODO: Fix this.
... still haven't replacing the text that used to be here.
... **** TODO: Working on filling this in ...
Applying $(\sin{\theta})^2 + (\cos{\theta})^2 = 1$, and preforming the subtractions to get zeros
[ Text is missing here ]
= $\begin{bmatrix}
1 & 0 \\
0 & 1
\end{bmatrix}$
which is a 2x2 identity matrix... proving that the Givens Rotation is orthogonal.
But, of course, we can do the same demonstration for trigonophobes with just the definitions of sine and cosine given above.
$G= \begin{bmatrix} \quad \cos{\theta} & \sin{\theta} \\ - \sin{\theta} & \cos{\theta} \end{bmatrix} = \begin{bmatrix} \dfrac{ x}{\sqrt{x^2+y^2}} & \dfrac{y}{\sqrt{x^2+y^2}} \\ \dfrac{-y}{\sqrt{x^2+y^2}} & \dfrac{x}{\sqrt{x^2+y^2}} \end{bmatrix} $
$sin{\theta}$ and $\cos{\theta}$ always return a result in the rangle -1 to 1 inclusive.
And since $\sqrt{x^2+y^2}$ is larger than either $x$ or $y$, the fractions must each also have a magnitude between -1 and 1 (inclusive).
Since the trig functions given and the fraction forms are equal,
$GG^T
=\begin{bmatrix}
\dfrac{ x}{\sqrt{x^2+y^2}} & \dfrac{y}{\sqrt{x^2+y^2}} \\
\dfrac{-y}{\sqrt{x^2+y^2}} & \dfrac{x}{\sqrt{x^2+y^2}}
\end{bmatrix}
\begin{bmatrix}
\dfrac{ x}{\sqrt{x^2+y^2}} & \dfrac{y}{\sqrt{x^2+y^2}} \\
\dfrac{-y}{\sqrt{x^2+y^2}} & \dfrac{x}{\sqrt{x^2+y^2}}
\end{bmatrix}^T
$
$=\begin{bmatrix}
\dfrac{ x}{\sqrt{x^2+y^2}} & \dfrac{y}{\sqrt{x^2+y^2}} \\
\dfrac{-y}{\sqrt{x^2+y^2}} & \dfrac{x}{\sqrt{x^2+y^2}}
\end{bmatrix}
\begin{bmatrix}
\dfrac{x}{\sqrt{x^2+y^2}} & \dfrac{-y}{\sqrt{x^2+y^2}} \\
\dfrac{y}{\sqrt{x^2+y^2}} & \dfrac{ x}{\sqrt{x^2+y^2}}
\end{bmatrix}
$
$=
\begin{bmatrix}
\dfrac{x^2+y^2}{x^2+y^2} & \dfrac{ -xy+yx}{x^2+y^2} \\
\dfrac{yx-xy }{x^2+y^2} & \dfrac{x^2+y^2}{x^2+y^2}
\end{bmatrix}
=\begin{bmatrix}
1 & 0 \\
0 & 1
\end{bmatrix}
$ which is, once again, an identity matrix.
Orthogonal matrices are famous for their numerical stability. And they are particularly good for selectively zeroing elements of a matrix in a manner that doesn't change the least squares solution.
The full Givens rotation matrix has the same width and height as the height of the matrix that you are applying it to. But since it only affects two rows it is usually written as if the two rows were extracted, a 2x2 matrix applied, and the rows put back. Of course, in practice, we don't actually move them around because the code to apply the rotation just has a slightly different indexing into data.
Givens Rotations are used to selectively zero out items in a problem matrix in order to (for example) to put a matrix into upper triangular form in a numerically stable manner, so that it is easy to solve.
Trivial example:
If we had a column vector $ \begin{bmatrix} x \\ y \end{bmatrix}$ and you wanted to zero out $y$, you could set it up as:
$\begin{bmatrix}
\quad c & s \\
-s & c
\end{bmatrix}
\begin{bmatrix} x \\ y \end{bmatrix}
$
The hypotenuse is computed as $h=\sqrt{x^2+y^2}$
$\cos\theta$ = Adjacent over hypotenuse
$c = \dfrac{x}{h}$
$\sin\theta$ = Opposite over hypotenuse
$s = \dfrac{y}{h}$
Final rotation:
$\begin{bmatrix}
\dfrac{ x}{\sqrt{x^2+y^2}} & \dfrac{y}{\sqrt{x^2+y^2}} \\
\dfrac{-y}{\sqrt{x^2+y^2}} & \dfrac{x}{\sqrt{x^2+y^2}}
\end{bmatrix}
\begin{bmatrix} x \\ y \end{bmatrix}
= \begin{bmatrix} \dfrac{x^2+y^2}{\sqrt{x^2+y^2}} \\ \dfrac{-yx+xy}{\sqrt{x^2+y^2}} \end{bmatrix}
= \begin{bmatrix} \sqrt{x^2+y^2} \\ 0 \end{bmatrix}$
Note that this is what we expected to have in the discussion of the triangle above.
For those that like to have a numeric, rather than symbolic, example:
For the column $\begin{bmatrix} 4 \\ 3 \end{bmatrix}$ we have a hypotenuse of $\sqrt{4^2+3^2} = \sqrt{16+9} = \sqrt{25} = 5$.
$c = \dfrac{4}{5}$ (Adjacent over hypotenuse)
$s = \dfrac{3}{5}$ (Opposite over hypotenuse)
Final rotation:
$\begin{bmatrix}
\quad \dfrac{3}{5} & \dfrac{4}{5} \\
-\dfrac{3}{5} & \dfrac{4}{5}
\end{bmatrix}
\begin{bmatrix} 4 \\ 3 \end{bmatrix}
=
\begin{bmatrix} \dfrac{16+9}{5} \\ \dfrac{-12+12}{5} \end{bmatrix}
=\begin{bmatrix} \dfrac{25}{5} \\ \dfrac{0}{5} \end{bmatrix}
=\begin{bmatrix} 5 \\ 0 \end{bmatrix}
$
Footnotes:
1) While the Pythagorean Theorem is traditionally credited to Pythagoras, archeologists have a Mesopotamian tablet (Plimpton 322) that was written more than a thousand years before Pythagoras [Pythagoras lived from 570 BCE to 495 BCE], that was a list of whole number pythagorean triples.
2 The book ERIC ED037335: The Pythagorean Proposition, Classics in Mathematics Education Series." by National Council of Teachers of Mathematics - NCTM) has "... 370 different proofs, whose origins range from 900 B.C. to 1940 A.D.". It also has the most complete and interesting biography of Pythagoras I (-JH) have ever seen. Lots of things I didn't know, and found interesting. The full book is availiable for free, in a number of formats, at https://archive.org/details/ERIC_ED037335/
Navigation: