# Commits

committed 496364c Draft

• Participants
• Parent commits c387f27

# File Algebra.html

 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
 <html xmlns="http://www.w3.org/1999/xhtml">

+<!-- This stuff makes the Sage cell instances work right -->
+    <script src="http://aleph.sagemath.org/static/jquery.min.js"></script>
+    <script src="http://aleph.sagemath.org/embedded_sagecell.js"></script>
+    <script>
+$(function () { + sagecell.makeSagecell({inputLocation: '#Vectors1', + template: sagecell.templates.restricted}); + sagecell.makeSagecell({inputLocation: '#Vectors2', + template: sagecell.templates.restricted}); + sagecell.makeSagecell({inputLocation: '#LAExamples', + template: sagecell.templates.restricted}); + sagecell.makeSagecell({inputLocation: '#VectorSpaces', + template: sagecell.templates.restricted}); + sagecell.makeSagecell({inputLocation: '#SVD', + template: sagecell.templates.restricted}); + sagecell.makeSagecell({inputLocation: '#A5', + template: sagecell.templates.restricted}); + sagecell.makeSagecell({inputLocation: '#polyrings', + template: sagecell.templates.restricted}); + sagecell.makeSagecell({inputLocation: '#modarith1', + template: sagecell.templates.restricted}); + sagecell.makeSagecell({inputLocation: '#modarith2', + template: sagecell.templates.restricted}); + sagecell.makeSagecell({inputLocation: '#primes', + template: sagecell.templates.restricted}); + sagecell.makeSagecell({inputLocation: '#primeplot', + template: sagecell.templates.restricted}); +}); + </script> +  <head>  <title>Algebra, linear and otherwise</title>  <meta name="author" content="Byungchul Cha, Karl-Dieter Crisman, Dan Drake, and Jason Grout" />    <h1>Algebra, linear and otherwise</h1>   -<p>At one time 'higher' algebra may have been seen as blissfully computer-free.  -But today computers are essential for many types of "real" algebra. A typical  -<a href="#Matrices">linear algebra</a> class provides a wealth  +<p>At one time 'higher' algebra may have been seen as blissfully computer-free. +But today computers are essential for many types of "real" algebra. A typical +<a href="#Matrices">linear algebra</a> class provides a wealth  of examples of with image analysis, wavelets, and so on. </p>   -<p>It is also evident in <a href="#NumberTheory">number theory</a>, where anyone can factor hundred-digit  -numbers and where many students want to see examples from cryptography. Perhaps surprisingly, though, <a  -href="#AbstractAlgebra">abstract algebra</a> has also undergone a sea change with the advent of computer  -visualization. The <a href="References.html">PascGalois</a> project and the new textbook <a  -href="References.html">by Nathan Carter</a> are good examples of how algebra can be visualized, and group  -theory has long benefited from this as well. To try the examples out yourself, type them in or use the  +<p>It is also evident in <a href="#NumberTheory">number theory</a>, where anyone can factor hundred-digit +numbers and where many students want to see examples from cryptography. Perhaps surprisingly, though, <a +href="#AbstractAlgebra">abstract algebra</a> has also undergone a sea change with the advent of computer +visualization. The <a href="References.html">PascGalois</a> project and the new textbook <a +href="References.html">by Nathan Carter</a> are good examples of how algebra can be visualized, and group +theory has long benefited from this as well. To try the examples out yourself, type them in or use the  worksheet at #Algebra. FIXME: make sure this works</p>    <h2 id="Matrices">Matrices and Their Friends</h2>    <p>It is easy to create matrices. Here are two ways of creating the same matrix.  <ul> -<li>A = matrix([[1,2,3],[4,5,6]])</li> -<li>B = matrix(2,[1,2,3,4,5,6])</li> +<li><code>A = matrix([[1,2,3],[4,5,6]])</code></li> +<li><code>B = matrix(2,[1,2,3,4,5,6])</code></li>  </ul> -</p> +These will make integer matrices by default; Sage will make appropriate methods available +depending on whether entries are real, complex, rational, etc.</p>    <p>Vectors are built in, and Sage knows what kind of multiplication is appropriate  for vectors and vectors, as well as vectors and matrices. -<ul> -<li>V = vector([1,0,-1])</li> -<li>V*A; V*V</li> -</ul> -Solving matrix equations is quite doable as well; one way to do this is with the backslash,  -which may be familiar from other systems. Here, we'll solve "A^T X = V".  -A.transpose()\V -(-5/3, 2/3) -</p>   -<p>More importantly, Sage can compute all the <em>other</em> things one normally wants in the undergraduate  -curriculum. FIXME: Add the examples here with the commands. +<div id="Vectors1"><script type="text/x-sage">A = matrix([[1,2,3],[4,5,6]]) +V = vector([1,0,-1]) +V*A; V*V</script></div> + +<p>Solving matrix equations is also easy. One way to do this is with the backslash, +which may be familiar from other systems. Here, we'll solve "A^T X = V".</p> + +<div id="Vectors2"><script type="text/x-sage">A = matrix([[1,2,3],[4,5,6]]) +V = vector([1,0,-1]) +A.transpose()\V</script></div> + + +<p>More importantly, Sage can compute all the <em>other</em> things one normally wants in the undergraduate +curriculum, such as:</p>  <ul>  <li>Eigenvalues</li>  <li>Determinants (of square matrices!)</li>  <li>Row-Reduced Echelon Form</li>  </ul> +<div id="LAExamples"><script type="text/x-sage">A = matrix([[1,2,3],[4,5,6],[-1,-2,-3]]) +print A.eigenvalues() +print det(A) +A.rref()</script></div>    <p>It's also very important to be mathematically correct. Sage returns vector spaces and modules -for things like eigenspaces. FIXME: Example.</p> +for things like eigenspaces and kernels.</p> + +<div id="VectorSpaces"><script type="text/x-sage">A = matrix([[1,2,3],[4,5,6],[-1,-2,-3]]) +print A.left_kernel().intersection(A.image()) +A.left_kernel(); A.image()</script></div> + +<p>But if that isn't how you teach linear algebra, there is full support for numerical +methods as well, when appropriate. Here, we specify a base ring for the matrices, because SVD +FIXME: isn't implemented? doesn't make sense? What? +otherwise.</p> + +<div id="SVD"><script type="text/x-sage">A = matrix(RDF,[[1.03,2.1,3.3],[4.0,5.0,6.3],[-1.001,-2.013,-3.2]]) +A.SVD()</script></div> +    <h2 id="AbstractAlgebra">Groups, Rings, and Beyond</h2>   -<p>Many common groups are pre-defined, usually as permutation groups, and  +<p>Abstract algebra is very well supported. +Many common groups are pre-defined, usually as permutation groups, and  every group of order 15 or less is available as a permutation group. Here, we check whether the alternating  group of degree 5 is simple. -<ul> -<li>H = AlternatingGroup(5); H </li> -<li>Alternating group of order 5!/2 as a permutation group</li> -<li>H.is_simple() </li> -<li>True</li> -</ul> -There are also commands for accessing all normal subgroups, stabilizers, and all manner of other  +<div id="A5"><script type="text/x-sage">H = AlternatingGroup(5) +H; H.is_simple()</script></div> + +<p>There are also commands for accessing all normal subgroups, stabilizers, and all manner of other  objects.</p>    <p>We'll use the most basic rings of the form "Z/nZ" <a href="#NumberTheory">below</a>, for number theory. -But there are lots of other rings available, the most important of which are polynomial rings. We can  -use this to talk about a lot of the typical ingredients of undergraduate algebra. -<ul> -<li>R.&lt;x&gt;=QQ[]</li> -<li>R.random_element()</li> -<li>(x^2+x+1).is_irreducible()</li> -<li>I = R.ideal('x^2+x+1');I</li> -<li>Principal ideal (x^2 + x + 1) of Univariate Polynomial Ring in x over Rational Field</li> -<li>Q = R.quotient(I); Q</li> -<li>Univariate Quotient Polynomial Ring in xbar over Rational Field with modulus x^2 + x + 1</li> -</ul> -Some of these topics cause a lot of trouble, so having the ability to verify hand computations easily -may help a lot with comprehension. -</p> +But there are lots of other rings available, the most important of which are polynomial rings. We can +use this to talk about a lot of the typical ingredients of undergraduate algebra. Here's how to create +a univariate polynomial ring over the rationals, and do some things with it.</p>   -<p>FIXME: Anything about fields? Probably no more than that.</p> +<div id="polyrings"><script type="text/x-sage">R.<x>=QQ[] +print R.random_element() +print (x^2+x+1).is_irreducible() +I = R.ideal('x^2+x+1') +Q = R.quotient(I) +I; Q</script></div> + +<p>Some of these topics cause a lot of trouble, so having the ability to verify hand computations easily +may help a lot with comprehension.</p> +    <h2 id="NumberTheory">Number Theory</h2>   -<p>Unsurprisingly, since Sage's origins are in number theoretic computation, Sage has massive  +<p>Unsurprisingly, since Sage's origins are in number theoretic computation, Sage has massive  number-theoretic potential. Here, we'll restrict attention to the most basic functionality.</p>   -<p>The first real computation one does in number theory is often just modular arithmetic. With the  -"mod" command, consistently staying in one modulus is easy. -<ul> -<li>a = mod(2,13)</li> -<li>a^10000000</li> -</ul> -Or one can just create a ring and use that. Here, we verify Fermat's Little Theorem for the prime 13. -<ul> -<li>Zp = Integers(13)</li> -<li>for b in Zp: print b^12</li> -</ul> -</p> +<p>The first real computation one does in number theory is often just modular arithmetic. With the +<code>mod</code> command, consistently staying in one modulus is easy.</p>   -<p>Need an industrial-strength pair of primes to teach RSA? No problem. -<ul> -<li>p = random_prime(200,proof=True)</li> -<li>q = random_prime(200,proof=True)</li> -<li>n = p*q</li> -</ul> -And once you pick an exponent coprime to "phi(n)" as the encryption key,  -you can just get the decryption key in a matter of milliseconds with "mod(e,euler_phi(n))^-1".</p> +<div id="modarith1"><script type="text/x-sage">a = mod(2,13) +a^10000000</script></div>   -<p>Sage also plots a number of useful number-theoretic functions. FIXME: Screenshots or images -<ul> -<li>plot(moebius,10,100)</li> -<li>plot(prime_pi,10,10^4)+plot(Li,10,10^4,color='red')</li> -</ul> -</p> + +<p>Or one can just create a ring and use that. Here, we verify Fermat's Little Theorem for the prime 13.</p> + +<div id="modarith2"><script type="text/x-sage">Zp = Integers(13) +for b in Zp: print b^12</script></div> + +<p>Remember, using the dot and tab will give lots of other things you can do with these numbers.</p> + +<p>What if you need an industrial-strength pair of primes to teach RSA? No problem; Sage has a full +suite of prime functions. Click "Evaluate" a few times to get different primes in this example. +We'll hope that <code>e=19</code> is indeed coprime to "phi(n)" here.</p> + +<div id="primes"><script type="text/x-sage">p = random_prime(10^200,proof=True); q = random_prime(10^200,proof=True) +n = p*q; print "n is "+ str(n) +phi = (p-1)*(q-1) +print "$\phi\$ is "+str(phi)
+if mod(19,phi)==0:
+    print "Oops, try again, we got unlucky"
+else:
+    d = mod(19,phi)^-1
+    print "My decryption key is "+str(d)</script></div>
+
+<p>This may take a few seconds to load, due to proving that <code>p</code> and <code>q</code>
+are, in fact, prime.  Notice that we got the decryption key in a matter of milliseconds with "mod(e,euler_phi(n))^-1".  Well,
+we were lucky that we knew how to factor <code>n</code>!</p>
+
+<p>Sage also plots a number of useful number-theoretic functions.  Here's a little piece of the
+Prime Number Theorem.</p>
+
+<div id="primeplot"><script type="text/x-sage">plot(prime_pi,10,10^4)+plot(Li,10,10^4,color='red')</script></div>
+
+<p>And here is the explicit formula using the zeros of the Riemann zeta function up to about
+height 50 (compare the black and the blue, especially between 90 and 100), with some other good approximations.</p>
+
+<img src="screenshots/PNT.png" />
+
+<p>The sky's the limit with Sage!</p>

 <div class="footer">
 <p>Previous: <a href="DoingCalc.html" class="internal">Doing Calculus</a> | Up: <a href="Mathematics.html" class="internal">Doing Mathematics with Sage</a> | Next: <a href="OtherTopics.html" class="internal">We Got Your Topics Right Here!</a></p>