{"record":{"id":"c803ae9c45523201","repo":"TheAlgorithms/Python","slug":"no-lu-decomposition-exists","errorCode":null,"errorMessage":"No LU decomposition exists","messagePattern":"No LU decomposition exists","errorType":"exception","errorClass":"ArithmeticError","httpStatus":null,"severity":"error","filePath":"linear_algebra/lu_decomposition.py","lineNumber":102,"sourceCode":"    rows, columns = np.shape(table)\n    if rows != columns:\n        msg = (\n            \"'table' has to be of square shaped array but got a \"\n            f\"{rows}x{columns} array:\\n{table}\"\n        )\n        raise ValueError(msg)\n\n    lower = np.zeros((rows, columns))\n    upper = np.zeros((rows, columns))\n\n    # in 'total', the necessary data is extracted through slices\n    # and the sum of the products is obtained.\n\n    for i in range(columns):\n        for j in range(i):\n            total = np.sum(lower[i, :i] * upper[:i, j])\n            if upper[j][j] == 0:\n                raise ArithmeticError(\"No LU decomposition exists\")\n            lower[i][j] = (table[i][j] - total) / upper[j][j]\n        lower[i][i] = 1\n        for j in range(i, columns):\n            total = np.sum(lower[i, :i] * upper[:i, j])\n            upper[i][j] = table[i][j] - total\n    return lower, upper\n\n\nif __name__ == \"__main__\":\n    import doctest\n\n    doctest.testmod()\n","sourceCodeStart":84,"sourceCodeEnd":115,"githubUrl":"https://github.com/TheAlgorithms/Python/blob/f5988cc09713315817df6a7e327e258013a94440/linear_algebra/lu_decomposition.py#L84-L115","documentation":"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.","triggerScenarios":"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].","commonSituations":"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.","solutions":["Use scipy.linalg.lu(matrix) instead — it performs partial pivoting and succeeds whenever the matrix is invertible.","Pre-check the leading principal minors: if any det(matrix[:k, :k]) == 0, reorder rows first, then call lower_upper_decomposition.","Catch ArithmeticError at the call site and fall back to a pivoting solver or report that no LU decomposition exists for this ordering.","If solving a system, switch to np.linalg.solve or gaussian elimination with pivoting instead of hand-rolling LU."],"exampleFix":"// before\nmatrix = np.array([[0, 1], [1, 0]])\nlower, upper = lower_upper_decomposition(matrix)  # ArithmeticError\n\n// after\nfrom scipy.linalg import lu\np, lower, upper = lu(matrix)  # pivoting handles zero leading minors","handlingStrategy":"try-catch","validationCode":"import numpy as np\n\n# Leading principal minors must all be non-zero for unpivoted LU\nleading_minors_ok = all(np.linalg.det(matrix[:k, :k]) != 0 for k in range(1, matrix.shape[0] + 1))\nif not leading_minors_ok:\n    matrix = matrix[np.argsort(np.abs(matrix[:, 0]))[::-1]]  # pivot: bring largest first-row entry up","typeGuard":null,"tryCatchPattern":"try:\n    lower, upper = lower_upper_decomposition(matrix)\nexcept ArithmeticError:\n    # no unpivoted LU for this row ordering; fall back to pivoting\n    from scipy.linalg import lu\n    p, lower, upper = lu(matrix)","preventionTips":["If inputs may have zero leading minors, default to scipy.linalg.lu, which pivots and raises only for structurally impossible cases.","Pre-screen with leading principal minors: any det(A[:k, :k]) == 0 guarantees this failure.","Do not treat this error as 'singular matrix' — e.g. [[0,1],[1,0]] is invertible but still fails; reorder rows first.","Catch ArithmeticError specifically (distinct from the ValueError raised for non-square input) so both causes are handled precisely."],"tags":["linear-algebra","lu-decomposition","zero-pivot","singular-matrix","numpy"],"backgroundTag":null,"analyzedSha":"f5988cc09713315817df6a7e327e258013a94440","analyzedAt":"2026-08-14T17:30:07.041Z","schemaVersion":2},"datasetVersion":"2026-08-15T17:31:12.345Z"}