QR Decomposition

Problem

Implement QR Decomposition using the Gram-Schmidt process. Given a matrix A, decompose it into an orthogonal matrix Q and an upper triangular matrix R such that A = QR.

Solution

import numpy as np

def qr_decomposition(A: list[list[float]]) -> tuple:
    A = np.array(A, dtype=float)
    m, n = A.shape
    Q = np.zeros((m, n))
    R = np.zeros((n, n))

    for j in range(n):
        v = A[:, j].copy()
        for i in range(j):
            R[i, j] = np.dot(Q[:, i], A[:, j])
            v = v - R[i, j] * Q[:, i]
        R[j, j] = np.linalg.norm(v)
        if R[j, j] < 1e-10:
            Q[:, j] = 0
        else:
            Q[:, j] = v / R[j, j]

    return Q, R

Explanation

1. Modified Gram-Schmidt: Process each column of A one at a time.
2. For column j, start with v = A[:, j].
3. Project out the components along all previously computed orthonormal vectors Q[:, 0], ..., Q[:, j-1]. The projection coefficients become the entries of R.
4. The remaining vector v is orthogonal to all previous columns. Normalize it to get Q[:, j], and store its norm in R[j, j].
5. The result satisfies A = Q @ R where Q has orthonormal columns and R is upper triangular.

Complexity

• Time: O(m * n^2) for an m x n matrix
• Space: O(m * n + n^2) for Q and R