Mathematics 152
Project 3
A PHP Program for Group Isomorphisms
Last Modified: September 8, 2004
The initial design of this
project was done by Carli Collins and Zoltan Feledy, Harvard Extension
School graduate
students.
This project assumes that you have experience at programming in some
language: C, C++, Basic, Java, Perl, JavaScript .... and that you
have done projects 1 and 2. You will
learn more PHP and HTML as
you go.
If you are not interested in user interfaces, you can do just the
second part of the project for 10 points credit. The entire project is
worth 20 points, but the third part is tricky.
I. Create the User Interface
1.
Open
HapEdit. From the toolbar, choose Folders, and click on the icon for
the
project in which you did the permutation program. I will refer to it as
M152Bamberg, but your version should include your own name.
2.
Right click on the window with the file icons, and
select New...PHP Page. Save
this page as C:\EasyPHP\www\M152Bamberg\
iso.php.
3.
Change the title tag of your document to
Isomorphism Demonstration
by <Your Name>, for example
<title> Isomorphism
Demonstration by
Paul Bamberg</title>
Here
is a plan for laying out the Web page as tables nested within
tables. One table will contain tabs that allow the user
to select a
group of matrices over a finite field. A second table will allow
the
user to select two matrices, then push a "calculate"
button to get the answer. A third table will display the two
matrices, their product, and the permutation corresponding to
each
matrix.
4.
Starting the first table:
a. Put your cursor just above the
closing </body> tag, and
select Actions...Table...Insert Table… from the menu. On the
General tab set Width to 100%. On the
Frame tab set border, spacing, and margin all to 0. On the Alignment
tab set Horizontal alignment to center. Click OK.
b. Put your cursor between the <table></table>
tags, then select Actions...Table...Insert Cells… from the menu. On the
General tab set Width to -1. Select
the Cell tab and input 1 into # of cells and 2 into #
of lines.
c. The top row is just to hold a nice-looking title. Change the
opening tag to
<tr class =
"title">
so that you can later apply a style. Download the file logo.jpg
from the course Web site (under PHP programs) or from the PHP Setup CD,
and copy it into the same
directory as iso.php.
d. In the only cell of the top row, denoted
by a <td></td> tag,
insert an image tag by selecting Actions... Image...Insert image. For
Alignment,
select middle from the dropdown list
and click OK. Now edit the cell so that after the image tag it reads
Harvard University | Mathematics 152 </td>.
Press F9 to run the PHP script and see the image.
6. Inserting a form:
- Place the cursor between the
<td> and </td> tags in the second row, and
Select Actions...Form...Insert Form from the
menu
- Name the form calculation,
set the action to iso.php
and leave the Method as Post. Click OK. The
effect of the action will be, when the user clicks a button, to submit
the data that has been entered back to this PHP file for processing.
7.
Creating the first table within the form.
a. Put your cursor between the form tags, and select
Actions...Table...Insert Table… from the menu. On the General tab set
Width
to 100%.On the
Frame tab set border to 0, spacing and margin to 3. Set the alignment
to
(Default). Click OK.
b.
Put your cursor between the <table></table>
tags, then select Actions...Table...Insert Cells… from the menu. On the
General tab set Width to -1. Select
the Cell tab and input 1 into # of cells and 3
into #
of lines. Select the Alignment tab and choose (Default)
horizontal
alignment. Click OK to create the cells.
c. Change the cell in the first row to read
<td
class="heading">The
Isomorphism between Permutation Groups and Matrices over Finite
Fields</td>
d. Change the cell in the second row to read
<td
class="note">Choose one of
the following groups of matrices over finite fields</td>
e. The cell in the third row will contain tabs with links, as in the
first project. Place the
cursor in the position for this cell
and
choose Actions...Link...Create link from the menu. For Page,
select iso.php from the dropdown list
and click OK. Under Advanced, enter tab as the class. Now edit
the link so that it reads
<a class = "tab" href =
"iso.php?order=4">SL(2,F4)</a>.
Press F9 to make sure that the tab
looks OK. Then insert two more tabs into the same cell, one with
order=5 and text SL(2,Z5) and one with order=7 and text SL(2,Z7). Press
F9 to make sure that row of tabs looks OK.
f. Place the cursor under the closing tag for the table and select
Actions...More Actions...Add horizontal line… from the menu.
8.
Creating the second table within the form.
a. Put your cursor above the
</form> tag, and select
Actions...Table...Insert Table… from the menu. On the General tab set
Width
to 100%.On the
Frame tab set border to 0, spacing and margin to 3. Set the alignment
to
(Default). Click OK.
b.
Put your cursor between the <table></table>
tags, then select Actions...Table...Insert Cells… from the menu. On the
General tab set Width to 30%. Select
the Cell tab and input 3 into # of cells and 2
into #
of lines. Select the Alignment tab and choose (Default)
horizontal
alignment. Click OK to create the cells.
c. The first row consists of headers. Edit the opening tag to read
<tr
class = "heading">.
Then edit the three cells to read
<td
width="30%">Build Matrix
A</td>
<td width="30%">Build Matrix B</td>
<td width="40%">One vector from each subspace</td>
Press F9 to make sure that the headings look OK. Everything will
look much better once you apply styles, of course.
d. In the first cell of the second row will be two dropdowns for
selecting the two rows of matrix A. Edit the first cell to have a
width of 17%. Place the cursor between the <td> tags, then select
Actions... Form... Insert options list from the menu. Choose Atop
as the name. The options will have to be filled in by PHP, but
put in x | x+1 as a placeholder for now. Click OK. Type
<br> after the
closing select tag, then insert another options list with name ABottom,
and put in 0 | x+1 as a placeholder for now.. Edit the width of
the second cell to be 20%, then
insert another pair of option lists, with names Btop and BBottom
respectively. The same placeholders will be fine.
e. In the third cell of the second row will a list of vectors, one fro
each subspace. Edit the width to 32%, place the cursor between the
<td> tags, and choose Actions... Form... Insert textarea from the
menu. Type in "vectorlist" as the name and provide the value ( 1
0) as a placeholder. Press F9 to make sure that the second row looks OK.
f. Place the cursor under the closing tag for the table and select
Actions...More Actions...Add horizontal line… from the menu.
9.
Creating the third table within the form.
a. Put your cursor above the </form>
tag, and select
Actions...Table...Insert Table… from the menu. On the General tab set
Width
to 100%. On the
Frame tab set border to 0, spacing and margin to 3. Set the alignment
to
(Default). Click OK.
b.
Put your cursor between the <table></table>
tags, then select Actions... Table...Insert Cells… from the menu. On
the
General tab set Width to 33%. Select
the Cell tab and input 3 into # of cells and 6
into #
of lines. Select the Alignment tab and choose (Default)
horizontal
alignment. Click OK to create the cells.
c. The first row again consists of headers. Edit the opening tag
to read
<tr class = "subheading">.
Then edit the three cells to read
<td
width="33%">Matrix
A</td>
<td width="33%">Matrix B</td>
<td width="33%">Matrix AB</td>
Press F9 to make sure that these headings look OK. Again,
everything will look much better once you apply styles.
d. The second row contains matrices, which will require a table within
each cell. The actual entries will have to be supplied by PHP,
but we can use "1" as a placeholder. Put your cursor between the
<td> tags for the first cell, and select
Actions...Table...Insert Table… from the menu. On the General tab set
Width
to -1. On the
Frame tab set border to 0, spacing and margin to 3. Set the alignment
to
(Default). Click OK. Put your cursor between the <table></table>
tags, then select Actions...Table...Insert Cells… from the menu. On the
General tab set Width to 10 pixels. Select
the Cell tab and input 4 into # of cells and 1
into #
of lines. Select the Alignment tab and choose (Default)
horizontal
alignment. Click OK to create the cells.
e. Edit the four cells that you just created to contain the following:
<td
class="matrixBrace"
width="10">[</td>
<td class="output" width="21">1<br>1</td>
<td class="output" width="15">1<br>1</td>
<td class="matrixBrace" width="56">]</td>
f. Make the next two cells in the second row be exactly the same
as the first. Later it will be the job of PHP to fill in the
entries for the correct matrices. Press F9 to see the the matrices look
OK.
g. The last four rows of the table contain the order of each matrix and
the permutation associated with each. Eventually PHP will fill in the
order and permutation correctly, but for the moment we just use
placeholders. Edit the last four rows to look like this.
<tr
class="subheading">
<td >Order</td>
<td >Order</td>
<td >Order</td>
</tr>
<tr class="output">
<td >3</td>
<td >3</td>
<td >3</td>
</tr>
<tr class="subheading">
<td>Permutation</td>
<td>Permutation</td>
<td>Permutation</td>
</tr>
<tr class="output">
<td>(36)(34)</td>
<td>(12)(45)</td>
<td>(12)(36)</td>
</tr>
Press F9 to see the completed user interface, without styles.
10.
Creating and inserting the style sheet
Edit the file Math152.css by appending the following style definitions::
/* Body
tag */
BODY {
margin: 15px 5px
5px 5px;
background-color: #E4E4E4;
}
/* Page Title
*/
.title {
color: #000000;
font-family:
sans-serif;
font-size: 18px;
font-weight: bold;
padding-left: 5px;
}
/* Headings */
.heading {
color: #8B0000;
font-family:
sans-serif;
font-size: 14px;
font-weight: bold;
}
/* Sub
Headings */
.subheading {
color: #8B0000;
font-family:
sans-serif;
font-size: 12px;
font-weight: bold;
}
/* Matrix
brace [ or ] */
.matrixBrace {
color: #00008B;
font-size: 30px;
font-family:
sans-serif;
font-weight: normal;
line-height:
1.30556;
}
/* Output of
permutations, orders,
matrices */
.output {
color: #00008B;
font-family:
sans-serif;
font-size: 11px;
font-weight: bold;
text-align: left;
}
/* Notes */
.note {
color: #000000;
font-family:
sans-serif;
font-size: 12px;
font-weight: normal;
text-align: left;
}
In
iso.php, place
the cursor just above the closing </head> tag. From the main
menu, choose Actions...Page...Insert CSS... and choose the file
math152.css. Press F9 to see the dramatically improved appearance of
the
output. You can play with the values, colors and fonts and fonts
in math152.css to achieve a different look.
II. Implement the Mathematics
11. To avoid difficulties in debugging PHP, it is best to continue by
implementing all the mathematics in a standalone test program.
Create a new php file named testiso.php with the following contents:
<?php
include_once("FiniteField.php");
include_once("matrixclass.php");
echo "Testing <br>";
$field = MakeField(4);
$v= new vector("x","x+1",$field);
$m= new
matrix("x","x+1","1","0",$field);
$mv= $m->transformVector($v);
echo $mv->toString();
?>
This will create a vector and a matrix, let the matrix act on the
vector, and print out the result. You can then modify it to test
new functions as you add them.
12. Create a new file named matrixclass.php to define classes for
vectors and matrices. Here is a definition for the vector
class. A vector has two components, strings $v1 and $v2, and a
field $F that specifies how to interpret these strings. The
constructor function, named vector(), builds a vector out of specified
values.
The function toString() converts the vector into a string suitable for
display in a dropdown list Eventually you will need functions that act
on vectors, but this will do for a start.
<?php
include_once("FiniteField.php");
class vector {
var $v1;
var $v2;
var $F;
function vector($v1, $v2,
$field) {
$this->v1 = $v1;
$this->v2 = $v2;
$this->F =
$field;
}
function toString() {
return
$this->v1." | ".$this->v2;
}
}
function vectorFromString($str,$field) {
$components = explode("|",$str);
$v1 = trim($components[0]);
$v2 = trim($components[1]);
return new vector($v1,$v2,$field);
}
?>
Notice that the last function, which creates a vector from a string
like " 1 | x+1 ", is not a member of the vector class.
13. Now add to matrixclass.php a rudimentary definition for the matrix
class. A
matrix has four entries, strings
$a11, $a12, $a21 and $a22, and a field $F that specifies how to
interpret these strings. The constructor function, named matrix(),
builds a matrix out of
specified values. The function transformVector() acts on a vector to
produce a new vector. Eventually you will need more matrix functions,
but this will do for a start.
class matrix {
var
$a11;
var
$a12;
var
$a21;
var
$a22;
var $F;
function matrix($a11, $a12,
$a21, $a22, $field) {
$this->a11 =
$a11;
$this->a12 =
$a12;
$this->a21 =
$a21;
$this->a22 =
$a22;
$this->F =
$field;
}
function transformVector($v){
$v1 =
$this->F->Add($this->F->multiply($this->a11,$v->v1),$this->F->multiply($this->a12,$v->v2));
$v2 =
$this->F->Add($this->F->multiply($this->a21,$v->v1),$this->F->multiply($this->a22,$v->v2));
return new
vector($v1, $v2, $this->F);
}
function toString() {
return $this->a11." |
".$this->a12."<br>".$this->a21." | ".$this->a22;
}
}
function
matrixFromRows($top,$bottom,$field) {
$components = explode("|",$top);
$m11 = trim($components[0]);
$m12 = trim($components[1]);
$components = explode("|",$bottom);
$m21 = trim($components[0]);
$m22 = trim($components[1]);
return new matrix($m11,$m12,$m21,$m22,$field);
}
Notice that the last function, which creates a matrix from two strings
like " 1 | x+1 " and " 0 | x ", is not a member of the matrix class.
At this point you can press F9 to execute the file testiso.php.
If you see no output, not even an error message, comment out all the
lines under the first echo and debug them one at a time. Once you see
the output
Testing
1 | x
you are in business.
14. It is your job to add more functions to the vector and matrix
classes so that can you multiply matrices and calculate the permutation
associated with a matrix.
Here are suggested names for functions. You should write them one
at a time and test as you go by modifying testiso.php.
For vectors:
function isZero () //returns TRUE only
for the zero vector
function isEqual ($other) //returns
TRUE if $other is equal to the vector
function isMultiple ($other) //returns
TRUE if $other is a multiple of the vector
function normalize() // returns a
multiple of the vector whose first component is either 1 or 0, and in
the second case it returns (0,1)
function subspaceIndex() // returns a
positive integer that identifies the subspace to which the vector
belongs
This next function is not a member of the vector class, but it
is useful for creating permutations.
function
vectorFromIndex($i,$field) //returns
a vector in the subspace with index $i whose first component is either
0 or 1
You should test carefully that the vector
$v = vectorFromIndex($i,$field);
has the property that
$v->subspaceIndex() == $i;
For matrices:
function det() //returns the
determinant
function isInCenter() //returns TRUE
for the any multiple of the identity matrix.
function multiplyBy($M)
//returns the product $M$this
function order() //returns the order
of the permutation associated with the matrix(use isInCenter())
function Apply($i) //returns the effect of the matrix on the a vector
from the subspace with index $i;
function permutation()
//returns a
string specifying the permutation associated with the matrix
For this last function you will want to reuse some ideas from project
1. It is safest to modify the Multiply function from
permutcalc.php. The major change is that the index in the for
loop is no longer a character but a subspace index, and it ranges only
from
1 up to the number of subspaces.
When you can correctly calculate the product of two matrices and the
permutation associated with a matrix, the mathematical part of the
project is done.
Here is a rudimentary version of testiso.php
<?php
include_once("FiniteField.php");
include_once("matrixclass.php");
echo "Testing
<br>";
$field =
MakeField(4);
$v= new
vector("x","x+1",$field);
$m= new
matrix("x","x+1","1","0",$field);
$mv=
$m->transformVector($v);
echo
$mv->toString()."<br>";
$zeroV = new
vector("0","0",$field);
if
($zeroV->isZero())
echo "OKZero";
if
(!$v->isZero())
echo "OKZero"."<br>";
if
($v->isEqual(new vector("x","x+1",$field)))
echo "OKEqual"."<br>";
if
($v->isMultiple(new vector("x+1","1",$field)))
echo "OKMult"."<br>";
$w =
$v->normalize();
echo
$w->toString()."<br>";
$v1 = new
vector("0","x",$field);
echo
$v1->subspaceIndex(),"<br>";
$v2 = new
vector("x","0",$field);
echo
$v2->subspaceIndex(),"<br>";
$v3 = new
vector("x","1",$field);
echo
$v3->subspaceIndex(),"<br>";
$v4 = new
vector("x","x",$field);
echo
$v4->subspaceIndex(),"<br>";
$v5 = new
vector("x","x+1",$field);
echo
$v5->subspaceIndex(),"<br>";
for ($j=1;
$j<= 5; $j++) {
$vv =
vectorFromIndex($j,$field);
echo
$j, " ", $vv->toString(),"
",$vv->subspaceIndex(), "<br>";
}
echo
$m->toString(), "<br>";
echo
$m->det(), "<br>";
$m2= new
matrix("x","x+1","1","x+1",$field);
echo
$m2->det(), "<br>";
$c = new
matrix("x","0","0","x",$field);
if
($c->isInCenter())
echo "OKCenter","<br>";
echo
$m->order(),"
",$m2->order()," ",$c->order(),"<br>";
echo
$m->Apply(1), "<br>";
echo
$m->Apply(2), "<br>";
echo
$m->Apply(3), "<br>";
echo
$m->Apply(4), "<br>";
echo
$m->Apply(5), "<br>";
echo
$m->permutation(), "<br>";
?>
Here is the output that it produces if things are working
correctly:
Testing
1 | x
OKZeroOKZero
OKEqual
OKMult
1 | x
1
5
4
2
3
1 0 | 1 1
2 1 | 1 2
3 1 | x 3
4 1 | x+1 4
5 1 | 0 5
x | x+1
1 | 0
x+1
x
OKCenter
3 5 1
5
2
3
1
4
(154)
If you plan to submit only the mathematical part of the project, you
will want a more complete test program, but if you are going on to part
III, the simple test should be adequate.
III. Integrate the Mathematics into the User Interface
15. The final task is to integrate the mathematics into the Web
page. This will require you to replace all the placeholders in
iso.php with appropriate php code.
As in project 2, the selected tab tells you which field to use by
setting the value of $_GET['order'], so you should again start the PHP
code with
include_once("FiniteField.php");
include_once("matrixclass.php");
$order
= isset($_GET['order'])?$_GET['order']:4;
$field = MakeField($order);
16. Next you need to check whether any values have been selected
for the rows of the matrices and set default values otherwise
$aTopRow =
isset($_POST['Atop'])?$_POST['Atop']:"1
| 0";
$aBottomRow =
isset($_POST['Abottom'])?$_POST['Abottom']:"";
$bTopRow
= isset($_POST['Btop'])?$_POST['Btop']:"1
| 0";
$bBottomRow =
isset($_POST['Bbottom'])?$_POST['Bbottom']:"";
17. The hardest part is the input of the matrices. You will
want to fill the first row
for matrix A and matrix B with strings made, using the toString()
function, from all the non-zero vectors. Because you are not
using any polynomials with exponents, it is safe to use the displayed
string in the dropdown as a value.
Here is code for filling the dropdown for the first row of matrix A,
which carefully excludes a row of two zeroes..
for ($i=0;
$i< $field->nElements; $i++)
for ($j=0; $j< $field->nElements; $j++) {
$v = new
vector($field->convertPoly($i),$field->convertPoly($j),$field);
$s = $v->toString();
if ($s == "0 | 0")
continue;
if ($aTopRow == $s)
echo '<option
selected>',$s,'</option>';
else
echo
'<option>',$s,'</option>';
}
The same code, with a very minor change, can also be used for
filling the top row of matrix B.
18. After the user has chosen the first row for a matrix, you should
allow only options for the second row that make the
determinant 1. The problem is how to detect that a value has been
selected in the dropdown for the first row. Standard HTML does
not permit this, but you can use a little bit of JavaScript, supported
both by Netscape and by Internet Explorer, that will achieve the
desired effect. What you need to do is to make the selection of
an
item from a top-row dropdown cause the form to be submitted, but with
an
indication that the corresponding bottom-row dropdown needs
to be set correctly.
At the top of the PHP code add the lines
$resetBottom = isset($_GET['reset'])?$_GET['reset']:"";
if ($resetBottom == "a")
$aBottomRow = "";
if ($resetBottom == "b")
$bBottomRow = "";
These can reset the bottom row to empty as an indication that
the bottom-row dropdown needs to be refilled.
Then edit the dropdown for the top row of matrix A to begin
<select
name="Atop" size="1"
onChange="action='iso.php?reset=a&order=<?php echo
$order?>';submit()">
This will set the value both of $_GET['reset'] and of $_GET['order'].
Make the corresponding change for the top row of matrix B.
19. When the time comes to fill the bottom row of matrix a, you must
check each candidate to see whether it leads to a determinant of 1. If
the bottom row needs to be reset, as signaled by an empty string, the
first successful candidate will become the new bottom row. Here
is code for filling the bottom row of matrix a.
for ($i=0; $i< $field->nElements; $i++)
for ($j=0; $j< $field->nElements; $j++) {
$m21 = $field->convertPoly($i);
$m22 = $field->convertPoly($j);
$v = new vector($m21,$m22,$field);
$bottom = $v->toString();
$m = matrixFromRows($aTopRow, $bottom, $field);
if ($m->det() != "1")
continue;
if ($aBottomRow=="")
$aBottomRow= $bottom;
if ($aBottomRow == $bottom)
echo '<option selected>',$bottom,'</option>';
else
echo '<option>',$bottom,'</option>';
}
Then edit the dropdown for thebottom row of matrix A to begin
<select
name="Abottom" size="1" onChange="action='iso.php?order=<?php echo
$order?>';submit()">
This will set the value only of $_GET['order'].
With a few minor changes this will also serve for filling the bottom
row of matrix B.
You can now press F9 and observe that the matrices a and b are
guaranteed to have determinant 1.
20. The cell to the right of the matrix dropdowns should contain a list
with one vector from each subspace so that it will be possible to check
that the permutation associated with each matrix is correct. Here
is PHP code to do this in a textarea.
<textarea name="vectorlist"
rows="5" cols="20"><?php
for ($i = 1; $i <= $field->nElements+1; $i++) {
$v = vectorFromIndex($i,$field);
echo $i,": ( ",$v->v1," ",$v->v2," )\n";
}?></textarea>
20. The final step is to do the calculation. After all the
dropdowns have been processed, you can construct the matrices a and b
and their product with the code
<?php $ma=matrixFromRows($aTopRow,$aBottomRow,$field);
$mb=matrixFromRows($bTopRow,$bBottomRow,$field);
$mab=$mb->multiplyBy($ma);
?>
21. To display the matrices, you only need to replace your
placeholders. Here, for example, is what is needed for the left
column of matrix a.
<?php echo $ma->a11."<br>".$ma->a21;?>
Once you have replaced the placeholders for six columns, press
F9 to test.
22. As a precaution, you want to calculate and display orders and
permutations only for matrices whose determinant is 1. Here are
appropriate lines, for example, for matrix a.
<td ><?php if ($ma->det()== "1")echo $ma->order()
?></td>
<td ><?php if ($ma->det()== "1")echo $ma->permutation()
?></td>
Once you have replaced six placeholders, press F9 to test.
Grading standards:
Just doing the UI (the first part) -- 4 points
Just doing the mathematics (the second part, which can be done
independently of the UI) - 10 points. If you do only this part,
you will need to submit a testiso.php that tests everything.
Integrating the mathematics and the UI - 6 points