# How can we do LDU decomposition modulo $p$?

If we have an $n \times n$ matrix, with all entries taken modulo $p$, how can we output the three matrixes in LDU decomposition, with all entries again modulo $p$? We can assume the input matrix is invertible.

That is, $LDU=A$, with $A$ given. $L$ is a lower-triangular matrix, $D$ is a diagonal matrix, and $U$ is an upper-triangular matrix. The entries of the results are modulo $p$.

• Do LUDecomposition[mat,Modulus->p] and separate out the diagonal from the upper part. – Daniel Lichtblau Jun 4 '16 at 22:46
• @DanielLichtblau: Thanks! That Modulus trick makes it easy! – Matt Groff Jun 4 '16 at 22:59
• Note that LUDecomposition[] pivots, so you have an extra permutation matrix to contend with. If you need the version without pivoting, you'll have to write your own. – J. M.'s ennui Jun 5 '16 at 2:57
• @J.M. I'm not sure it pivots in the modular case, except when it must. But I don't recall for certain (I think I added that option, and it would have been around 20 years ago). – Daniel Lichtblau Jun 5 '16 at 15:44
• @Daniel, yep, here's a random example where it pivots: LUDecomposition[{{4, 4, 4, 3}, {0, 0, 4, 1}, {3, 3, 4, 2}, {4, 1, 0, 4}}, Modulus -> 5] But that would be because the leading $2\times 2$ block is singular, which is exactly when pivoting is necessary. – J. M.'s ennui Jun 5 '16 at 15:57

For reference, here is how to generate a modular $\mathbf L\mathbf D\mathbf U$ decomposition, as suggested by Daniel in the comments:
mat = {{1, 0, 2}, {2, 1, 3}, {2, 1, 2}}; m = 5;

You can check that Mod[l.d.u, m] gives a result that is congruent to mat. If the matrix has a singular leading submatrix, one should then account for an additional permutation matrix constructed from the vector piv; how to do this is left as an exercise for the interested reader.