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$ – Daniel Lichtblau Jun 4 '16 at 22:46
  • $\begingroup$ @DanielLichtblau: Thanks! That Modulus trick makes it easy! $\endgroup$ – Matt Groff Jun 4 '16 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$ – J. M.'s ennui Jun 5 '16 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$ – Daniel Lichtblau Jun 5 '16 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$ – 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;
{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, privacy policy and cookie policy

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