20131106

Please Login to access more options.

Today

Problem (Continue Working On Open Problems)

Please look at the Open Problems list, and continue working on these. In your preparation, please tell me which of the problems on the list you would feel comfortable presenting to the class. When we have a critical mass of students ready to present each problems, we'll discuss it in class (sometimes with a presentation, sometimes with just a discussion).

Problem 69 (Cayley Tables And Isomorophisms On A Group Of Order 4)

In the problem Orders Of $\mathbb{Z}_n$ And $U(n)$ And Their Elements we computed the orders of $U(n)$ of $n$ from 2 to 10. The groups $U(5)$, $U(8)$, and $U(10)$ all have order 4 (they have four elements). For $U(5)$, we can construct a multiplication table (called a Cayley table) that represents the binary operation of the group. We create this table exactly as we created the times tables in grade school, where we put the product $ab$ in the row corresponding to $a$ and the column corresponding to $b$. The table for $U(5)$ is shown below. $$\begin{array}{c|cccc} \cdot \text{ mod } 5 & 1&2&3&4 \\ \hline\hline 1 & 1&2&3&4 \\ 2 & 2&4&1&3 \\ 3 & 3&1&4&2 \\ 4 & 4&3&2&1 \\ \end{array}$$

1. Construct a multiplication table, i.e. Cayley table, for $U(8)$ and $U(10)$. Which of these groups is isomorphic to $U(5)$?
2. Let $G = \{a,b,c,d\}$ and $H=\{r,s,t,u\}$ and define the operation $*$ on $G$ in the table on the left below, and the operation $\times$ on $H$ by the table on the right below. $$ \begin{array}{c|cccc} * & a&b&c&d \\ \hline\hline a & a&b&c&d \\ b & b&d&a&c \\ c & c&a&d&b \\ d & d&c&b&a \\ \end{array} \quad\quad\quad \begin{array}{c|cccc} \times & r&s&t&u \\ \hline\hline r & t&u&r&s \\ s & u&t&s&r \\ t & r&s&t&u \\ u & s&r&u&t \\ \end{array}.$$ For each group, which element is the identity element? Which group is isomorphic to $U(8)$?
3. Let $K=\{1,-1,i,-i\}$, which is a subset of the complex numbers (recall that $i=\sqrt{-1}$ and $i^2=-1$). Construct a multiplication table for $K$, and show that $K$ is isomorphic to one of the groups above.

To show that two groups are isomorphic, we must show that there is a bijection between them that preserves the group structures. In linear algebra, we encounter maps that preserve the group structure, but are not necessarily bijections. We called such maps linear transformations in linear algebra. In a general group setting, we call these maps homomorphisms. Here's a formal definition.

Definition (Group Homomorphism)

Let $(G,\cdot)$ and $(H,\times)$ be groups. We say that the function $f:G\to H$ is a group $\textdef{homomorphism}$ if $f$ preserves the group structures, which means $f(a\cdot b)=f(a)\times f(b)$ for every $a,b\in G$.

When we want to know if a matrix is invertible, or serves as a valid encryption key, we can discover this by computing the determinant. If the determinant of the matrix is non zero, has a multiplicative inverse, then we can invert this matrix. We shows this was true as well even when working with matrix encryption mod $n$.

Problem 70 (The Determinant Map Is A Homomorphism)

Let $n$ be an integer greater than 1, and consider the general linear group $\text{GL}(2,\mathbb{Z}_n)$ of two by two invertible matrices mod $n$. Let $f$ be the determinant map $f:\text{GL}(2,\mathbb{Z}_n)\to U(n)$ defined by $f(A)=\det A$, i.e. defined by $$f\left(\begin{bmatrix}a&b\\c&d\end{bmatrix}\right)= (ad-bc)\pmod n.$$ Show that $f$ is a homomorphism. Prove this result by direct computation, rather than by claiming it was already shown to be true in a previous course.

The set of matrices that have determinant one is a special group of matrices. We can use this group of matrices to learn quite a bit about all matrices. Here's a formal definition.

Definition (Special Linear Group $\text{SL}(m,\mathbb{Z}_n)$)

We have already defined the general linear group $\text{GL}(m,\mathbb{Z}_n)$ to be the set of $m$ by $m$ invertible matrices with coefficients in $\mathbb{Z}_n$, together with the binary operation of matrix multiplication mod $n$. The set of matrices in $\text{GL}(m,\mathbb{Z}_n)$ that have determinant 1 is called the special linear group, and we write $$\text{SL}(m,\mathbb{Z}_n)=\left\{ a\in \text{GL}(m,\mathbb{Z}_n) \mid \det(a)=1 \right\}.$$

Problem 71 (The Special Linear Group Is A Subgroup Of The General Linear Group)

Prove that $\text{SL}(m,\mathbb{Z}_n)$ is a subgroup of $\text{GL}(m,\mathbb{Z}_n)$. Why is the set of matrices whose determinant equals 2 not a subgroup of the general linear group?

Given $m,n\geq 2$, how many elements are in $GL(2,\mathbb{Z}_n)$? In other words, how many different matrix encryption keys are there, given the size of the matrix and what coefficients we'll allow. This is a nontrivial problem, but its answer is provides a key to knowing how to decrypt a message by brute force. We'll find that knowing something about the special linear groups will help us answer this question. First, let's make an observation that should simplify some computations if we assume that $n$ is prime.

Exercise (The Order Of $U(p)$ When $p$ Is Prime)

If $p$ is a prime, then what is the order of $U(p)$? In other words, what is the Euler $\varphi$ function at $p$, namely what is $\varphi(p)$.

Problem 74 (Conjecturing The Order Of General Linear Groups)

Let's focus on 2 by 2 matrices with entries in $\mathbb{Z}_p$ where $p$ is a prime. So we let $p$ be a prime and consider $G = \text{GL}(2,\mathbb{Z}_p)$.

1. Here is a list of all 81 of the 2 by 2 matrices with entries in $\mathbb{Z}_3$. Underneath that list you'll see the determinant of each matrix has already been computed for you. How many matrices have determinant 1, in other words how many matrices are in $\text{SL}(2,\mathbb{Z}_3)$. How many matrices are invertible, i.e. how many matrices are in $\text{GL}(2,\mathbb{Z}_3)$? What patterns did you use to help you count?

   • n=3
     matrices=[];
     for i in [0..n-1]:
      for j in [0..n-1]:
       tempmatrices=[]
       for k in [0..n-1]:
        for l in [0..n-1]:
         tempmatrices.append(matrix(2,2,[i,j,k,l]))
       matrices.append(tempmatrices)
     show(table(matrices))
     
     dets=[];
     for i in [0..n-1]:
      for j in [0..n-1]:
       tempdets=[]
       for k in [0..n-1]:
        for l in [0..n-1]:
         tempdets.append(matrix(2,2,[i,j,k,l]).det().mod(n))
       dets.append(tempdets)
     show(table(dets))
     
2. This sage code below repeats the above with $n=5$. Use this to count how many matrices have determinant 1 (are in $\text{SL}(2,\mathbb{Z}_5)$) and then how many are invertible (are in $\text{GL}(2,\mathbb{Z}_5)$). What patterns did you use to help you count?

   • n=5  #Change this number as needed. 
     matrices=[];
     for i in [0..n-1]:
      for j in [0..n-1]:
       tempmatrices=[]
       for k in [0..n-1]:
        for l in [0..n-1]:
         tempmatrices.append(matrix(2,2,[i,j,k,l]))
       matrices.append(tempmatrices)
     #show(table(matrices))  #Uncomment this line (remove the #) if you want to see all the matrices. 
     
     dets=[];
     for i in [0..n-1]:
      for j in [0..n-1]:
       tempdets=[]
       for k in [0..n-1]:
        for l in [0..n-1]:
         tempdets.append(matrix(2,2,[i,j,k,l]).det().mod(n))
       dets.append(tempdets)
     show(table(dets))
     

3. You can modify the sage code above to let $n=7, 11, 13,$ etc. How many matrices are in $\text{SL}(2,\mathbb{Z}_7)$ and $\text{GL}(2,\mathbb{Z}_7)$? What patterns did you use to help you count?
4. If $p$ is a prime, make a conjecture about the order of $\text{SL}(2,\mathbb{Z}_p)$ and the order of $\text{GL}(2,\mathbb{Z}_p)$. You do not have to prove your conjecture.

For more problems, see AllProblems