{VERSION 5 0 "IBM INTEL NT" "5.0" } {USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0 1 0 0 0 0 1 }{CSTYLE "2D Math" -1 2 "Times" 0 1 0 0 0 0 0 0 2 0 0 0 0 0 0 1 }{CSTYLE "Hyperlink" -1 17 "" 0 1 0 128 128 1 2 0 1 0 0 0 0 0 0 1 }{CSTYLE "2D Comment" 2 18 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 } {CSTYLE "2D Output" 2 20 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 256 "" 0 1 128 0 128 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 257 "" 1 18 128 0 128 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 258 "Tub ular" 1 24 128 0 128 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 259 "" 1 14 128 128 128 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 260 "" 1 18 128 128 128 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 261 "" 1 18 0 0 128 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 262 "" 1 14 0 0 128 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 263 "" 1 14 0 0 128 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE " " -1 264 "" 1 14 128 128 128 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 265 "" 0 1 128 128 128 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 266 "" 1 14 0 0 128 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 267 "" 0 1 0 0 128 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 268 "" 1 18 0 128 128 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 269 "" 1 18 0 128 128 1 0 0 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 270 "" 0 1 0 128 128 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 271 "" 1 14 0 128 128 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 272 "" 1 14 0 128 128 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 273 "" 1 14 0 128 128 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 274 "" 1 14 0 128 128 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 275 "" 1 14 0 128 128 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 276 "" 1 14 0 128 128 1 0 0 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 277 "" 1 14 0 128 128 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 278 "" 1 14 0 128 128 1 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 279 "" 1 14 0 128 128 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 280 "" 1 18 0 128 128 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 281 "" 1 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 282 "" 1 14 0 128 128 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 283 "" 1 18 0 128 128 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 284 "" 1 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 285 "" 1 14 0 128 128 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 286 "" 1 14 0 128 128 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 287 "" 1 14 0 128 128 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 288 "" 1 14 0 128 128 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 289 "" 1 14 0 128 128 1 0 0 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 290 "" 1 14 0 128 128 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 291 "" 1 18 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 292 "" 1 18 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 293 "Tribune" 1 18 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 294 "Submarine" 1 18 192 192 192 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 295 "" 1 14 0 0 128 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 296 "" 1 14 0 128 128 1 0 0 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 297 "" 1 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 298 "" 1 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 299 "" 1 14 0 128 128 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 300 "" 1 14 0 128 128 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 301 "" 1 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 302 "" 1 14 0 128 128 1 0 0 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 303 "" 1 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 304 "" 1 14 0 128 128 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 306 "" 1 14 0 128 128 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 307 "" 1 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 308 "" 1 14 0 128 128 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 309 "" 1 14 0 128 128 1 0 0 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 310 "" 1 14 0 128 128 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 311 "" 1 14 0 128 128 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 312 "" 0 1 0 128 128 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 313 "" 1 14 0 128 128 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 314 "" 1 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 315 "" 1 14 0 128 128 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 316 "" 1 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 317 "" 1 14 0 128 128 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 318 "" 1 14 0 128 128 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 319 "" 1 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 320 "" 1 14 0 128 128 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 321 "" 1 14 0 128 128 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 322 "" 1 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 323 "" 1 14 0 128 128 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 324 "" 1 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 325 "" 1 14 0 128 128 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 326 "" 1 14 0 128 128 1 0 0 0 0 0 0 0 0 0 0 }{PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }1 1 0 0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "Headi ng 1" -1 3 1 {CSTYLE "" -1 -1 "Times" 1 18 0 0 0 1 2 1 2 2 2 2 1 1 1 1 }1 1 0 0 8 4 1 0 1 0 2 2 0 1 }{PSTYLE "Heading 2" -1 4 1 {CSTYLE "" -1 -1 "Times" 1 14 0 0 0 1 2 1 2 2 2 2 1 1 1 1 }1 1 0 0 8 2 1 0 1 0 2 2 0 1 }{PSTYLE "Error" -1 8 1 {CSTYLE "" -1 -1 "Courier" 1 10 255 0 255 1 2 2 2 2 2 1 1 1 3 1 }1 1 0 0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "Maple Output" -1 11 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }3 3 0 0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "Maple Output" -1 12 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }1 3 0 0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "Normal" -1 256 1 {CSTYLE "" -1 -1 "Treasur e" 1 12 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }3 1 0 0 0 0 1 0 1 0 2 2 0 1 } {PSTYLE "Normal" -1 257 1 {CSTYLE "" -1 -1 "Times" 1 14 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }1 1 0 0 0 0 1 0 1 0 2 2 0 1 }} {SECT 0 {PARA 256 "" 0 "" {TEXT -1 0 "" }{TEXT 256 0 "" }{TEXT 257 0 " " }{TEXT 258 13 "Latin Squares" }}{PARA 0 "" 0 "" {TEXT 265 0 "" } {TEXT 259 0 "" }{TEXT 260 12 "Objective: " }}{PARA 0 "" 0 "" {TEXT 264 178 "To test if a given matrix is a latin square, to produce all p ossible latin squares of a given dimension and to investigate the conn ections between latin squares and group theory." }{TEXT 266 79 " \+ \+ " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 267 0 "" }{TEXT 261 15 "Introduction: " }}{PARA 257 "" 0 "" {TEXT 262 162 "An \+ nxn square matrix is a latin square of dimension n if the elements of \+ the matrix are arranged in such a \+ " }}{PARA 0 "" 0 "" {TEXT 263 213 "way that each is present exactly once in each row and each column. The elements of a \+ latin square can be almost anything, including: numbers, letters, symb ols and colored boxes. For this project, the scope will " }}{PARA 0 " " 0 "" {TEXT 295 265 "be limited to the integers from 1...n, where n i s the dimension of the matrix. The following worksheet provides a mea ns for checking whether or not a matrix is a latin square and discusse s methods used to produce latin squares and their connection to group \+ theory." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 3 "" 0 "" {TEXT -1 0 "" }{TEXT 268 11 "Discussion:" }{TEXT -1 0 "" }}{SECT 1 {PARA 4 "" 0 " top" {TEXT 269 30 "Part I: Testing a given matrix" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 270 0 "" }{TEXT 271 342 "The first step of the pr oject consisted of writing a program that tests if an inputted matrix \+ is a latin square. The program simply considers a matrix and returns \+ a true if the matrix is a latin square or a false if it is not. The p rogram tests if the integers (1...n) are all used and if each occurs e xactly once in every row and column. " }}{PARA 0 "" 0 "" {TEXT -1 0 " " }}{PARA 0 "" 0 "" {TEXT 272 12 "The program:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 410 "islatin := \+ proc(A)\n local i, n, v;\n if not type(A, 'matrix(integer, sq uare)') then\n ERROR(`invalid arguments`)\n end if;\n \+ \n n := linalg[rowdim](A); \n\n for v in [linalg[row ](A, 1 .. n), linalg[col](A, 1 .. n)] do \n if convert(v, set ) <> \{seq(i, i = 1 .. n)\} then\n RETURN(false)\n \+ end if;\n end do; \n RETURN(true) \nend proc:" }}} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 273 106 "To use \+ this procedure, a matrix must be inputted first with a name, and then \+ checked using this program. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" } {MPLTEXT 1 0 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 70 "a := mat rix([[1, 2, 3, 4], [2, 3, 4, 1], [3, 4, 1, 2], [4, 1, 2, 3]]);" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"aG-%'matrixG6#7&7&\"\"\"\"\"#\"\"$ \"\"%7&F+F,F-F*7&F,F-F*F+7&F-F*F+F," }}}{PARA 11 "" 1 "" {TEXT -1 0 " " }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "islatin(a);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%%trueG" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 310 65 "Therefore, this is an example of a matrix that is a latin square. " }{TEXT -1 1 "\n" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 274 50 "An example \+ of a matrix that is not a latin square:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 54 "b:= matrix([[4,4,3,3],[4,4,1,1 ],[3,3,1,1],[1,1,4,4]]);" }{TEXT -1 0 "" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"bG-%'matrixG6#7&7&\"\"%F*\"\"$F+7&F*F*\"\"\"F-7&F+F+F-F-7&F- F-F*F*" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "islatin(b);" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#%&falseG" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 275 169 "Matrix(b) above returns a false because every integer f rom 1 to n (here n=4) is not used and each integer is not limited to o nly one appearance in each row and column. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 276 101 "A non-square matrix returns a n error because the dimensions do not fulfill the definition of a lati n " }{TEXT 278 6 "square" }{TEXT 279 1 "." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 34 "c:= matrix([[1, 2, 3],[3, 1, 2]]);" }}{PARA 0 "" 0 "" {TEXT 277 2 " " }{TEXT -1 0 "" }}{PARA 11 " " 1 "" {XPPMATH 20 "6#>%\"cG-%'matrixG6#7$7%\"\"\"\"\"#\"\"$7%F,F*F+" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "islatin(c);" }}{PARA 8 " " 1 "" {TEXT -1 38 "Error, (in islatin) invalid arguments\n" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{PARA 4 "" 0 "" {HYPERLNK 17 "back to top" 1 "" "top" }{TEXT -1 0 "" }}}{SECT 1 {PARA 4 "" 0 "top of section II" {TEXT -1 0 "" }{TEXT 280 45 "Part II: Produ cing all possible latin squares" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 " " }{TEXT 281 0 "" }{TEXT 282 1576 "The second part of the project cons isted of writing a program that produces all possible latin squares of a given dimension, narrowing the vast number of possibilities by fixi ng the first row and column as 1...n in sequential order. As the dime nsion n gets larger, the number of possible latin squares grows rapidl y. Without fixing the first row and column, there is one possible lat in square for n=1, two possibilities for n=2, 12 possibilities for n=3 , 576 possibilities for n=4, 161,280 possibilities for n=5, and so on \+ (http://mathworld.wolfram.com/LatinSquare.html). The code that follow s produces all of the latin squares with the first row and column set \+ as 1...n. The above number of possibilities for each dimension of lat in squares comes from the number of possibilities with the first row a nd column set multiplied by the number of permutations of the rows and columns. Thus, the number of latin squares produced by the following code multiplied by (n!)(n-1!) equals the total number of latin square s possible. Working backwards, this would indicate how many latin squ ares the following code should produce. If n=3 has a total of 12 lati n squares, dividing that by (3!)(2!) would mean that the following pro gram with n=3 would give just one latin square. For n=4, 576/((4!)(3! )) = 4, so the program should produce four latin squares. For n=5, 16 1,280/((5!)(4!)) = 56, so there should be 56 latin squares for the pro gram's result. As you will see, this is true. Thus, the following pr ogram gives all of the latin squares with the first row and column set ." }{TEXT -1 0 "" }{TEXT 296 1 " " }{TEXT 297 0 "" }{TEXT -1 0 "" }}} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" } {TEXT 298 0 "" }{TEXT 299 318 "To make the program less difficult to f ollow, the actual procedure is broken down into smaller procedures. T hus, there are three smaller programs written that are used in the fin al procedure that produces the latin squares. These smaller programs \+ only make sense in the context of the entire code, so here they are:\n " }{TEXT -1 0 "" }{TEXT 300 0 "" }{TEXT -1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 266 "listunion := proc(li)\n local C, i, L, m, set1, set2 , set3;\n L := [];\n m := nops(li);\n for i from 1 to m do \n \+ set1 := convert(L, set);\n set2 := convert(li[i], set);\n set3 := set1 union set2;\n L := convert(set3, list);\n end do;\n retur n L;\nend proc:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 105 "listmin us := proc(list1, list2)\n convert(convert(list1, set) minus convert( list2, set), list);\nend proc:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 468 "lsquare := proc(n, i, j)\n local B, C, d, k, r, x, z;\n B \+ := matrix(n);\n x := linalg[rowdim](B);\n B[i,j] := [seq(k, k= 1..x)];\n B[i,j] := listminus (B[i,j], linalg[row](n, i));\n \+ B[i,j] := listminus (B[i,j], linalg[col](n,j));\n if B[i,j] = [] the n \n return [] \n end if; \n z := nops(B[i,j]);\n \+ C := [seq(matrix(n), t=1..z)];\n for r from 1 to z do\n \+ C[r][i,j] := B[i,j][r]; \n end do;\n return C;\nend pr oc:" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 301 0 "" }{TEXT 302 103 "Here is the complete program that produces the latin squares, using the above three smaller procedures:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 430 "latin := proc(n)\n# n=ro w/column dimension \nlocal C, g, i, j, x, z;\n x := matrix(n,n,0) ; \n for i from 1 to n do x[1,i] := i end do;\n for i from 1 to n do x[i,1] := i end do;\n C := [x];\n for i from 2 to n do\n for j from 2 to n do\n g := [seq(0, k=1..nops(C))];\n for z from 1 to nops(C) do\n g[z] := lsquare(C[z], i, j);\n end do;\n \+ C := listunion(g);\n end do; \n end do;\n return C;\nend pr oc:" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 303 0 "" }{TEXT 304 68 "To produce the latin squares of a certain dimension n, use lat in(n):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "latin(2);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7#-%'matrixG6#7$7$\"\"\"\"\"#7$F*F)" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "latin(3);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7#-%'matrixG6#7%7%\"\"\"\"\"#\"\"$7%F*F+F)7%F+F)F*" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "latin(4);" }}{PARA 11 "" 1 " " {XPPMATH 20 "6#7&-%'matrixG6#7&7&\"\"\"\"\"#\"\"$\"\"%7&F*F)F,F+7&F+ F,F*F)7&F,F+F)F*-F%6#7&F(7&F*F,F)F+7&F+F)F,F*7&F,F+F*F)-F%6#7&F(7&F*F+ F,F)7&F+F,F)F*7&F,F)F*F+-F%6#7&F(F-F:F5" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 306 483 "These are all latin squares because the \+ integers 1...n have all been used, and each integer appears exactly on ce in each row and column. The number of resulting latin squares corr esponding with their dimension matches the predicted results from the \+ opening comments. The above latin squares are all of the possible lat in squares of their given dimension with the first row and column set. There is a problem with finding the latin squares of any dimension g reater than 4, however." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 9 "latin(5);" }}{PARA 8 "" 1 "" {TEXT -1 62 "Error , (in latin) assigning to a long list, please use arrays\n" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 307 0 "" }{TEXT 308 588 "Based on preliminary calculations, this result should consist of 56 distinct l atin squares. However, this is too much data for MAPLE to include in \+ a list, so latin squares of dimension greater than 4 need to have thei r own special provisions made to the latin(n) procedure. This is diff icult to do, so only latin(5) is rewritten here to show that it is pos sible. Anything beyond n=5 is really too big for MAPLE to handle usin g the methods used here with lists. It may be possible or more effici ent to use arrays, but here the scope is limited to the possibilities \+ while using lists. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 " " {TEXT 309 358 "For n=5, the procedure needs to be broken into parts. The first step within this new code uses latin(n) but changes the in dices so the program just produces the possible squares with the first three rows completed. After this is done, new added steps run a loop through each of these possible latin squares individually to fill in \+ the remaining rows. The " }{TEXT -1 0 "" }{TEXT 311 76 "procedure has been renamed latin5 so as not to confuse the two procedures. " }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 762 "la tin5 := proc()\n local C, F, g, i, j, k, n, S, t, x, z;\n # n is the d imension\n n := 5;\n x := matrix(n,n,0); \n for i from 1 to n \+ do x[1,i] := i end do;\n for i from 1 to n do x[i,1] := i end do;\n \+ C := [x];\n for i from 2 to 3 do\n for j from 2 to n do\n g := [seq(0, k=1..nops(C))];\n for k from 1 to nops(C) do\n g[ k] := lsquare(C[k], i, j);\n end do;\n C := listunion(g);\n end do; \n end do;\n S := [];\nfor z from 1 to nops(C) do\n F \+ := [C[z]]: \n for i from 4 to n do\n for j from 2 to n do\n g := [seq(0, k=1..nops(F))];\n for k from 1 to nops(F) do\n \+ g[k] := lsquare(F[k], i, j);\n end do;\n F := listunio n(g);\n end do; \n end do;\n S := [op(S), F];\nend do;\n C := li stunion(S);\nend proc:" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" } {TEXT 312 0 "" }{TEXT 313 302 "To produce all possible latin squares o f dimension 5, use the command latin5(). Because there are going to b e so many latin squares, and because it is important to know how many \+ are actually produced to check this against preliminary calculations, \+ naming the results \"F\" will help for later reference." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "F := latin5();" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%\"FG7Z-%'matrixG6#7'7'\"\"\"\"\"#\"\"$\"\"%\"\"&7'F,F /F+F-F.7'F-F.F,F/F+7'F.F-F/F+F,7'F/F+F.F,F--F'6#7'F*7'F,F/F.F+F-7'F-F+ F/F,F.7'F.F-F+F/F,7'F/F.F,F-F+-F'6#7'F*7'F,F-F/F+F.7'F-F/F.F,F+7'F.F+F ,F/F-7'F/F.F+F-F,-F'6#7'F*7'F,F/F.F-F+7'F-F.F+F/F,7'F.F+F/F,F-7'F/F-F, F+F.-F'6#7'F*F7F17'F.F+F/F-F,7'F/F-F+F,F.-F'6#7'F*7'F,F-F.F/F+F87'F.F/ F,F+F-FA-F'6#7'F*F7F87'F.F-F,F/F+FA-F'6#7'F*FEF8F97'F/F.F,F+F--F'6#7'F *F07'F-F.F/F,F+F@7'F/F-F.F+F,-F'6#7'F*7'F,F+F.F/F-7'F-F.F/F+F,7'F.F/F, F-F+FM-F'6#7'F*F>FFF_oF3-F'6#7'F*F]oFhn7'F.F/F+F-F,FH-F'6#7'F*7'F,F.F/ F-F+7'F-F/F.F+F,F@FM-F'6#7'F*7'F,F.F/F+F-F?F97'F/F+F,F-F.-F'6#7'F*7'F, F+F/F-F.F17'F.F/F+F,F-Fin-F'6#7'F*7'F,F.F+F/F-F[p7'F.F-F/F,F+F`p-F'6#7 'F*Fjo7'F-F+F.F/F,FepFH-F'6#7'F*FQ7'F-F/F,F+F.FL7'F/F.F+F,F--F'6#7'F*7 'F,F-F+F/F.F^oF_oF3-F'6#7'F*F_p7'F-F/F+F,F.FV7'F/F+F.F-F,-F'6#7'F*FjoF [rF@Fin-F'6#7'F*FdpF[pFVFcq-F'6#7'F*FdpFFFR7'F/F-F.F,F+-F'6#7'F*F>F1Ff oF3-F'6#7'F*FjoF^qFRFM-F'6#7'F*FjoFbqF9F3-F'6#7'F*F7FFFjpF`p-F'6#7'F*F ]oF[rF2F:-F'6#7'F*F>F1FepF\\r-F'6#7'F*F0F^oF@Ffr-F'6#7'F*F77'F-F+F,F/F .FjpFA-F'6#7'F*F0F^oFVF3-F'6#7'F*FipF?F2F`p-F'6#7'F*F0F^qFjpFZ-F'6#7'F *F7FhnF9F`p-F'6#7'F*FgqF?FLFZ-F'6#7'F*FipF?FLFH-F'6#7'F*FQF[rFLFZ-F'6# 7'F*FQFbqFGFA-F'6#7'F*FipFbqFjpF\\r-F'6#7'F*FgqF[pFGF:-F'6#7'F*FEF^oF@ FM-F'6#7'F*FEF_tF2Fcq-F'6#7'F*FdpF?F9FZ-F'6#7'F*FipFbqFLFfr-F'6#7'F*F_ pF_tFfoFfr-F'6#7'F*FgqFhnFRF\\r-F'6#7'F*F_pF^qF_oFM-F'6#7'F*FQF8FfoFZ- F'6#7'F*F0F1FGFin-F'6#7'F*FQF^oFepF`p-F'6#7'F*FipF8F_oFin-F'6#7'F*F>F^ qF_oFcq-F'6#7'F*F]oFbqFjpFA-F'6#7'F*F>F^qFepF:-F'6#7'F*FjoF_tFepFin" } }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 314 0 "" }{TEXT 315 183 "To avoid having to count how many possibilities there are by hand, us e the nops() function which gives the number of elements in a list. B ased on earlier results, there should be 56." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "nops(F);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"#c " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 316 0 "" }{TEXT 317 210 "This shows that thi s program, although it had to be altered to work with the large number of latin squares for dimension 5, does give all possible latin square s of dimension 5 with the first row and column set." }}}{PARA 0 "" 0 " " {TEXT -1 0 "" }}{PARA 257 "" 0 "" {HYPERLNK 17 "back to top" 1 "" "t op of section II" }{TEXT -1 0 "" }}}{SECT 1 {PARA 4 "" 0 "top of secti on III" {TEXT 283 40 "Part III: Latin squares and group theory" }} {PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 284 0 "" }{TEXT 285 462 "Cayley t ables are a huge part of group theory. These tables represent the ele ments of a group and display the solutions of the operations placed up on the group. Cayley tables, interestingly enough, have the same prop erties of latin squares insofar as each element must be used and occur s exactly once in each row and column. Actually, all Cayley tables ar e latin squares. The question then arises: what is the relationship b etween latin squares and groups? " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT 287 649 "Because every group can be written as a Cayley table, and all Cayley tables are latin squares, it is implied \+ that all groups can be represented by a latin square. However, based \+ on the fact that we know how many groups exist of certain orders and t he fact that there is such a vast number of latin squares, it seems pl ausible that every possible latin square (whether or not distinct) may not represent a different group. This mirrors the same idea in group theory, where isomorphic Cayley tables represent the same group. So \+ some latin squares may represent the same groups as other latin square s, but does every latin square represent a group? " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 318 418 "Take the groups of orde r 3. There is only one, Z3. (There is only one group of any order p \+ where p is prime, namely Zp.) Once again limiting the scope to the la tin squares produced by the previous programs (where the first row and column are set), it is necessary to determine whether or not the lati n square represents a group. In this case, the produced latin square \+ of dimension 3 does represent the group Z3. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 288 549 "Moving t o the groups of order 4 -- there are two: Z4 and Z2xZ2. However, ther e are four distinct latin squares produced by latin(4). Which, if any , represent groups? If they all represent groups, it proves the point that some distinct latin squares represent the same group. If any of them does not represent a group, it proves the point that not all lat in squares represent groups. Upon further inspection, it is evident t hat all of these latin squares represent groups of order 4. One of th em represents Z2xZ2, while the others represent Z4." }}{PARA 0 "" 0 " " {TEXT -1 0 "" }}{PARA 0 "" 0 "" {XPPEDIT 18 0 "matrix([[1, 2, 3, 4], [2, 1, 4, 3], [3, 4, 1, 2], [4, 3, 2, 1]]);" "6#-%'matrixG6#7&7&\"\" \"\"\"#\"\"$\"\"%7&F)F(F+F*7&F*F+F(F)7&F+F*F)F(" }{TEXT -1 1 " " } {TEXT 319 0 "" }{TEXT 320 60 "represents Z2xZ2 because all of the elem ents are of order 2." }}{PARA 0 "" 0 "" {TEXT 321 366 "The other latin squares of dimension 4 have elements of order 4 and order 2, so they \+ represent the cylic group Z4. Again, this investigation is limited to the squares produced with the first row and column set. So, although there may be latin squares of dimension 4 that do not represent group s, the squares tested under these specifications all represent groups. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 289 436 "Gi ven that 5 is prime, there is only one group of order 5, Z5. There ar e 56 possible latin squares of order 5 under these specifications, whi ch all must represent Z5 if they are going to represent a group. It w ould be difficult to go through each one of these possible squares to \+ determine which represent Z5 and which, if any, do not, but it will su ffice to show a few examples to conclude that not all of these squares represent Z5." }}{PARA 0 "" 0 "" {XPPEDIT 18 0 "matrix([[1, 2, 3, 4, \+ 5], [2, 1, 4, 5, 3], [3, 4, 5, 1, 2], [4, 5, 2, 3, 1], [5, 3, 1, 2, 4] ]);" "6#-%'matrixG6#7'7'\"\"\"\"\"#\"\"$\"\"%\"\"&7'F)F(F+F,F*7'F*F+F, F(F)7'F+F,F)F*F(7'F,F*F(F)F+" }{TEXT -1 1 " " }{TEXT 322 0 "" }{TEXT 323 190 "does not represent Z5 because 2 is not of order 5, and all el ements in Zp have to be of order p to be a Cayley table of Zp. Thus, \+ this latin square is not a Cayley table for Z5. Similarly," }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {XPPEDIT 18 0 "matrix([[1, 2 , 3, 4, 5], [2, 3, 5, 1, 4], [3, 4, 1, 5, 2], [4, 5, 2, 3, 1], [5, 1, \+ 4, 2, 3]]);" "6#-%'matrixG6#7'7'\"\"\"\"\"#\"\"$\"\"%\"\"&7'F)F*F,F(F+ 7'F*F+F(F,F)7'F+F,F)F*F(7'F,F(F+F)F*" }{TEXT -1 1 " " }{TEXT 324 0 "" }{TEXT 325 56 "does not represent Z5 because 3 does not have order 5. \+ " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 326 235 "Th ese examples prove that not all latin squares actually correspond to g roups. However, it is true that all groups have a latin square, for t hey all can be represented by at least one Cayley table, which are by \+ nature latin squares. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 290 118 "Therefore, all groups can be repres ented by latin squares, but not all latin squares represent their own \+ unique group." }}{PARA 0 "" 0 "" {TEXT 286 1 " " }}{PARA 257 "" 0 "" {HYPERLNK 17 "back to top" 1 "" "top of section III" }{TEXT -1 0 "" }} }{PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 291 0 "" }{TEXT -1 0 "" }{TEXT 292 0 "" }{TEXT 293 0 "" }}{PARA 0 "" 0 "" {TEXT 294 23 "created by: J amie Woods" }{TEXT -1 0 "" }}}{MARK "11" 0 }{VIEWOPTS 1 1 0 1 1 1803 1 1 1 1 }{PAGENUMBERS 0 1 2 33 1 1 }