{VERSION 5 0 "SGI MIPS UNIX" "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 "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 "fixed" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 257 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 258 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 259 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 260 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 } {PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Heading 1" 0 3 1 {CSTYLE "" -1 -1 "" 1 18 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }1 0 0 0 8 4 0 0 0 0 0 0 -1 0 }{PSTYLE "Maple Output" 0 11 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }3 3 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }} {SECT 0 {EXCHG {PARA 3 "" 0 "" {TEXT -1 54 "Maple Summer Workshop 2004 : Maple Programming Tutorial" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 260 53 " Matrices, Gaussian elimination, tables, finite fields" }{TEXT -1 28 " \nMichael Monagan, June 2004." }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 190 "Here is a Maple code for reducing a Matrix A to row Echelon form and \+ outputing the det(A). The input is a Maple matrix, a two dimensional \+ array. Subscripts use the square bracket notation " }{TEXT 256 6 "A[i ,j]" }{TEXT -1 4 " = " }{XPPEDIT 18 0 "A[i,j];" "6#&%\"AG6$%\"iG%\"jG " }{TEXT -1 1 " " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 740 "GE := \+ proc(A::Matrix) local m,n,r,c,d,i,j;\n m,n := LinearAlgebra:-Dimens ions(A);\n if m<>n then error \"input must be square\"; fi;\n r, c,d := 1,1,1;\n while r0 then break; fi;\n od;\n if i> n then c := c+1; next fi; # no pivot\n if i<>r then # interchan ge row i and r\n for j from c to n do A[r,c],A[i,c] := A[i,c ],A[r,c] od;\n d := -d;\n fi;\n for i from r+1 to n do\n for j from c+1 to n do\n A[i,j] : = A[i,j]-A[i,c]/A[r,c]*A[r,j];\n od;\n A[i,c] := 0;\n od;\n r := r+1;\n c := c+1;\n od;\n \+ for i from 1 to n do d := d*A[i,i] od;\n d;\nend: " }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 39 "A := Matrix([[6,3,4],[3,4,5] ,[4,5,7]]);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"AG-%'RTABLEG6%\"*Cd _p#-%'MATRIXG6#7%7%\"\"'\"\"$\"\"%7%F/F0\"\"&7%F0F2\"\"(%'MatrixG" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 6 "GE(A);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"#6" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 2 "A;" } }{PARA 11 "" 1 "" {XPPMATH 20 "6#-%'RTABLEG6%\"*Cd_p#-%'MATRIXG6#7%7% \"\"'\"\"$\"\"%7%\"\"!#\"\"&\"\"#F-7%F0F0#\"#6\"#:%'MatrixG" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 132 "This code works for the field of \+ rational numbers Q. We can decribe this field as follows, as a table \+ of constants and procedures. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 319 "Q := table():\nQ[0] := 0; # the addititive identity\nQ[1] := 1; # the multiplicative identity;\nQ [`+`] := proc(a,b) a+b end: # addition\nQ[`*`] := proc(a,b) a*b end: # multiplication\nQ[`/`] := proc(a,b) a/b end: # division\nQ[`-`] := pr oc(a,b) if nargs=a then -a else a-b fi end:\nQ[Characteristic] := 0; # the characteristic" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>&%\"QG6#\"\"!F '" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>&%\"QG6#\"\"\"F'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>&%\"QG6#%/CharacteristicG\"\"!" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 46 "Now here is a version of Gaussian elimination \+ " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 785 "GE := proc(A::Matrix,F ) local m,n,r,c,d,i,j;\n m,n := LinearAlgebra:-Dimensions(A);\n \+ if m<>n then error \"input must be square\"; fi;\n r,c,d := 1,1,F[1 ];\n while rF[0] then break; fi;\n od;\n if i>n then c \+ := c+1; next fi; # no pivot\n if i<>r then # interchange row i \+ and r\n for j from c to n do A[r,c],A[i,c] := A[i,c],A[r,c] \+ od;\n d := F[`-`](d);\n fi;\n for i from r+1 t o n do\n for j from c+1 to n do \n A[i,j] := F[`-`](A[i,j],F[`*`](F[`/`](A[i,c],A[r,c]),A[r,j]));\n od; \n A[i,c] := F[0];\n od;\n r := r+1;\n \+ c := c+1;\n od;\n for i from 1 to n do d := F[`*`](d,A[i,i]) \+ od;\n d;\nend:\n" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 39 "A : = Matrix([[6,3,4],[3,4,5],[4,5,7]]);" }}{PARA 11 "" 1 "" {XPPMATH 20 " 6#>%\"AG-%'RTABLEG6%\"*!=2?F-%'MATRIXG6#7%7%\"\"'\"\"$\"\"%7%F/F0\"\"& 7%F0F2\"\"(%'MatrixG" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "GE(A ,Q);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"#6" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 2 "A;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-%'RTABLEG6 %\"*!=2?F-%'MATRIXG6#7%7%\"\"'\"\"$\"\"%7%\"\"!#\"\"&\"\"#F-7%F0F0#\"# 6\"#:%'MatrixG" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 88 "Now we will red o this using the field of integers modulo 11 (the deteriminant will be 0)" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 255 "Z11 := table():\nZ1 1[0] := 0:\nZ11[1] := 1:\nZ11[`+`] := proc(a,b) a+b mod 11 end:\nZ11[` *`] := proc(a,b) a*b mod 11 end:\nZ11[`-`] := proc(a,b) if nargs=1 the n -a mod 11 else a-b mod 11 fi end:\nZ11[`/`] := proc(a,b) a/b mod 11 \+ end:\nZ11[Characteristic] := 11:\n" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 39 "A := Matrix([[6,3,4],[3,4,5],[4,5,7]]);" }}{PARA 11 " " 1 "" {XPPMATH 20 "6#>%\"AG-%'RTABLEG6%\"*K$4?F-%'MATRIXG6#7%7%\"\"' \"\"$\"\"%7%F/F0\"\"&7%F0F2\"\"(%'MatrixG" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 10 "GE(A,Z11);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"! " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 2 "A;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-%'RTABLEG6%\"*K$4?F-%'MATRIXG6#7%7%\"\"'\"\"$\"\"%7%\" \"!\"\")F-7%F0F0F0%'MatrixG" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 47 "No w we will do this in a finite field GF(q) of " }{TEXT 257 1 "q" } {TEXT -1 1 "=" }{XPPEDIT 18 0 "p^k;" "6#)%\"pG%\"kG" }{TEXT -1 116 " \+ elements. We specify the field by giving the minimal polnomial which \+ must be an irreducible polynomial of degree " }{TEXT 258 1 "k" }{TEXT -1 9 " over GF(" }{TEXT 259 1 "p" }{TEXT -1 3 "). " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 686 "GaloisField := proc(p::prime,m) local F,x; \n x := indets(m,name);\n \n if nops(x) <> 1 then error \"inv alid minimial poly\" fi;\n x := x[1];\n if not type(m,polynom(in teger,x)) or \n not Irreduc(m) mod p then \n error \"inval id minimal polynomial\" \n fi;\n F[0] := 0;\n F[1] := 1;\n \+ F[Characteristic] := p;\n F[Extension] := m;\n F[`+`] := proc(a ,b) a+b mod p end;\n F[`-`] := proc(a,b) if nargs=1 then -a mod p e lse a-b mod p fi end;\n F[`*`] := proc(a,b) Rem(a*b,m,x) mod p end: \n F[`/`] := proc(a,b) \n if b=0 then error \"inverse does \+ not exist\" fi;\n Gcdex(b,m,x,'s') mod p;\n Rem(a*s,m, x) mod p;\n end;\n F\nend:" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 31 "GF18 := GaloisField(2,x^3+x+1);" }}{PARA 11 "" 1 " " {XPPMATH 20 "6#>%%GF18G%\"FG" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "y := GF18[`/`](1,x);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"yG ,&*$)%\"xG\"\"#\"\"\"F*F*F*" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "GF18[`*`](y,x);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 45 "A := Matrix([[1,x,1],[1,x^2, 1],[0,x,x^2+1]]);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"AG-%'RTABLEG6 %\"*GSrq#-%'MATRIXG6#7%7%\"\"\"%\"xGF.7%F.*$)F/\"\"#F.F.7%\"\"!F/,&F1F .F.F.%'MatrixG" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "GE(A,GF18 );" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,&%\"xG\"\"\"F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 2 "A;" }}{PARA 11 "" 1 "" {XPPMATH 20 " 6#-%'RTABLEG6%\"*GSrq#-%'MATRIXG6#7%7%\"\"\"%\"xGF,7%\"\"!,&*$)F-\"\"# F,F,F-F,F/7%F/F/,&F1F,F,F,%'MatrixG" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{MARK "1 0 1" 1 }{VIEWOPTS 1 1 0 1 1 1803 1 1 1 1 }{PAGENUMBERS 0 1 2 33 1 1 }{RTABLE_HANDLES 269525724 272007180 272009332 270714028 }{RTABLE M7R0 I6RTABLE_SAVE/269525724X,%)anythingG6"6"[gl!"%!!!#*"$"$""'""!F(""$#""&""#F(""%F )#"#6"#:6" } {RTABLE M7R0 I6RTABLE_SAVE/272007180X,%)anythingG6"6"[gl!"%!!!#*"$"$""'""!F(""$#""&""#F(""%F )#"#6"#:6" } {RTABLE M7R0 I6RTABLE_SAVE/272009332X,%)anythingG6"6"[gl!"%!!!#*"$"$""'""!F(""$"")F(""%F)F(6 " } {RTABLE M7R0 I6RTABLE_SAVE/270714028X,%)anythingG6"6"[gl!"%!!!#*"$"$"""""!F(%"xG,&*$F)""#F'F )F'F(F'F(,&F+F'F'F'6" }