linear_algebra.lu_decomposition

Lower-upper (LU) decomposition factors a matrix as a product of a lower triangular matrix and an upper triangular matrix. A square matrix has an LU decomposition under the following conditions:

  • If the matrix is invertible, then it has an LU decomposition if and only

if all of its leading principal minors are non-zero (see https://en.wikipedia.org/wiki/Minor_(linear_algebra) for an explanation of leading principal minors of a matrix). - If the matrix is singular (i.e., not invertible) and it has a rank of k (i.e., it has k linearly independent columns), then it has an LU decomposition if its first k leading principal minors are non-zero.

This algorithm will simply attempt to perform LU decomposition on any square matrix and raise an error if no such decomposition exists.

Reference: https://en.wikipedia.org/wiki/LU_decomposition

Functions

lower_upper_decomposition(→ tuple[numpy.ndarray, ...)

Perform LU decomposition on a given matrix and raises an error if the matrix

Module Contents

linear_algebra.lu_decomposition.lower_upper_decomposition(table: numpy.ndarray) → tuple[numpy.ndarray, numpy.ndarray]

Perform LU decomposition on a given matrix and raises an error if the matrix isn’t square or if no such decomposition exists >>> matrix = np.array([[2, -2, 1], [0, 1, 2], [5, 3, 1]]) >>> lower_mat, upper_mat = lower_upper_decomposition(matrix) >>> lower_mat array([[1. , 0. , 0. ],

[0. , 1. , 0. ], [2.5, 8. , 1. ]])

>>> upper_mat
array([[  2. ,  -2. ,   1. ],
       [  0. ,   1. ,   2. ],
       [  0. ,   0. , -17.5]])

>>> matrix = np.array([[4, 3], [6, 3]])
>>> lower_mat, upper_mat = lower_upper_decomposition(matrix)
>>> lower_mat
array([[1. , 0. ],
       [1.5, 1. ]])
>>> upper_mat
array([[ 4. ,  3. ],
       [ 0. , -1.5]])

# Matrix is not square >>> matrix = np.array([[2, -2, 1], [0, 1, 2]]) >>> lower_mat, upper_mat = lower_upper_decomposition(matrix) Traceback (most recent call last):

…

ValueError: ‘table’ has to be of square shaped array but got a 2x3 array: [[ 2 -2 1]

[ 0 1 2]]

# Matrix is invertible, but its first leading principal minor is 0 >>> matrix = np.array([[0, 1], [1, 0]]) >>> lower_mat, upper_mat = lower_upper_decomposition(matrix) Traceback (most recent call last): … ArithmeticError: No LU decomposition exists

# Matrix is singular, but its first leading principal minor is 1 >>> matrix = np.array([[1, 0], [1, 0]]) >>> lower_mat, upper_mat = lower_upper_decomposition(matrix) >>> lower_mat array([[1., 0.],

[1., 1.]])

>>> upper_mat
array([[1., 0.],
       [0., 0.]])

# Matrix is singular, but its first leading principal minor is 0 >>> matrix = np.array([[0, 1], [0, 1]]) >>> lower_mat, upper_mat = lower_upper_decomposition(matrix) Traceback (most recent call last): … ArithmeticError: No LU decomposition exists