La matrice inversa modulo n
La matrice inversa modulo \(n\) di una matrice \(A\) è una matrice \(A^{-1}\) tale che, quando viene moltiplicata per \(A\), il risultato è congruente alla matrice identità \(I\) modulo \(n\), ovvero $$ AA^{-1} \equiv I \mod n $$
Ogni elemento della matrice prodotto è congruente all'elemento corrispondente nella matrice identità, modulo n.
Come si calcola la matrice inversa mod n
Considero una matrice quadrata 2x2 modulo n
$$ A = \begin{pmatrix} a & b \\ c & d \end{pmatrix} $$
Per calcolare la matrice inversa A-1 modulo n di una matrice A con elementi interi calcolo il determinante modulo n.
$$ det(A) $$
E' necessario il determinante e n siano coprimi, cioè il loro massimo comune divisore deve essere 1, altrimenti la matrice A non è invertibile modulo n.
Se il determinante e n sono coprimi, posso procedere con il calcolo.
$$ MCD( \ \det(A) \ , \ n \ ) = 1 $$
Trovo l'inverso moltiplicativo del determinante modulo n, che indico con det(A)−1 mod n
In altre parole trovo un numero det(A)−1 che moltiplicato per det(A) restituisce 1 mod n.
$$ \det(A) \cdot \det(A)^{-1} \equiv 1 \mod 9 $$
A questo punto, posso ottenere la matrice inversa A-1 modulo n tramite questa formula:
$$ A^{-1} = det(A)^{-1} \cdot \begin{pmatrix} d & -b \\ -c & a \end{pmatrix} \ \mod n $$
Infine, aggiusto ogni elemento della matrice inversa risultante per assicurarmi che sia nel range da 0 a n−1.
Un esempio pratico
Considero una matrice quadrata 2x2 nel modulo n=9.
$$ B = \begin{pmatrix} 2 & 3 \\ 1 & 4 \end{pmatrix} $$
Calcolo il determinante della matrice B modulo 9.
$$ \det(B) = 2 \cdot 4 - 3 \cdot 1 = 5 \ \mod 9 $$
Verifico che det(B)=5 e n=9 siano coprimi, ovvero che il loro massimo comune divisore sia uguale a 1 modulo 9.
$$ MCD(5,9) = 1 \ \mod 9 $$
In questo caso sono coprimi, quindi la matrice B è invertibile e posso procedere.
Nota. In caso contrario, la matrice B non è invertibile. Se det(B) e n non sono coprimi, la matrice B non ha una matrice inversa e il calcolo finisce qui.
L'inverso moltiplicativo di 5 modulo 9 è 2, perché
$$ 5 \cdot 2 \equiv 10 \equiv 1 \mod 9 $$
Applico la formula per l'inversa di una matrice 2x2 con operazioni modulo 9
$$ B^{-1} \mod 9 = 2 \cdot \begin{pmatrix} 4 & -3 \\ -1 & 2 \end{pmatrix} \mod 9 $$
$$ B^{-1} \mod 9 = \begin{pmatrix} 2 \cdot 4 & 2 \cdot (-3) \\ 2 \cdot (-1) & 2 \cdot 2 \end{pmatrix} \mod 9 $$
$$ B^{-1} \mod 9 = \begin{pmatrix} 8 & -6 \\ -2 & 4 \end{pmatrix} \mod 9 $$
Aggiusto i valori nella matrice per fare in modo che siano compresi nel range da 1 a 9.
Ad esempio, in questo caso ci sono due congruenze -6≡3 mod 9 e -2≡7 mod 9.
Quindi, l'inversa modulo 9 della matrice B è la seguente:
$$ B^{-1} \mod 9 = \begin{pmatrix} 8 & 3 \\ 7 & 4 \end{pmatrix} \mod 9 $$
Questo esempio dimostra come calcolare l'inversa modulo n di una matrice 2x2 quando il determinante della matrice e n sono coprimi.
Verifica. Moltiplico la matrice A per la sua matrice inversa A-1 modulo 9.
$$ B \cdot B^{-1} \mod 9 = \begin{pmatrix} 2 & 3 \\ 1 & 4 \end{pmatrix} \cdot \begin{pmatrix} 8 & 3 \\ 7 & 4 \end{pmatrix} \mod 9$$
$$ B \cdot B^{-1} \mod 9 = \begin{pmatrix} 2 \cdot 8 + 3 \cdot 7 & 2 \cdot 3 + 3 \cdot 4 \\ 1 \cdot 8 + 4 \cdot 7 & 1 \cdot 3 + 4 \cdot 4 \end{pmatrix} \mod 9$$
$$ B \cdot B^{-1} \mod 9 = \begin{pmatrix} 37 & 18 \\ 36 & 19 \end{pmatrix} \mod 9$$
Infine, aggiusto i valori con il modulo 9.
Ad esempio, 37≡1 mod 9, 18≡0 mod 9, 36≡0 mod 9, 19≡1 mod 9
$$ B \cdot B^{-1} \mod 9 = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} \mod 9$$
Il risultato finale è la matrice identità modulo 9.
E così via.
