Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 2 down vote accepted

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{n}$.

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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