Skip to main content
edited tags
Link
Source Link
Matt Groff
  • 1.2k
  • 1
  • 10
  • 16

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