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$.

  • 3
    $\begingroup$ Do LUDecomposition[mat,Modulus->p] and separate out the diagonal from the upper part. $\endgroup$ Commented Jun 4, 2016 at 22:46
  • $\begingroup$ @DanielLichtblau: Thanks! That Modulus trick makes it easy! $\endgroup$
    – Matt Groff
    Commented Jun 4, 2016 at 22:59
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Jun 5, 2016 at 2:57
  • $\begingroup$ @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). $\endgroup$ Commented Jun 5, 2016 at 15:44
  • $\begingroup$ @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. $\endgroup$ Commented Jun 5, 2016 at 15:57

1 Answer 1


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;
{lu, piv, cond} = LUDecomposition[mat, Modulus -> m];

l = LowerTriangularize[lu, -1] + IdentityMatrix[Length[lu]];
d = DiagonalMatrix[Diagonal[lu]];
u = Mod[DiagonalMatrix[PowerMod[Diagonal[lu], -1, m]].UpperTriangularize[lu], m];

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.