3
$\begingroup$

What are the rules for modular arithmetic when multiplying two matrices? I want to calulate $C = AB \mod{n}.$ Aside from the obvious way of performing the modulo after the multiplication, when and where can i safely perform the modulo during the multiplication algorithm?


[1] Normally:

$C_{ij}=\displaystyle\sum\limits_{k=0}^m A_{ik}B_{kj}$

Can I take each of these summands $A_{ik}B_{kj} \mod{n}$, as follows?

[2]

$C_{ij}=\displaystyle\sum\limits_{k=0}^m [ A_{ik}B_{kj}\pmod{n} ]$


Here is an example:

$A = \left(\begin{array}{cc} 9 & 2 \\ 10 & 10 \\ \end{array}\right)$

$B = \left(\begin{array}{cc} 7 & 3 \\ 1 & 6 \\ \end{array}\right)$

$C = \left(\begin{array}{cc} 65 & 39 \\ 80 & 90 \\ \end{array}\right)$

$C \equiv \left(\begin{array}{cc} 2 & 4 \\ 3 & 6 \\ \end{array}\right) \mod{7}$


edit:

using [2]

$C \mod 7= \left(\begin{array}{cc} 2 & 11 \\ 3 & 6 \\ \end{array}\right)$

This doesn't result in the same matrix.

1 Answers 1

4

Once you take pass into modular arithmetic, you're stuck there: $C \mod{7}$ has values in the integers $\mod{7}$, not in the integers themselves.

But modulo 7, $\left(\begin{matrix}2&11\\3&6\end{matrix}\right)=\left(\begin{matrix}2&4\\3&6\end{matrix}\right)$ simply because $11\equiv 4 \mod{7}$.

And in general, yes, you can apply $[2]$; you can even get $C\mod{7}\equiv(A\mod{7})(B\mod{7})\mod{7}$.

All this follows from the facts that $ab \mod{n}\equiv (a\mod{n}b\mod{n}) \mod {n}$ and $a+b \mod{n}\equiv (a\mod{n}+b\mod{n}) \mod{n}$