Please help with the following matrices questions:

*Appreciate it if you can show your work

If you are unable to view the questions below, here is link https://massey.limfinity.com/207/hillcipher.pdf

Thanks

Conclusion Will Gaussian elimination always work? The answer is no - some matrices do not have inverses, and the algorithm will get stuck. Take a course in linear algebra to learn the details. It turns out that the Hill Cipher can be broken. If an enemy knows the plaintext and corresponding ciphertext of a single message, she can reverse engineer to discover the key, with which to decrypt future messages. Fortunately for modern electronic communication, mathematicians have developed more sophisticated and secure methods of encryption. They all build upon the basic ideas we have learned in discrete math. 30. (Bonus) The plaintext "BONUS PROBLEM" gets encrypted to "QF43406. 1FJJXTS", and the Hill Cipher key is nine characters long. Decrypt the message "V. 8Y_Q063163.15".28. Use the Gaussian elimination algorithm to find the inverse of A = 14 5]. 18 4 - (the key "NERD" ) 29. Use shorthand to describe the first three row operations you would do on this matrix to implement Gaussian elimination. Do not actually do them. 4 15 21 2 3 1 0 11 13 0 0Example Find the inverse of: 5 A = 20 18 Start with an augmented matrix [A | /), and do row operations until it becomes [/ | B]. 5 7 1 0 0 09 00 to 20 010 9 18 0 0 1 23 24 21 0 (R1 + 2"' R1) 8 20 1 0 1 3 9 180 0 1 1 23 24 21 0 0 (R2 + R2 - 8R1) 0 0 14 37 10 9 18 0 01 23 24 21 0 0 (R3 + Rs - 3R1) 0 0 14 37 1 0 0 22 28 19 0 1 23 24 21 0 0 (R2 ++ Rs) 22 19 0 0 0 14 37 1 0 23 24 | 21 0 (R2 + 22 1 R2) 1 40 28 0 37 0 1 23 24 21 0 0 (R3 + 14-1 R3) 0 1 5 0 28 0 0 29 : 0 1 23 24 21 0 0 (R2 + R2 - 5R3) 0 1 0 18 26 28 0 29 3 0 1 23 0 22 10 0 (R1 + R1 - 24R3) 0 1 0 18 26 28 0 0 1 29 1 0 0 18 27 12 (R1 + R1 - 23R2) 10 26 28 0 0 1 3 0 We have found the inverse: 18 27 12 A- = B = 18 26 28 29 3 0 As you can see, finding the inverse can be computationally intense. Mathematicians prefer to write computer programs to implement such algorithms. 19Gauss Elimination Algorithm Since the exact same row operations must be done for both systems, they can be solved together using the augmented matrix: 20 8 |0 The general procedure for turning the coefficient matrix into / is called Gaussian elimination. Here the steps are illustrated with a 3 x 3 matrix. (I) Start with column j = 1. (II) If the diagonal position j, j is zero, swap row j with another row below it. (III) Multiply row j by a constant to put a 'l' in position j, j. (IV) Add/subtract a multiple of row j to each row below it to put zeros under the j, j entry. (V) Move to the next column, and go back to step (II). After all the diagonal entries are 'l', with zeros below, your augmented matrix will look like: (VI) Now work your way backward, starting with the last column, zeroing out the entries above the diagonal: * 1 0 010 + (VII) Your augmented matrix now displays the inverse on the right-hand side. 1827. Go through the same exact process to solve the second system 13 1 612 = 17Row Operations By convention, let's refer to equation i as row i, denoted Ra. Any linear system can be manipulated in three ways without changing the solution, as illustrated here with shorthand descriptions of the row operations: . swap two equations (e.g. R1 ) R2) 20611 + 8622 = 13611 + 622 = 1 . multiply one equation by a non-zero constant (e.g. R2 + 3R2) 20611 + 8622 = 0 39611 + 3622 = 3 . add a multiple of one equation to another equation (e.g. R2 + R2 + 2R1) 2061 + 8622 = 79611 + 19622 = 3 Gauss Elimination We will design a sequence of row operations that progressively simplify the system of equations, eventually revealing the solution. It is unnecessary to write the variables each time; only the coefficients and right-hand side values are required. Going back to the original system, write the augmented matrix 20 8 0 First multiply row 1 by 13-1 (mod 41) = 19, and reduce (mod 41). (R1 + 19R1) 7 19 20 8 0 Now subtract 20 times row 1 from row 2, and reduce. (R2 + R2 - 20R1) 19 19 -372 -380 - 18 38 30 Next multiply row 2 by 38-1 (mod 41) = 27, and reduce. (R2 + 27R2) 19 19 1026 810 - 8 P|89 Finally, subtract 19 times row 2 from row 1, and reduce. (R1 + R1 - 19R2) 1 9 -570 Since the coefficient matrix is now the identity, it simply reads bj1 = 4 and b21 = 31. 16Computing the Inverse Matrix Suppose Alice and Bob will communicate using the key "MATH" . It is easy for Alice to find the encoding matrix A. Just fill the 2 x 2 matrix with the numeric equivalents of M-A-T-H. A = 120 8 Bob's task is more difficult. He must find the decoding matrix B so that BA = /; thus B is the inverse of A. We can easily check that 20 B = 31 27 is the inverse, because: BA = 31 27 20 [452 164] 943 247 = 0 1 (mod 41) But inverses commute, so AB is also the identity: AB - 20 8 31 29 - $3 328 616 = 6 9 (mod 41) It turns out that checking the solution is easy, but finding it is not. We will now describe an algorithm that Bob can use to find B. Linear Equations Assume that we are working in Zan, so all equations are true (mod 41). Let's label the unknown entries of B, and consider the equation AB = I. AB = By the definition of matrix multiplication, this breaks into two matrix-vector equations: 20 8 621 Let's focus on the first of these: which corresponds to the following system of simultaneous linear equations 13b11 + b-22 = 20611 + 86-22 = 0 1524. Use the web app to find the encoding and decoding matrices for the key "EASY", then verify that AB = 12 (mod 41). 25. Use the web app to find the decoding matrix for the key "HOKIES". 26. By hand, show the steps to decode "II?N4B' using the key "HOKIES". 14As hoped, this procedure has restored the original message "RENDEZVOUS AT 9". For another example, let's decrypt "F3RM7VUJ6SE" using the key "NERD". The web app tells us that the decoding matrix is B = | 24 11 15 2 The encrypted message matrix is M = 6 30 18 13 34 22] 26 21 10 33 19 5 Multiplying them gives: BM = 24 11] [6 30 18 13 34 22 15 2 26 21 10 33 19 5 430 951 542 675 1025 583 = 142 492 290 261 548 340 20 8 9 19 0 19 0 3 15 15 12 (mod 41) which translates to "THIS_IS_COOL". Notice that plaintext "OO" appeared as "6S" in ciphertext. Entire Process Summary Imagine Alice and Bob want to communicate secret messages. If any third party intercepts a message, they shouldn't be able to read it. 1. Alice and Bob agree on a key word or phrase. 2. Alice uses the key to create the encryption matrix A. 3. Bob uses the key to create the decryption matrix B, so that BA = I. 4. Alice creates a message matrix M, pre-multiplies it by A to get AM, and sends the corresponding ciphertext to Bob. 5. If anybody intercepts the ciphertext, it will look like gibberish. 6. Bob receives the ciphertext, converts it to M, knowing that M = AM. Then Bob pre-multiplies by B BM = B(AM) = (BA)M = IM = M which is the original plaintext message. 23. Use the web app with the key from problem #14 to decode the quote at the beginning of this project. 1322. By hand, show the steps to encrypt the message "RU READY" using the key "NERD". You can check your answer with the computer. Decryption Only the intended recipient should be able to read your message. So your key should be privately shared, and not easy to guess. Given the key and the encrypted message, how can we undo the encryption? The answer is to use a matrix inverse. When decrypting, the hillcipher web app will display both the encoding matrix A, and a decoding matrix called B. This is calculated so that BA = I (mod 41), and thus B and A are inverses. In other words, multiplying by B reverses the effect of multiplying by A. When both operations are appled to a message, you end up with the original. For example, if the key is "MATH", then A = 20 8 B = 31 27 You should check that the decoding and encoding matrices multiply to give the identity. BA= 20] [13 1] [452 164] 943 247] = 6 1 (mod 41) A message is decrypted just like it is encrypted, except that we use the decoding matrix B instead of the encoding matrix A. For example, to decrypt "IBRLCJ849F7FN14M" using the key "MATH": BM = 20 9 2 18 12 3 10 35 31] 31 27 36 6 34 6 14 28 31 13 756 128 168 292 600 760 384 1251 224 1476 534 471 1066 1922 1312 18 5 14 4 5 26 22 15 21 19 1 20 0 36 (mod 41) 12Let's do one more example, this time by hand and via computer. The key is "NERD" and the message is "GOBBLE". Check that the encoding and message matrices are: A = 18 4 M = 2 12 When you multiply them, you should get AM = 108 270 53 [26 24 12 134 318 56 11 31 15 (mod 41) Finally read off the encoded message to be "ZXLK40". Use the web app to check these calculations. 18. What is the encoding matrix for the key "HOKIES" ? 19. Reduce the matrix 48 15 138 209 410 92 97 43 (mod 41) and read off the message. 20. Use the web app to encrypt the message "THE CAT IN THE HAT" using the key "SEUSS". How do the two occurrences of "THE" translate as ciphertext? 21. Use the web app to encrypt your favorite quotation. Email me (kmassey@cn.edu) the key and cipher- text. 11Encryption Matrix multiplication will be used to jumble the message matrix, so that nobody could decipher the result without the key. To encrypt the message with a key: . Create a square encoding matrix A from the key. . Create the message matrix M with the same number of rows as A. . Multiply the encoding matrix by the message matrix to form AM. This creates linear combinations of the encoding matrix columns using coefficients from the message matrix. . Reduce modulo 41 (or generally the # of characters in your alphabet). . Convert back to characters. Let's illustrate by encoding "RENDEZVOUS AT 9" with the key "MATH". We already found A and M: A = 13 8 M = 18 5 14 4 5 26 22 15 20 21 19 0 1 20 0 36 0 Now multiply A by M: AM 13 1 18 5 14 4 5 26 22 15 20 8 21 19 0 1 20 0 36 0 255 84 182 53 85 338 322 195 528 252 280 88 260 728 300 9 2 18 12 3 10 35 31 36 6 34 6 14 28 31 13 (mod 41) Here is a detailed working of the first entry calculation: 13 . 18 + 1 . 21 = 255 = 9 (mod 41) Converting the result matrix back to characters (9 - 1, 2 - B, etc), "RENDEZVOUS AT 9" translates to 'IBRLCJ849F7FN14M", which can transmitted securely. Now use the key "CNEAGLE" instead. The corresponding matrices are: 14 5 18 5 14 4 57 A = 7 12 M = 26 22 15 21 19 1 2 0 1 20 0 36 3 5 [18 5 4 5 AM = 7 26 22 15 21 19 5 1 12 2 0 1 20 0 36 418 328 352 306 461] 200 1 359 151 570 116 49 125 41 116 8 0 24 19 10 = 36 7 31 28 37 (mod 41) 34 8 2 0 34 This time the same message gets converted to "H_XSJ9G41 . 7HB_7". You should convince yourself of the calculations above. They are quite tedious to do by hand. On the course web page is an app called hillcipher.php that creates the matrices and does the calculations for you. 10Message Matrix Suppose you want to encode the secret message: "RENDEZVOUS AT 9". First, we convert it to (18, 5, 14, 4, 5, 26, 22, 15, 21, 19, 0, 1, 20, 0, 36) The message matrix M should have the same number of rows as the encoding matrix A. For example, if the key is "MATH", then both matrices should have two rows, and in particular M = 18 5 14 4 5 26 22 15 21 19 0 1 20 0 36 0 However, if the key is "CNEAGLE", then we need three rows and 18 5 14 4 5 M = 26 22 15 21 19 1 20 0 36 Any extra spots in the message matrix may be filled in with zeros. 15. Write the encoding matrix for the key "MATHEMATICS". 16. If the key is "TIP", write the message matrix for the message "SELL APPLE". What if the key were "HOT TIP" instead ? 17. If the key is & characters long, find a formula for the number of rows in A and M.Encryption We will now explain the Hill Cipher using the language of modular arithmetic and linear algebra. Character-Numeric Conversion First we will map each character in our alphabet to a corresponding number. In order to unambiguously encrypt/decrypt messages, we need those numbers to have inverses modulo the total number of characters. Therefore the length of the alphabet should be prime. The English alphabet has 26 characters, but 26 is not prime. We also want to include other symbols besides letters. Our map will include a total of 41 characters - a good choice since 41 is prime. A B C D E FG HI JK LM NOP QR ST 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 U V W X Y Z 1 2 3 4 5 6 7 8 9 ? 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 Lower and upper case letters are not distinguished. The phrase "DO IT" would be: (4, 15, 0, 9, 20) 14. The key to decoding the quote at the beginning of this project is (2, 4, 9, 19, 3, 18, 5, 20, 5). Translate this back to characters. Encoding Matrix We will use a combination of matrix multiplication and modular arithmetic to encrypt our messages. First we must create an encoding matrix, which we'll call A. Given the key (code word), use the table above to convert it into numbers, which are placed in a square matrix. We'll fill the entries in reading order, padding any extra space with numbers beginning with one. For example, suppose the key is "MATH". This converts to (13, 1, 20, 8). Since it has only four characters, we can fit it in a 2 x 2 matrix as follows A = 20 8 Notice we begin at the top left and fill row-by-row. Now let's use the key "CNEAGLE", which corresponds to (3, 14, 5, 1, 7, 12,5), and the encoding matrix 3 14 5 A = 7 2 Note that there were 7 characters, so the first square matrix that fits must be 3 x 3. The extra spots are padded with 'l' and '2'.12. Verify that A= 0 4 and B= . | are inverses (mod 5), but they are not inverses (mod 7). 21 6 32 13 0 13. Verify that A = 23 and B = 17 0 31 are inverses (mod 41). 9 37 16 25 7Therefore these two matrices are inverses of each other. In particular we could write A =B-1 B = A-1 Check that you can reverse the order of multiplication to get BA = 32 316 3 -12 Not all matrices have inverses, but many do. Later in this project we will learn how to compute the inverse of a matrix. 10. Verify that A = [3 and B = '5 12 are inverses by calculating both AB and BA. Show your work. 11. Show that these matrices are inverses by computing (show your work) We'll be using matrices to encrypt messages, so inverses will be essential to guarantee the intended recipient can decipher the message back to its original form. We will be working in Z,; in which case two matrices are inverses if AB reduces to I mod n. AB = I (mod n) For example, if A = 2 4 and B - 3 3 then in base 7,Verify these two matrix-vector multiplications: Identity matrices have the special property, illustrated above, that IS = 2, no matter what i is. Thus I acts just like the number one - multiplying by it doesn't change anything 9. Write /4 and compute /4 times the vector i = Inverses In mathematics there are many types of inverses: . The inverse of a number in R. 2-1 = 4 since 2 . = = 1. . The inverse of a number in En. 2-1 (mod 7) = 4 since 2 . 4 (mod 7) = 1 . The inverse of a function. If f(x) = e and g(x) = In(x), then f-1 = g since (go f)(x) = In(e) = z. The common thread here is that two objects are inverses if they undo each other and leave you with an identity. Like the antidote to a poison, or offsetting football penalties, the effects of an operation and its inverse will cancel each other out. By analogy, define two matrices to be inverses if they multiply together (in either order) to be the identity matrix I. For example, consider these two matrices: A = 2 3 B= 2 3] Earlier we saw that AB = 3 3] [32 67] - 16 9] -1 56. Multiply these matrices: 7. Multiply these matrices: 8. Matrix multiplication is not generally commutative. If A = 2 ; and B - 3 5 , compute AB and BA and show they are not the same. Identity Matrix An identity matrix is square (same number of rows and columns), with ones on the main diagonal and zeros elsewhere. Identity matrices go by the label 'I', sometimes with a subscript to indicate the size. For example, 12 = 6 9 0 Is = 10 1 0 44. Using the A from the previous problem, compute A 3,]. 5. If you are multiplying a matrix A by a vector z, what is the relationship between the the number of columns in A and the dimension of ? Matrix-matrix multiplication Remember that a matrix is just the concatenation of several vectors. We have already defined how to multiply a matrix by a vector. To multiply a matrix by another matrix, just use one vector at a time from the matrix on the right. For example, you can check that and 2 4 Combine these to get [20 9 13 : [7 2 - 26 14 37 27 Consider another example. To compute we may catenate the results of two separate matrix-vector multiplications: and thereforeThen the linear combination is written succinctly as matrix-vector multiplication Ar where : Here is another example: In general, matrices don't have to be square. For example, has two rows and three columns, so it's size is 2 x 3. We could multiply it by a 3 dimensional vector, e.g. 1. Compute 4 25 - 2 [ 92]. 2. If the linear combination in the previous problem were written as Ai, (a) write the matrix A, and state its size (b) write the vector , and state its dimension. 3. How many rows and colums does this matrix have? 4 23 A = - 2 5 1 2Hill Cipher Project KBOTTQ1EP-77, VO. L, XUOHSBY, _71ZVPKDE678_X, N2Y-8HI4VS, , 6Z28DDW5N7ADY013 Directions: . Answer all numbered questions completely. . Show non-trivial work in the space provided. . Non-computational answers should be given in complete sentences. Introduction The affine cipher encrypts one letter at a time, resulting in a simple permutation of the alphabet. For the casual observer, messages are unintelligible. But crypto-analysts can easily break the affine cipher by observing letter frequencies. For example, the most commonly occurring letter in the ciphertext is likely to be 'E' in the plaintext. In this project, we will develop the Hill Cipher, which encrypts several letters at a time, making frequency analysis much more difficult. The method uses modular arithmetic, as well as the basic linear algebra of matrices and vectors. Vectors and Matrices For all practical purposes, a vector is just a list of numbers. We will take the convention of writing the vector as a column. For example " = [3] 1 = Low The dimension of a vector is the same as its length. So u is two-dimensional, 7 is three-dimensional, and w is four-dimensional. A regular number (or a one-dimensional vector), is called a scalar. If vectors have the same dimension, you can perform basic arithmetic on them: addition/sutraction and scalar multiplication. For example, Often, vectors are identified by name. If we define d = then -4+5.1-2.-2] u +57 - 20 = 1+5-3-2.0 16 2+5-5-2-7 13 This result is referred to as a linear combination of the three vectors. When there are many vectors to deal with, they can be concatenated into a matrix. In the previous example, we could define a matrix called A that contains u, 7, and w, and a vector & that contains the coefficients in the expression # + 50 - 2w. 1 A =