galois.FieldArray.lu_decompose() → tuple[Self, Self]

Decomposes the input array into the product of lower and upper triangular matrices.

Returns:

  • The lower triangular matrix.

  • The upper triangular matrix.

Notes

The LU decomposition of \(\mathbf{A}\) is defined as \(\mathbf{A} = \mathbf{L} \mathbf{U}\).

Examples

In [1]: GF = galois.GF(31)

# Not every square matrix has an LU decomposition
In [2]: A = GF([[22, 11, 25, 11], [30, 27, 10, 3], [21, 16, 29, 7]]); A
Out[2]: 
GF([[22, 11, 25, 11],
    [30, 27, 10,  3],
    [21, 16, 29,  7]], order=31)

In [3]: L, U = A.lu_decompose()

In [4]: L
Out[4]: 
GF([[ 1,  0,  0],
    [ 7,  1,  0],
    [ 8, 25,  1]], order=31)

In [5]: U
Out[5]: 
GF([[22, 11, 25, 11],
    [ 0, 12, 21, 19],
    [ 0,  0, 17,  2]], order=31)

In [6]: np.array_equal(A, L @ U)
Out[6]: True