TheAlgorithms/Python · error · ArithmeticError

No LU decomposition exists

Error message

No LU decomposition exists

What it means

Raised by lower_upper_decomposition() in linear_algebra/lu_decomposition.py:102 when a diagonal element upper[j][j] is exactly 0 during factorization, making the division (table[i][j] - total) / upper[j][j] impossible. This is the mathematical condition that no (unpivoted, Doolittle) LU decomposition exists: a leading principal minor of the matrix is zero. Note the matrix may still be invertible — it just needs row permutations (PA = LU), which this implementation does not perform.

Source

Thrown at linear_algebra/lu_decomposition.py:102

    rows, columns = np.shape(table)
    if rows != columns:
        msg = (
            "'table' has to be of square shaped array but got a "
            f"{rows}x{columns} array:\n{table}"
        )
        raise ValueError(msg)

    lower = np.zeros((rows, columns))
    upper = np.zeros((rows, columns))

    # in 'total', the necessary data is extracted through slices
    # and the sum of the products is obtained.

    for i in range(columns):
        for j in range(i):
            total = np.sum(lower[i, :i] * upper[:i, j])
            if upper[j][j] == 0:
                raise ArithmeticError("No LU decomposition exists")
            lower[i][j] = (table[i][j] - total) / upper[j][j]
        lower[i][i] = 1
        for j in range(i, columns):
            total = np.sum(lower[i, :i] * upper[:i, j])
            upper[i][j] = table[i][j] - total
    return lower, upper


if __name__ == "__main__":
    import doctest

    doctest.testmod()

View on GitHub (pinned to f5988cc097)

Solutions

1. Use scipy.linalg.lu(matrix) instead — it performs partial pivoting and succeeds whenever the matrix is invertible.
2. Pre-check the leading principal minors: if any det(matrix[:k, :k]) == 0, reorder rows first, then call lower_upper_decomposition.
3. Catch ArithmeticError at the call site and fall back to a pivoting solver or report that no LU decomposition exists for this ordering.
4. If solving a system, switch to np.linalg.solve or gaussian elimination with pivoting instead of hand-rolling LU.

Example fix

// before
matrix = np.array([[0, 1], [1, 0]])
lower, upper = lower_upper_decomposition(matrix)  # ArithmeticError

// after
from scipy.linalg import lu
p, lower, upper = lu(matrix)  # pivoting handles zero leading minors

import numpy as np

# Leading principal minors must all be non-zero for unpivoted LU
leading_minors_ok = all(np.linalg.det(matrix[:k, :k]) != 0 for k in range(1, matrix.shape[0] + 1))
if not leading_minors_ok:
    matrix = matrix[np.argsort(np.abs(matrix[:, 0]))[::-1]]  # pivot: bring largest first-row entry up

try:
    lower, upper = lower_upper_decomposition(matrix)
except ArithmeticError:
    # no unpivoted LU for this row ordering; fall back to pivoting
    from scipy.linalg import lu
    p, lower, upper = lu(matrix)

When it happens

Trigger: Calling lower_upper_decomposition() on a matrix whose leading principal minors vanish, e.g. np.array([[0, 1], [1, 0]]) (first pivot is 0) or np.array([[1, 2], [2, 4]]) (singular, second pivot collapses to 0). The check `if upper[j][j] == 0` fires inside the inner loop over j < i before computing lower[i][j].

Common situations: Passing permutation-like or permuted matrices whose (0,0) entry is 0, singular matrices from underdetermined real-world data, or matrices that do have an LU factorization but only with pivoting — a very common surprise for users coming from scipy.linalg.lu which always pivots.

Related errors

• 'table' has to be of square shaped array but got a {rows}x{c
• Matrix is not invertible
• Input matrix A is not invertible. Cannot compute Schur compl
• Coefficient matrix dimensions must be nxn but received {rows
• Constant matrix must be nx1 but received {rows2}x{cols2}

AI-assisted analysis of TheAlgorithms/Python@f5988cc097 (2026-08-14). Data as JSON: /api/errors/c803ae9c45523201. Report an issue: GitHub.