No entiendo por qué la inversa es esto?

Question

mi pregunta está relacionada con la matriz de la inversión y el cifrado de Hill(usted no tiene que saber qué es lo que me ayude)

Mi maestro me dio un ejemplo. Primero tenemos una matriz (la clave de la matriz) que multiplicado por un vector de letras es otro vector con las anteriores cartas cifradas. Para descifrar lo que necesita la inversa de la clave de la matriz y, a continuación, se multiplica por el vector de la cifra de cartas, de este modo se obtiene el vector de descifrar las letras (el verdadero mensaje)

Bien, esta es la matriz, la clave de la matriz que tengo que multiplicar los vectores de las letras y obtener el mensaje cifrado.

$$ \left[ \begin{array}{ c c } 22&27&18 \\ 18&28&5 \\ 4&17&1 \end{array} \right] $$

Sin embargo, cuando trato de invertir es el uso de múltiples calculadoras en internet e incluso lenguajes de programación (por ejemplo, Ruby) puedo obtener una matriz (el inverso a uno) con una gran cantidad de 0.decimales de los números. No números enteros

¿Por qué estoy esperando para obtener números enteros? Porque mi profesor me dio la inversa. Este es:

$$ \left[ \begin{array}{ c c } 1&18&8 \\ 2&8&11 \\ 20&24&14 \end{array} \right] $$

No entiendo como esta. Sé que la matriz inversa es única, pero entonces, ¿quién está equivocado? Calculadoras de llevar en la misma matriz, sin embargo, la matriz de mi maestro dio el derecho de la matriz, debido a que puede descifrar el mensaje cifrado bien, por lo que debe ser la buena.

No se olvide de decirle a usted, que la inversa es la matriz mod 29.

Alguna idea de cómo podría llegar a la misma matriz, como mi maestro? Muchas gracias.

Answer 1

Todas las calculadoras que encontró hacer sus operaciones aritméticas con los racionales o reales, por lo que están muy mal de la tecnología de la aritmética en el campo de $F_{29}$. Pero el algoritmo habitual de la inversión de una matriz es inmune a tales bagatelas, y funciona de la misma. Yo camino a través de este. Como siempre, empezamos con la matriz aumentada con una identidad bloque de la derecha $$ \pmatrix{22&27&18&1&0&0\cr18&28&5&0&1&0\cr4&17&1&0&0&1\cr}. $$ Para empezar queremos un $1$ en la esquina superior izquierda. Para ello dividimos la primera fila por $22$. En $F_{29}$ tenemos $4\cdot22=88=1$, lo $22^{-1}=4$, y podemos así multiplicar la primera fila por $4$ (y recordar a reducir todo el modulo $29$) para obtener $$ \pmatrix{1&21&14&4&0&0\cr18&28&5&0&1&0\cr4&17&1&0&0&1\cr}. $$ Ahora podemos pivote de la primera columna. Por lo tanto, añadir la primera fila a la segunda multiplicada por $-18=11$, y a la tercera multiplicada por $-4=25$. Reducir el modulo $29$ y obtener $$ \pmatrix{1&21&14&4&0&0\cr0&27&14&15&1&0\cr0&20&3&13&0&1\cr}. $$ A continuación tenemos un $1$ a $(2,2)$-posición. Esta vez $14\cdot27=378=1$$F_{29}$, por lo que multiplicamos la segunda fila por $14$. $$ \pmatrix{1&21&14&4&0&0\cr0&1&22&7&14&0\cr0&20&3&13&0&1\cr}. $$ Lo siguiente que tenemos clara la segunda columna, agregando a la primera fila de la segunda fila multiplicada por $8=-21$, y añadiendo a la tercera fila de la segunda fila multiplicada por $9=-20$: $$ \pmatrix{1&0&16&2&25&0\cr0&1&22&7&14&0\cr0&0&27&18&10&1\cr}. $$ La multiplicación de la tercera fila por $14=27^{-1}$ nos da $$ \pmatrix{1&0&16&2&25&0\cr0&1&22&7&14&0\cr0&0&1&20&24&14\cr}. $$ A continuación, podemos trabajar en la tercera columna, y añadir la tercera fila (multiplicado por la constante apropiada) para las dos filas superiores, y al final $$ \pmatrix{1&0&0&1&18&8\cr0&1&0&2&8&11\cr0&0&1&20&24&14\cr}. $$ La reducción de la fila funcionado como se esperaba por lo que podemos deducir que la matriz dada es no singular, y su inversa se puede leer desde la mitad derecha de la anterior resultado final.

Usted debe caminar lejos de este ejercicio con el entendimiento de que el algoritmo dado en un curso de álgebra lineal funciona sobre cualquier campo. Sólo los detalles del campo de la aritmética variar de caso-por-caso. Aquí, en particular, la división se veía muy diferente, pero también probar si una entrada es igual a cero, $0=29=\cdots$, aparece de vez en cuando. Para más información revisar el algoritmo, y se observa que todas las operaciones y leyes de álgebra que el algoritmo depende, mantenga en todos los campos.

Answer 2

Usted podría utilizar Maple para encontrar la inversa de la matriz. Usted sólo tiene que escribir el comando Inverso(A) mod n. Las instrucciones se pueden encontrar aquí.

Para encontrar la inversa de una matriz en el campo de los números enteros mod de un primer número $p$, de continuar en un análogo de la manera como calcular la inversa de una matriz. La fórmula habitual se puede encontrar, por ejemplo, aquí.

La única cosa que usted necesita hacer es encontrar a $1/\det(A)$ en el campo de $\Bbb{Z}_p$, es decir, resolver la ecuación de $\det(A) \cdot x =1$$\Bbb{Z}_p$, y en lugar de dividir las entradas de $A^*$ con el determinante de a $A$, se multiplican las entradas de $A$$x$, la solución de la ecuación anterior en $\Bbb{Z}_p$.

Answer 3

Por la regla de Cramer, cada coeficiente de la matriz inversa es el determinante de una submatriz dividida por el determinante $D$ de la matriz original. Aquí $D=15\pmod{29}$, cuya inversa es $2$ mod $29$, por lo tanto los coeficientes de la matriz inversa son el doble de los determinantes de las submatrices, es decir, enteros mod $29$.

Tenga en cuenta que desde $29$ es una de las principales, cada número entero que no es $0$ mod $29$ tiene un número entero inversa por lo tanto el único caso en el que este puede fallar es cuando el determinante es $0$ mod $29$, y entonces no hay inversa de la matriz de todos modos.