You will create a Visual C++ program that lets you compute the inverse of a matrix in PSL(2,F), where F is a Galois field, or to multiply two such matrices. Then you will associate a permutation with each such matrix and let the user verify that the group of permutations is isomorphic to the group of matrices. If you are feeling exceedingly ambitious, you can display the two isomorphic groups SL(2,F4) and PSL(2,Z5) at the same time and have a four-way isomorphism.
These instructions will explain how to create the user-interface parts of the program that you may not have seen before. After that, you are on your own. You can reuse your previous code for multiplying permutations and for doing arithmetic in finite fields.
The program used in class that multiplies 2x2 matrices over F4, "SL2F.exe", can be dowloaded from the course Web site lab.dce.harvard.edu/summer/maths15. You can also download a copy of this document, from which you can paste code into your project as you are creating the project.
1. Click the "Microsoft Visual C++ 6.0" icon on the desktop, or go to
Start...Programs...Microsoft
Visual C++ 6.0...Microsoft Visual C++ 6.0 if there is no icon on the
desktop. From the menu select
File...New. Click on the Projects tab, then click on MFC AppWizard(exe).
In the location box,
choose the folder in which you keep your Math S15 projects. As the
project name, type in Iso.
Now click OK to start the AppWizard.
2. In Step 1, select Dialog Based, then click Next.
In Step 2, uncheck About Box and ActiveX Controls.
Change the title to "Isomorphism Demonstration." Click Finish.
3. Go to "Resource View" and click on the + next to Dialog, then
double-click on
IDD_ISO_DIALOG. Click on the text that starts "TODO:...",
then press the Delete key to get
rid of it. Do the same for the Cancel button. With the
OK button highlighted, press the Enter key.
Under the General tab, edit the caption to change it to "Done."
Click the little "x" to finish, then drag
the button down to the lower right-hand corner of the dialog.
4. Now we will change some properties of the entire dialog. Click
anywhere in empty space on the
dialog, then press Enter.
Under the General tab, click Font...and select Courier
New, Size 10. This is a non-proportional font, in which every character
has the same width,
Under the Styles tab, check Minimize box.
Click the little x to close Dialog Properties.
5. In the upper right-hand corner of the dialog, place a group box with
the caption "Galois Field". Inside the group box, place two radio buttons
(icon is a black circle inside a white circle). The top one should
have the ID IDC_F4 and the caption SL(2,F4) and should have the Group property
checked. The second one should have the ID IDC_Z5 caption PSL(2,Z5)
and should have the Group property unchecked.
Using ClassWizard, associate a member variable
int m_nField
with the button IDC_F4, and add handler functions for both buttons.
For the two handler functions, insert the single statement
UpdateData(TRUE);
Set a breakpoint at the end of each function by highlighting the final
right brace and pressing F9. Also, in the right-hand debug box (with
the Watch1 tab), type m_nField under "Name."
Build and run the project right now, using F5 to do this in Debug mode,
and verify that selecting one button unselects the other one and that when
the two handler functions are called the value of m_nField is 0 or 1, depending
on which button was selected.
6. In the upper left-hand corner of the dialog, place a group box, about
2 inches wide and 4 inches deep, with the caption Matrix A. At the upper
left corner of this group box, place a combo box (icon looks like a list
box with something on top of it). Make this half the width of the group
box. Give it the ID IDC_A11. Under styles uncheck Sort and select
Drop List, which means that the only valid strings are the ones are the
ones from the accompanying list box. Click on the dropdown arrow
and increase the height of the box so that it can hold six or seven lines
of text.
With this combo box selected, press Ctrl-C to copy it. Press
Ctrl-V to paste a copy, and drag it to the right side of the top row of
the group box. By accident, the automatically-generated ID IDC_A12
is correct! Adjust the size of the group box so that the two combo boxes
fit neatly. Now copy two more group boxes under the first two to
complete the 2x2 matrix. Change their IDs to IDC_A21 and IDC_A22.
Beneath the two combo boxes, place a button with ID IDC_ADJUST_A and
caption Read and Adjust.
Under the button, place an edit box, large enough to show two lines
of 12 characters, with ID IDC_SHOW_A. Under the Styles tab, check both
Multiline and Read-only. Beneath this, put a static text control "Permutation"
and under that, an edit box with ID IDC_PERMUTATION_A
Using ClassWizard, associate member variables (Category Control, type
CComboBox) named m_comboA11, m_comboA12, m_comboA21, and m_comboA22 with
the four combo boxes. These variables give you access to each combo
box.
For the two edit controls, add member variables
CString m_showA
and
CString m_permutationA
respectively..
Also add a handler for the Read and Adjust button.
7. Now switch to ClassView and right-click on Iso classes. Choose New
Class... from the drop-down menu, and seect Generic Class as the type.
For the name of the class, choose CMatrix2x2. Press OK to create
the class. Right-click on the name of this new class in ClassView
and add the following member variables:
CString m_11;
CString m_12;
CString m_21;
CString m_22;
CFiniteField m_field;
Just above the class declaration in Matrix2x2.h, insert the line
#include "FiniteField.h"
Now, by whatever means you find convenient, copy the files FiniteField.h
and FiniteField.cpp from your GField directory into the Iso directory.
Be sure to copy them, not just move them; otherwise you will not be able
to rebuild the previous project! Then select Project..Add To Project...Files
from the main menu, control-click on the two FiniteField files, and click
OK. From FiniteField.h, delete the line
#include "gfield.h"
(which was never really needed) and build your project. If you
have followed instructions carefully, you should see the class CFiniteField
under Class View.
8. In class CIsoDlg, insert the member variable
CMatrix2x2 m_matrixA;
Then add the following code for OnAdjustA()
void CIsoDlg::OnAdjustA()
{
UpdateData(TRUE);
CString text;
int index11 = m_comboA11.GetCurSel();
m_comboA11.GetLBText(index11,text);
m_matrixA.m_11 = text;
int index12 = m_comboA12.GetCurSel();
m_comboA11.GetLBText(index12,text);
m_matrixA.m_12 = text;
int index21 = m_comboA21.GetCurSel();
m_comboA21.GetLBText(index21,text);
m_matrixA.m_21 = text;
int index22 = m_comboA22.GetCurSel();
m_comboA22.GetLBText(index22,text);
m_matrixA.m_22 = text;
if (m_matrixA.AdjustDeterminant(index11,
index12, index21, index22)) {
m_comboA11.SetCurSel(index11);
m_comboA12.SetCurSel(index12);
m_comboA21.SetCurSel(index21);
m_comboA22.SetCurSel(index22);
m_showA = m_matrixA.EditBoxText();
UpdateData(FALSE);
}
else
AfxMessageBox("The determinant
of the matrix must be [1]. This can be achieved automatically if
you have at least 2 nonzero entries, including one in the top row");
}
In the class CMatrix2x2, add the member function
BOOL AdjustDeterminant(int& index11,
int& index12, int& index21, int& index22)
{
return (Determinant()
== "[1]");
}
The job of this function is to try to adjust the data supplied by the user so that the matrix has determinant [1] and to report whether the effort was successful . It will be part of your job to write an improved version of this function, but the one-line version above does the right thing for test cases where the determinant is already [1].
In the case of Z5 you may in some cases also want to multiply the entire matrix by the additive inverse of [1] so that it becomes the standard representative of its equivalence class. A reasonable criterion for "standard" is that the first nonzero entry should be [1] or [2] in the case of Z5. If you do not do this you will end up with a homomorphism of SL(2,Z5) onto A5, which is also OK.
9. In the class CMatrix2x2 add the following code for the Determinant() function.
CString CMatrix2x2::Determinant()
{
return m_field.Subtract(m_field.Multiply(m_11,m_22),
m_field.Multiply(m_12,m_21));
}
Notice that the CMatrix2x2 class works for any field that has functions
like Add() and Multiply(). When you add functions to it, preserve
this desirable property. Then adding new fields to the project will
be almost trivial.
10. Add the following functions to the class CMatrix2x2. These
format a matrix so that it can be displayed in an edit control.
CString CMatrix2x2::Extend(CString
s, int size)
{
while (s.GetLength() < size)
s += " ";
return s;
}
CString CMatrix2x2::EditBoxText()
{
return Extend(m_11) + m_12 +
"\r\n" + Extend(m_21) + m_22;
}
11. Add the following function to the class CIsoDlg. This puts the correct strings for the chosen Galois field into a combo box.
void CIsoDlg::FillComboBox(CComboBox
&box, CMatrix2x2& m)
{
box.ResetContent();
for (int i = 0; i < m.m_field.m_strElements.GetSize();
i++){
box.AddString(m.m_field.m_strElements.GetAt(i));
}
box.SetCurSel(0);
}
12. Finally you can write the complete handler functions for the radio
buttons, as follows:
void CIsoDlg::OnF4()
{
UpdateData(TRUE);
m_matrixA.m_field.m_prime =
2;
m_matrixA.m_field.m_power =
2;
m_matrixA.m_field.m_strElements.Add("[0]");
m_matrixA.m_field.m_strElements.Add("[1]");
m_matrixA.m_field.m_strElements.Add("[x]");
m_matrixA.m_field.m_strElements.Add("[x+1]");
FillComboBox(m_comboA11,m_matrixA);
FillComboBox(m_comboA12,m_matrixA);
FillComboBox(m_comboA21,m_matrixA);
FillComboBox(m_comboA22,m_matrixA);
}
void CIsoDlg::OnZ5()
{
UpdateData(TRUE);
m_matrixA.m_field.m_prime =
5;
m_matrixA.m_field.m_power =
1;
m_matrixA.m_field.m_strElements.Add("[0]");
m_matrixA.m_field.m_strElements.Add("[1]");
m_matrixA.m_field.m_strElements.Add("[2]");
m_matrixA.m_field.m_strElements.Add("[3]");
m_matrixA.m_field.m_strElements.Add("[4]");
FillComboBox(m_comboA11,m_matrixA);
FillComboBox(m_comboA12,m_matrixA);
FillComboBox(m_comboA21,m_matrixA);
FillComboBox(m_comboA22,m_matrixA);
}
13. At this point you can build and run the project. For either field, if you type in a matrix whose determinant is [1], you should see it nicely displayed in the two-line edit control. Otherwise you will see a message box complaining that the determinant is not [1].
14. From this point you are on your own! Here are some features
that you might include:
For 6 points, compute the action of Matrix A on each of the lines in
the 2x2 vector space over the field and thereby associate a permutation
with the matrix. You can determine the lines from the CStringArray in the
CFiniteField: let the first one be ([1] [0]) and the others be ( [0] [1]),
([1], [1]), ([1],[x]) etc. This is slightly different from the numbering
that was done in class, bt it is more systematic. A function like
int CMatrix2x2.ActOnLine(int i)
will be all that you need. The code to convert the results of
this function into the cycle representation of the permutation is something
that you wrote for project 1.
For 7 points, improve AdjustDeterminant() so that it will fix one of the entries in the matrix to make the determinant [1].
For 8 points, have the AdjustA() function also report the order of the matrix in an edit box.
For 9 points, add a second matrix B and compute the product AB and the product of the corresponding permutations. You can copy the code that multiplies permutations from project 1.
For 10 points, add Z7 as an additional choice for the Galois field. This may be very easy!
For 11 points, make it possible for the user to type in the permutation instead of the matrix. This presents an interesting mathematical problem, since the permutation only tells you a vector proportional to the result of a matrix acting on a given vector.
For 12 points, add F8 .The permutations now involve nine lines, and you have reached the limit of what you can do with the symbols 1 through 9.
For 14 points, have a matrix from PSL(2,Z5) display the isomorphic matrix
from SL(2,F4) and both a six-element and a five-element permutation.
One algorithm for doing this is to convert the matrix to a permutation,
then to a rotation of a dodecadron with colored faces, then see what permutation
of five sets of colored edges arises and convert that permutation to a
matrix. However, that approach seems hard to implement in C++.
This is definitely for extra-extra credit!