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

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

Returns

  • P – The column permutation matrix.

  • L – The lower triangular matrix.

  • U – The upper triangular matrix.

Notes

The PLU decomposition of \(\mathbf{A}\) is defined as \(\mathbf{A} = \mathbf{P} \mathbf{L} \mathbf{U}\). This is equivalent to \(\mathbf{P}^T \mathbf{A} = \mathbf{L} \mathbf{U}\).

Examples

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

In [2]: A = GF([[0, 29, 2, 9], [20, 24, 5, 1], [2, 24, 1, 7]]); A
Out[2]: 
GF([[ 0, 29,  2,  9],
    [20, 24,  5,  1],
    [ 2, 24,  1,  7]], order=31)

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

In [4]: P
Out[4]: 
GF([[0, 1, 0],
    [1, 0, 0],
    [0, 0, 1]], order=31)

In [5]: L
Out[5]: 
GF([[ 1,  0,  0],
    [ 0,  1,  0],
    [28, 14,  1]], order=31)

In [6]: U
Out[6]: 
GF([[20, 24,  5,  1],
    [ 0, 29,  2,  9],
    [ 0,  0, 19,  8]], order=31)

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

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