Givens Rotation

Givens Rotation

Mathematical Definition

A Givens rotation matrix G(i, j, θ) is an orthogonal matrix that performs a rotation by an angle θ in the (i, j)-plane. For a 2D vector, it is simply the standard 2×2 rotation matrix:

To zero out the y-component (i.e., v'_y = 0), we choose θ such that:

In higher dimensions, G(i, j, θ) is the identity matrix modified so that elements at intersections of the i-th and j-th rows and columns match the 2D rotation matrix.

Key Concepts

Orthogonality and Norm Preservation

Because Givens rotation matrices are orthogonal (G^TG = I), multiplying a vector by a Givens matrix does not change the vector's Euclidean norm (L2 norm). Geometrically, this means the vector is only rotated, never stretched or shrunk.

Selective Annihilation

Unlike Householder reflections, which zero out all elements below the diagonal in a column simultaneously, a Givens rotation zeroes out exactly one element at a time. This makes Givens rotations highly effective for operating on sparse or banded matrices where introducing non-zero elements (fill-in) must be minimized.

Numerical Stability

Computing the cos(θ) and sin(θ) values explicitly using inverse trigonometric functions (like arctan) can be numerically unstable if x is very small. In practice, stable implementations calculate these values directly using the hypotenuse r = √(x² + y²): c = x/r and s = -y/r, handling edge cases carefully to avoid overflow or division by zero.

Historical Context

The Givens rotation is named after Wallace Givens, an American mathematician and pioneer in computer science. Givens introduced these orthogonal transformations in the 1950s as a method to compute the eigenvalues of symmetric matrices.

His work provided a numerically stable alternative to methods that were prone to accumulating rounding errors. Along with Householder reflections, Givens rotations became a fundamental algorithm in the development of modern numerical linear algebra routines used in software libraries like LAPACK.

Real-world Applications

• QR Decomposition: Givens rotations are often used to compute the QR decomposition of a matrix, especially when the matrix is sparse or banded, by systematically zeroing out elements below the main diagonal.
• SVD and Eigenvalue Computations: Iterative algorithms like the Jacobi method use sequences of Givens rotations to diagonalize symmetric matrices and compute their eigenvalues and eigenvectors.
• Signal Processing: In applications like adaptive filtering and beamforming, algorithms must update matrix decompositions continuously as new data arrives. Givens rotations allow for efficient O(n²) rank-1 updates to QR decompositions.
• Robotics and Kinematics: Finding inverse kinematics for robotic arms often relies on stable matrix inversions and orthogonal transformations where preserving numerical stability is vital.

Related Concepts

• Linear Transformations — the general category of vector space mappings to which Givens rotations belong
• QR Decomposition — a factorization algorithm frequently implemented using Givens rotations
• Orthogonal Projections — another form of transformation often contrasted with rotations