How Do You Find the Inverse of a Matrix Modulo 26?

  • Thread starter Thread starter DODGEVIPER13
  • Start date Start date
  • Tags Tags
    Inverse Modulus
Click For Summary

Discussion Overview

The discussion revolves around finding the inverse of a 2x2 matrix modulo 26. Participants explore various methods, including the Euclidean algorithm, adjoint matrices, and modular arithmetic, while seeking clarification on their calculations and the correctness of their approaches.

Discussion Character

  • Homework-related
  • Mathematical reasoning
  • Debate/contested

Main Points Raised

  • One participant calculates the determinant of matrix A as -121 and finds -121 mod 26 to be 9, expressing confusion about the subsequent steps in finding the inverse.
  • Another participant notes that 26 and 9 are coprime, suggesting this is a result of the Euclidean algorithm.
  • Several participants question the method of finding the inverse, with one suggesting the use of the adjoint matrix and expressing confusion about the book's solution, which states the inverse is 3.
  • Another participant proposes testing if 26k + 1 is divisible by 9 to find the inverse, leading to a conclusion that k=1 gives 3.
  • Participants discuss the manipulation of equations derived from the Euclidean algorithm, with some expressing confusion over the presence of zero in their calculations.
  • There are multiple references to the need for clarity in the steps taken to derive the inverse, with some participants attempting to clarify the process of working with modular arithmetic and the adjoint matrix.
  • One participant shares their calculations involving fractions and modular arithmetic, leading to further questions about the steps taken to arrive at specific values.
  • Another participant emphasizes the importance of generating a multiplication table for modulo 26 to aid in solving for variables in the equations derived from the adjoint matrix.

Areas of Agreement / Disagreement

Participants express varying levels of understanding and confusion regarding the methods for finding the inverse of the matrix. There is no consensus on the correct approach, and multiple competing views on how to proceed remain evident throughout the discussion.

Contextual Notes

Limitations include unresolved mathematical steps, particularly in the application of the Euclidean algorithm and the manipulation of equations. Participants also express uncertainty about the definitions and methods used in modular arithmetic.

  • #31
A=9 b=2 c=1 d =15
 
Physics news on Phys.org
  • #32
<br /> \begin{pmatrix}<br /> 9 &amp; 2\\<br /> 1 &amp; 15\\<br /> \end{pmatrix}<br />
 
  • #33
Sweet man you are the best, so if I see this on the test I should follow the instructions you gave?
 
  • #34
Excellent!
Now demonstrate that the answer is correct:
<br /> \begin{pmatrix}<br /> 9 &amp; 2\\<br /> 1 &amp; 15\\<br /> \end{pmatrix}<br /> \begin{pmatrix}<br /> 5 &amp; 8\\<br /> 17 &amp; 3\\<br /> \end{pmatrix} = ?<br />
Remember this: When you do the adds and multiplies you can start by ignoring the modulo 26 arithmetic. But before you finish, bring everything back to 0 to 25.

For example, if you work it out and get this:
<br /> \begin{pmatrix}<br /> 1303 &amp; 2604\\<br /> 3905 &amp; 5206\\<br /> \end{pmatrix}<br />
Take the next step to bring it to modulo 26:
<br /> \begin{pmatrix}<br /> 1303 &amp; 2604\\<br /> 3905 &amp; 5206\\<br /> \end{pmatrix} = <br /> \begin{pmatrix}<br /> 3 &amp; 4\\<br /> 5 &amp; 6\\<br /> \end{pmatrix}<br />
 
  • #35
DODGEVIPER13 said:
Sweet man you are the best, so if I see this on the test I should follow the instructions you gave?
Once you demonstrate that your answer is correct (which it is), you will have achieved minimum rank at modulo 26 wizardry!
 
  • #36
DODGEVIPER13 said:
Sweet man you are the best, so if I see this on the test I should follow the instructions you gave?
To answer your question directly, yes. I imagine it's an open book exam, your arithmetic has been solid, and I think you're ok with the steps that need to be followed. So you should be set.
 
  • #37
<br /> \begin{pmatrix}<br /> 1303 &amp; 2604\\<br /> 3905 &amp; 5206\\ mod 26<br /> \end{pmatrix}<br />

1303 mod 26 = 1303/26 = 50.11538-50= .11538*26 = 3

2604 mod 26 = 2604/26 = 100.15384-100 = .15384*26 = 4

3905 mod 26 = 3905/26 = 150.192307-150 = .192307*26 = 5

5206 mod 26 = 5206/26 = 200.2307-200 = .2307*26 = 6

The result is:
<br /> \begin{pmatrix}<br /> 3 &amp; 4\\<br /> 5 &amp; 6\\ mod 26<br /> \end{pmatrix}<br />
 
  • #38
Oh I guess I should have set the matrix

<br /> \begin{pmatrix}<br /> 1303 &amp; 2604\\<br /> 3905 &amp; 5206\\ mod 26<br /> \end{pmatrix}<br />

equal to the identity matrix:

<br /> \begin{pmatrix}<br /> 1 &amp; 0\\<br /> 0 &amp; 1\\ mod 26<br /> \end{pmatrix}<br />
 
  • #39
You need to do the matrix multiplication. Multiply what you calculated as the matrix inverse with the original matrix:
<br /> \begin{pmatrix}<br /> 9 &amp; 2\\<br /> 1 &amp; 15\\<br /> \end{pmatrix}<br /> \begin{pmatrix}<br /> 5 &amp; 8\\<br /> 17 &amp; 3\\<br /> \end{pmatrix} = ?<br />
Do you know how to do a matrix multiply?
 
  • #40
Yes sir sorry for the late reply:

<br /> \begin{pmatrix}<br /> 79 &amp; 78\\<br /> 260 &amp; 53\\<br /> \end{pmatrix}<br />
 
  • #41
ahhh now I take the mod 26 of each number and compare to the unit matrix correct?
 
  • #42
Hey I have a question what does finding the inverse actually mean in regards to cryptography? More specifically the Hill cipher. I have done another problem and checked it but I don't actually know what I am finding?
 
  • #43
DODGEVIPER13 said:
ahhh now I take the mod 26 of each number and compare to the unit matrix correct?
That is 100% correct. And as you can probably see - it works out to the unit matrix. Congratulations!
 
  • #44
DODGEVIPER13 said:
Hey I have a question what does finding the inverse actually mean in regards to cryptography? More specifically the Hill cipher. I have done another problem and checked it but I don't actually know what I am finding?
Knowing how to invert a matrix is critical to the Hill cipher - otherwise you won't be able to decode the message.
 
  • #45
So let's says the message was originally this: EHQC what would the new matrix give IBAO?
 
  • #46
This is assuming the numbers correspond to the letters of the alphabet
 
  • #47
DODGEVIPER13 said:
So let's says the message was originally this: EHQC what would the new matrix give IBAO?
By my calculations (using Excel spread sheet):
<br /> \begin{pmatrix}<br /> 4 (E) &amp; 7 (H)\\<br /> 16 (Q) &amp; 2 (C)\\<br /> \end{pmatrix}<br /> \begin{pmatrix}<br /> 5 &amp; 8\\<br /> 17 &amp; 3\\<br /> \end{pmatrix} = <br /> \begin{pmatrix}<br /> 9 (J) &amp; 1 (B)\\<br /> 10 (K) &amp; 4 (E)\\<br /> \end{pmatrix}<br />

edit-----
I just noticed where you got EHQC. I was assigning 0, 1, 2, ... 25 to A, B, C, ... Z. You're assigning 1, 2, 3, ... 0.
Your EHQC is the original matrix and your IBAO is the inverse.

I thought you were trying to encode "EHQC" using the matrix as a cypher.

IMRR MIUTBZFN
 
Last edited:
  • #48
Here's an example of how you would use it to code and decode:

Plain text: "encryption"
<br /> \begin{pmatrix}<br /> 4 (E) &amp; 13 (N)\\<br /> 2 (C) &amp; 17 (R)\\<br /> 24 (Y) &amp; 15 (P)\\<br /> 19 (T) &amp; 8 (I)\\<br /> 14 (O) &amp;13 (N)\\<br /> \end{pmatrix}<br /> \begin{pmatrix}<br /> 5 &amp; 8\\<br /> 17 &amp; 3\\<br /> \end{pmatrix} = <br /> \begin{pmatrix}<br /> 7 (H) &amp; 19 (T)\\<br /> 13 (N) &amp; 15 (P)\\<br /> 11 (L) &amp; 3 (D)\\<br /> 23 (X) &amp; 20 (U)\\<br /> 5 (F) &amp; 21 (V)\\<br /> \end{pmatrix}<br />
Cipher text is: "htnpldxufv"
<br /> \begin{pmatrix}<br /> 7 (H) &amp; 19 (T)\\<br /> 13 (N) &amp; 15 (P)\\<br /> 11 (L) &amp; 3 (D)\\<br /> 23 (X) &amp; 20 (U)\\<br /> 5 (F) &amp; 21 (V)\\<br /> \end{pmatrix}<br /> \begin{pmatrix}<br /> 9 &amp; 2\\<br /> 1 &amp; 15\\<br /> \end{pmatrix} = <br /> \begin{pmatrix}<br /> 4 (E) &amp; 13 (N)\\<br /> 2 (C) &amp; 17 (R)\\<br /> 24 (Y) &amp; 15 (P)\\<br /> 19 (T) &amp; 8 (I)\\<br /> 14 (O) &amp;13 (N)\\<br /> \end{pmatrix}<br />
Plain text: "encryption"

If you want to change the encryption code, you generate a new matrix and its inverse.
 
  • #49
Ok thanks this clears it up
 

Similar threads

What is the inverse of the 3x3 matrix mod 26
  • · Replies 3 ·
Replies
3
Views
14K
Why Does Expanding (13-8)^99 Not Yield the Same Remainder as 5^99 Modulo 13?
  • · Replies 7 ·
Replies
7
Views
2K
How to read a column of data into Fortran without arrays? (Fortran 77)
  • · Replies 7 ·
Replies
7
Views
3K
High School What theorems are available when using modulo arithmetic?
  • · Replies 11 ·
Replies
11
Views
2K
Undergrad Modulo and Modulus in math and computer programming
  • · Replies 5 ·
Replies
5
Views
3K
Trouble understanding modulo equivalence notation
  • · Replies 1 ·
Replies
1
Views
2K
High School Two interesting number theory tricks
  • · Replies 3 ·
Replies
3
Views
1K
Engineering How do I find the transition matrix of this dynamic system?
  • · Replies 18 ·
Replies
18
Views
3K
Comp Sci Finding Cousins of Giuga Numbers: Can You Solve This Prime Number Puzzle?
  • · Replies 32 ·
2
Replies
32
Views
5K
Engineering How Can MATLAB Be Used to Analyze Signal Duration and Frequencies Using DFT?
  • · Replies 1 ·
Replies
1
Views
3K