LU Decomposition

Factor a square matrix as A = L @ U with the Doolittle algorithm.

L is lower triangular with ones on its diagonal, and U is upper triangular. Gaussian elimination already computes both: U is the matrix that elimination leaves behind, and L holds the multipliers it used. Once you have them, solving A x = b for many right-hand sides is cheap: one forward substitution with L and one back substitution with U, each O(n^2).

For each pivot column k and each row i > k:

L[i, k] = U[i, k] / U[k, k]
U[i, :] = U[i, :] - L[i, k] * U[k, :]

Start from U = copy of A and L = identity.

Function signature

def lu_decompose(A):

Example

Input

lu_decompose(np.array([[4.0, 3.0], [6.0, 3.0]]))

Output

L = array([[1. , 0. ],
           [1.5, 1. ]])
U = array([[ 4. ,  3. ],
           [ 0. , -1.5]])

Reasoning

To clear the 6 below the pivot 4, subtract 1.5 times row 0 from row 1. That leaves [0, 3 - 4.5] = [0, -1.5] in U, and records the multiplier 1.5 in L. Multiplying back, L @ U gives A.

Constraints and notes

• No pivoting. You can assume no zero pivot appears.
• Return (L, U). Do not modify A.
• Do not use scipy.linalg.lu.