Please Login to access more options.

Problem 40 (General Linear Group Introduction)

We've used matrices mod $5$ to encrypt a simple message. The set of possible 2 by 2 matrices mod $5$ that we can use as an encryption key is an important set in cryptography. It's called a general linear group and written $\text{GL}(2,\mathbb{Z}_5)$. We can generalize this to $m$ by $m$ matrices mod $n$ and write $\text{GL}(m,\mathbb{Z}_n)$, though generally we require that $n$ be a prime. With each of the problems below, a single sentence or two is enough to answer the question.

  1. If we want $A$ to serve as a valid matrix for encryption, what must we require about $A$? One sentence is fine.
  2. If $A\in \text{GL}(2,\mathbb{Z}_5)$, show that $A^{-1}\in \text{GL}(2,\mathbb{Z}_5)$.
  3. If $A\in \text{GL}(2,\mathbb{Z}_5)$ and $B\in \text{GL}(2,\mathbb{Z}_5)$, why is $AB\in \text{GL}(2,\mathbb{Z}_5)$?
  4. Prove that if we know for some integer $k$ that $A_1,A_2,A_3,\ldots,A_k \in \text{GL}(2,\mathbb{Z}_5)$, then we know $A_1A_2A_3\cdots A_k\in \text{GL}(2,\mathbb{Z}_5)$.
  5. Is $\text{GL}(2,\mathbb{Z}_5)$ a group? (Which of the group properties did we not show above? Are they true?)
  6. Do your arguments above hold when considering $\text{GL}(m,\mathbb{Z}_n)$ for every $m,n \in \mathbb{N}$ such that $n\geq 2$? A conjecture with a reasonable justification (not a complete a proof) is fine in this part.
In linear algebra we showed that $\det (AB)=\det(A)\cdot \det(B)$ when working with real numbers (not mod $n$). However, since we've shown that we can perform addition and multiplication either before or after we compute remainders, and the determinant is defined entirely in terms of sums and products, then this fact is true for matrices mod $n$ as well. Similarly, we know that a matrix has an inverse if and only if the determinant is not zero. You may use these facts without proof.

Solution

  1. For a matrix to serve as an encryption key, it must be invertible. Since we are using matrices in $\mathbb{Z}_5$, this means that their determinant must be coprime to $5$.
  2. For a matrix to be in $GL(2, \mathbb{Z}_5)$, it must have an inverse in $GL(2, \mathbb{Z}_5)$. For $A^{-1}$ to be in $GL(2, \mathbb{Z}_5)$, it's ("its" not "it's=it is". It do this all the time, and I've noticed you do as well.) inverse must be as well. We know that $A \in GL(2, \mathbb{Z}_5)$. Note $A * A^{-1} = A^{-1}* A = i$. (What does the part to the left show? What should your reader take away from it. What you have to the right is NOT what the thing to the left shows. You seemed to have skipped an important logical bit. Also, just use $AA^-1$, rather than an asterisk, as that is the notation for matrix multiplication. ) Since the inverse of $A^{-1}$ is in the group, $A^{-1}$ is as well.
  3. Since $A$ and $B$ are both in $GL(2, \mathbb{Z}_5)$, their inverses must be as well. We know that $AB$ is in $GL(2, \mathbb{Z}_5)$ if it has an inverse in $GL(2, \mathbb{Z}_5)$. We know from linear algebra that $AB^{-1} = B^{-1}A{-1}$. Are you missing parenthesis somewhere to the left? Thus $AB$ and $AB^{-1}$ are in $GL(2, \mathbb{Z}_5)$. You did not show both of these facts, but are claiming to have shown both. Careful.
  4. We know that $A_1A_2 \in GL(2, \mathbb{Z}_5)$. It follows by induction using (3) that $A_1A_2A_3\cdots A_k\in GL(2,\mathbb{Z}_5)$. Please include this induction proof here, or use an alternate proof.
  5. To show that $GL(2, \mathbb{Z}_5)$ is a group, we must show that the group operation (matrix multiplication) is associative, that it is closed, that the identity exists, and that all elements have inverses. We know that matrix multiplication is associative (though not commutative), that it is closed from (3), that the identity exists from (2) (Does 2 show this?), and that all elements have inverses from the definition of $GL(2, \mathbb{Z}_5)$. (Your words above are showing that you are missing some very subtle things. Come by. Let's chat. ) This means that $GL(2, \mathbb{Z}_5)$ is a group.
  6. Everything that I have done should generalize beyond $2\times2$ matrices and $\mathbb{Z}_5$. Note that inversion is more complicated with square matrices greater than $2\times 2$, but not in ways that pose any real problem.
Tags

Change these as needed.

  • Week4 - Which week are you writing this problem for?
  • Christian - Sign your name by just changing "YourName" to your wiki name.
  • NeedsWork
  • When you are ready to submit this written work for grading, add the phrase [[!Submit]] to your page. This will tell me that you have completed the page (it's past rough draft form, and you believe it is in final draft form). Don't type [[!Submit]] on a rough draft.
  • If I put [[!NeedsWork]] on your page, then your job is to review what I've written, address any comments made, and then delete all the comments I made. When you have finished reviewing your work, leave [[!NeedsWork]] on your page and type [[!Submit]]. (Both tags will show up). This tells me you have addressed the comments.
  • I'll mark your work with [[!Complete]] after you have made appropriate revisions.