Singular Value Decomposition (SVD) of 2x2 Matrix

#12 · Linear Algebra · Hard

Problem

Perform Singular Value Decomposition (SVD) on a 2x2 matrix, decomposing it into U Sigma V^T. Return the singular values and the matrices U and V.

Solution

import numpy as np

def svd_2x2(A: list[list[float]]) -> tuple:
    A = np.array(A, dtype=float)
    # Compute A^T * A and A * A^T
    ATA = A.T @ A
    AAT = A @ A.T

    # Eigenvalues/vectors of A^T * A give V and sigma^2
    eigvals_v, V = np.linalg.eigh(ATA)
    # Sort by descending eigenvalue
    idx = np.argsort(eigvals_v)[::-1]
    eigvals_v = eigvals_v[idx]
    V = V[:, idx]

    # Singular values
    sigma = np.sqrt(np.maximum(eigvals_v, 0))

    # Compute U from A * V / sigma
    U = np.zeros_like(A, dtype=float)
    for i in range(len(sigma)):
        if sigma[i] > 1e-10:
            U[:, i] = (A @ V[:, i]) / sigma[i]

    # Ensure proper orthogonal matrices (det = 1)
    if np.linalg.det(U) < 0:
        U[:, -1] *= -1
    if np.linalg.det(V) < 0:
        V[:, -1] *= -1

    return U.tolist(), sigma.tolist(), V.T.tolist()

Explanation

Compute A^T * A. Its eigenvectors form V and its eigenvalues are the squared singular values.
The singular values are the square roots of those eigenvalues, sorted in descending order.
U is computed via U_i = A * V_i / sigma_i for each singular value.
Adjust signs to ensure proper rotation matrices (positive determinant).

Complexity

Time: O(1) since the matrix is always 2x2 (eigenvalue computation is constant)
Space: O(1)

← #11 #13 →