Introduction

When you need to compute the QR decomposition of a matrix, the textbook approach applies Householder reflections — transformations that zero an entire column below the diagonal in one shot. That works beautifully on dense matrices. But what if the matrix is sparse, with most entries already zero? A Householder reflection can accidentally destroy that sparsity.

Givens rotations offer a surgical alternative. Each rotation targets exactly one entry, sets it to zero, and leaves every other entry it was not meant to touch unchanged. The price is that you need more steps; the payoff is total control over what zeros get created and what structure is preserved.

The idea is older than computers. The mathematician Wallace Givens systematized it in 1954 for use on early digital machines, where rotating in a single plane was cheaper than forming a full reflection. Today the same trick is indispensable in streaming signal processing, adaptive filters, and the sparse solvers at the heart of GPS, structural engineering simulations, and large-scale optimization.

Try It

The demo below shows a 3×33 \times 3 matrix. Click any off-diagonal entry to make it your target. Then press Apply rotation to watch a Givens rotation zero it exactly, while displaying the angle θ\theta and the updated matrix.

<!-- Givens rotation demo: click an off-diagonal entry to target it, then apply the rotation -->
<p class="hint">Click any <b>off-diagonal</b> entry (gray cell) to select it as the target. Press <b>Apply rotation</b> to zero it with a Givens plane rotation. The angle θ and the updated matrix appear on the right.</p>
<div class="matrix-wrap">
  <div id="matrix" class="matrix"></div>
  <div class="arrow">&#8594;</div>
  <div id="result" class="matrix result-mat"></div>
</div>
<div class="status" id="status">Click an off-diagonal entry to begin.</div>
<div class="btns">
  <button id="apply" type="button" disabled>Apply rotation</button>
  <button id="reset" type="button" class="ghost">Reset</button>
</div>

/* Layout and visual styles for the Givens rotation demo */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .8rem; line-height: 1.45; }
.matrix-wrap { display: flex; align-items: center; gap: .6rem; flex-wrap: wrap; margin: .5rem 0 .7rem; }
.matrix { display: grid; grid-template-columns: repeat(3, 56px); gap: 4px; }
.cell { width: 56px; height: 48px; display: flex; align-items: center; justify-content: center;
        font: 600 15px ui-monospace, monospace; border-radius: 7px; user-select: none; }
.fixed { background: #e8eef3; color: #1d3557; border: 1px solid #cdd9e3; }
.target-cell { background: #c9ccd1; border: 1px solid #adb1b8; cursor: pointer; transition: background .1s; }
.target-cell:hover { background: #b8bdc4; }
.target-cell.selected { background: #1d3557; color: #fff; border-color: #14274a; }
.target-cell.zeroed { background: #c9ccd1; color: #888; cursor: default; }
.result-mat .cell { background: #eaf7ef; color: #0a5c30; border: 1px solid #b4dfc7; }
.result-mat .cell.changed { background: #0a7d33; color: #fff; border-color: #065c26; }
.result-mat .cell.zero-achieved { background: #264de4; color: #fff; border-color: #1a35a8; }
.arrow { font-size: 1.8rem; color: #888; line-height: 1; }
.status { font-size: 1rem; font-weight: 600; margin: .4rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.info { color: #1d3557; }
.status.bad { color: #c92f3c; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button:disabled { opacity: .4; cursor: default; }
button.ghost { background: #fff; color: #1d3557; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// A Givens rotation G(i,j,theta) is a 2x2 orthogonal transformation applied to rows i and j
// it chooses c=cos(theta), s=sin(theta) so that the (i,j) entry becomes exactly 0

// 3x3 demo matrix — arbitrary values with interesting off-diagonal entries
let A = [
  [4, -2,  1],
  [3,  5, -1],
  [-1, 2,  6]
];
let target = null; // [row, col] of the cell the user wants to zero; null when none selected

// matrix dimension
const N = 3;

// Compute Givens parameters c,s,r given the two pivot values a (diagonal) and b (target)
function givensParams(a_ij, a_jj) {
  const rr = Math.sqrt(a_ij * a_ij + a_jj * a_jj);
  if (rr < 1e-14) return { c: 1, s: 0 };
  return { c: a_jj / rr, s: -a_ij / rr };
}

// Apply the Givens rotation to rows i and j across all columns
function applyGivens(mat, i, j, c, s) {
  const res = mat.map(row => row.slice());
  for (let col = 0; col < N; col++) {
    const xi = mat[i][col];
    const xj = mat[j][col];
    res[i][col] = c * xi + s * xj;
    res[j][col] = -s * xi + c * xj;
  }
  return res;
}

function fmt(v) { return v.toFixed(2); }

function renderMatrix(id, data, changedRows, zeroCell) {
  const el = document.getElementById(id);
  el.innerHTML = '';
  for (let r = 0; r < N; r++) {
    for (let cc = 0; cc < N; cc++) {
      const d = document.createElement('div');
      const isChanged = changedRows && changedRows.includes(r);
      const isZero = zeroCell && zeroCell[0] === r && zeroCell[1] === cc && Math.abs(data[r][cc]) < 1e-10;
      d.className = 'cell ' + (id === 'matrix' ? cellClass(r, cc) : 'fixed') +
        (isZero ? ' zero-achieved' : (isChanged ? ' changed' : ''));
      if (id === 'matrix') {
        if (!isFixed(r, cc)) {
          d.dataset.r = r; d.dataset.c = cc;
          d.addEventListener('click', onCellClick);
        }
      }
      d.textContent = fmt(data[r][cc]);
      el.appendChild(d);
    }
  }
}

// Diagonal entries are fixed (not clickable) — they are the pivots
function isFixed(r, c) { return r === c; }
function cellClass(r, c) {
  if (isFixed(r, c)) return 'fixed';
  if (target && target[0] === r && target[1] === c) return 'target-cell selected';
  return 'target-cell';
}

function onCellClick(e) {
  const r = +e.currentTarget.dataset.r;
  const c = +e.currentTarget.dataset.c;
  target = [r, c];
  renderMatrix('matrix', A, null, null);
  document.getElementById('apply').disabled = false;
  setStatus('Entry selected — press Apply rotation.', 'info');
}

function setStatus(t, cls) {
  const s = document.getElementById('status');
  s.textContent = t; s.className = 'status ' + cls;
}

function applyRotation() {
  if (!target) return;
  const [tr, tc] = target;
  // To zero A[tr][tc] we rotate rows tr and tc using A[tc][tc] as the pivot.
  // This drives the (tr,tc) entry to zero while preserving orthogonality.
  const i = tr; // row to be zeroed (off-diagonal row)
  const j = tc; // pivot row (diagonal)
  const { c, s } = givensParams(A[i][j], A[j][j]);
  const thetaDeg = (Math.atan2(-s, c) * 180 / Math.PI).toFixed(2);
  const B = applyGivens(A, i, j, c, s);
  renderMatrix('result', B, [i, j], [i, j]);
  const msg = i18nFmt('Zeroed row %r%, col %col% with θ = %theta%°.', { r: tr + 1, col: tc + 1, theta: thetaDeg });
  setStatus(msg, 'ok');
  A = B;
  target = null;
  document.getElementById('apply').disabled = true;
  renderMatrix('matrix', A, null, null);
}

function resetDemo() {
  A = [
    [4, -2,  1],
    [3,  5, -1],
    [-1, 2,  6]
  ];
  target = null;
  document.getElementById('result').innerHTML = '';
  document.getElementById('apply').disabled = true;
  renderMatrix('matrix', A, null, null);
  setStatus('Click an off-diagonal entry to begin.', '');
}

document.getElementById('apply').addEventListener('click', applyRotation);
document.getElementById('reset').addEventListener('click', resetDemo);
renderMatrix('matrix', A, null, null);
Result
Console

Notice what does not change: entries that share neither the row nor the column of the rotation are completely untouched. That is the defining property — a Givens rotation acts on exactly two rows at a time. String enough of them together and you drive an entire matrix to upper-triangular form, one zero at a time.

The Real Complexity

How does the cost compare with rival methods?

  • One rotation: applying a Givens rotation to an n×nn \times n matrix touches only two rows, so the work is O(n)O(n) — just a pass over those rows updating each element with c⋅x±s⋅yc \cdot x \pm s \cdot y.
  • Full QR via Givens: zeroing all n(n−1)2\frac{n(n-1)}{2} sub-diagonal entries needs that many rotations, giving O(n3)O(n^3) total — the same asymptotic cost as Householder QR.
  • But sparse matrices change everything. If an entry is already zero, you can skip its rotation entirely. In a matrix with kk non-zeros below the diagonal, only kk rotations are needed, costing O(kn)O(kn). When k≪n2k \ll n^2, this is a dramatic win.
  • Streaming and rank-one updates: when a new row arrives, a single sweep of nn rotations incorporates it into the existing QR factorization — no full restart. This is the foundation of recursive least squares and adaptive filters.
  • Numerical stability: Givens rotations are orthogonal transformations, so they never amplify rounding errors. The condition number of the problem is preserved exactly, unlike normal-equation approaches that square it.

The tradeoff is pedagogical simplicity vs. bulk efficiency. For dense matrices Householder wins by constant factors; for sparse or streaming data Givens is the natural choice and often the only practical one.

Where It Matters

"Zero one entry at a time with full control" turns out to be exactly what many real systems need:

  • Sparse linear systems: structural finite-element models and power-flow networks have millions of variables but each equation touches only a handful. Sparse QR via Givens exploits that exactly, only performing rotations for non-zero entries.
  • Adaptive signal processing: recursive least squares updates a QR factorization with each new sample. One sweep of Givens rotations appends the new row, keeping filters responsive in real time — used in echo cancellation, noise reduction, and radar tracking.
  • GPS and navigation: Kalman filters for position estimation use QR-based square-root forms for numerical safety. Givens rotations are the standard update step.
  • Computer graphics and robotics: orthogonalizing a rotation matrix that has drifted from orthogonality due to floating-point accumulation is a classic Givens application.
  • Rank-revealing QR: by choosing the order of Givens rotations strategically you expose the numerical rank of a matrix — a fundamental operation in dimensionality reduction and compressed sensing.

See also how QR decomposition uses these building blocks at a higher level, and how dimensionality reduction exploits the resulting factorizations.

Conclusion

Givens rotations are proof that sometimes the most powerful tool is the most precise one. Where Householder reflections swing a sledgehammer, a Givens rotation makes a single, targeted cut — zero exactly one entry, touch exactly two rows, leave everything else alone.

That precision is not just elegant; it is efficient. In the sparse and streaming worlds that dominate modern computation, the ability to skip rotations for entries that are already zero, or to update a factorization with a single new sample, turns an O(n3)O(n^3) algorithm into something far leaner in practice. Wallace Givens gave us the idea in 1954; it is more relevant today than ever.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/givens-rotations/Content licensed under CC BY-NC 4.0.