tag:blogger.com,1999:blog-73156354614690766582017-07-24T08:32:36.503-07:00Matrix ApplicationsThis blog contains matrix applications that I have found or developed to use in Linear Algebra or Mathematical Modeling. You'll need to know some linear algebra to understand these posts.
These are not in-depth explanations but just a taste to whet your appetite. There will be some errors. Gently point them out, and I'll fix them.Murphy Waggonernoreply@blogger.comBlogger10125tag:blogger.com,1999:blog-7315635461469076658.post-67333084270521285242017-06-03T13:30:00.000-07:002017-06-03T13:30:10.722-07:00Applications: Projects requiring solutions of systems<h3>Solving systems of equations</h3><br /><b>Nodal analysis of circuits</b> - Uses systems of equations to find the current through each loop of a circuit including batteries and resisters. Nodal analysis creates linear equations using Kirchhoff's Laws of junctions and paths. This is a popular project for students who have studied some physics. One value of this project is the ability to create overdetermined, consistent systems of equations, which helps students understand rows of zeros in the RREF form of augmented matrices. This article on <a href="http://mathonweb.com/help/backgd5.htm">Nodal Analysis of Electric Circuits</a> has a clear explanation.<br /><br /><b>Loop analysis of circuits</b> - Uses systems of equations to find the current through each loop of a circuit including batteries and resisters. Loop analysis creates linear equations using Kirchhoff's Laws of loops. Again, a popular project for students who have studied some physics and also has the opportunity for overdetermined, consistent systems. Equivalent in results to nodal analysis, this could be combined or assigned separately. This article on <a href="http://mathonweb.com/help/backgd4.htm">Loop Analysis of Electric Circuits</a> has a clear explanation.<br /><br /><b>Curve fitting</b> - Using systems of equations a student finds the coefficients of a polynomial of degree <i>n</i> - 1 to fit <i>n</i> points. I don't think of this as a juicy application that gives the student an appreciation for how linear algebra is used in the world. Fitting an <i>n-</i>degree polynomial to <i>m</i> points using least squares or other methods is more likely to happen.<br /><br /><br /><br />Murphy Waggonerhttps://plus.google.com/105547390628598253045noreply@blogger.comtag:blogger.com,1999:blog-7315635461469076658.post-41080073859295651412017-06-01T13:10:00.000-07:002017-06-01T13:10:21.797-07:00Applications: Projects using vector spaces<h3>Inner product spaces</h3><br /><b>Curve fitting using least squares</b> - Uses matrix multiplication, inverses, and equations to find coefficients of a curve that fits a set of points. I have three misgivings about curve fitting with least squares: it can be done without any understanding, it is not representative of least squares problems in general, and the various spaces involved confuses the issue. Taking the last point first, the problem involves points in 2D or 3D space, matrices in <i>n</i> x <i>k</i> space where <i>n</i> is the number of points and <i>k</i> the terms of the curve being fit, and coefficients that live in <i>k</i>-space. If we are trying to fit a line, the coefficients are 2D, but that 2D space is not the 2D space of the original points. <br /><br />If a student is assigned this project without have learned about projections, they can do the calculations anyway, since they just require matrix multiplication and solving systems of equations. The process of setting up the matrices does not promote deeper understanding of inner product spaces, and so if the student is going to fit curves, they might as well use Excel, which also doesn't deepen their understanding of linear algebra.<br /><br />Finally, if a student learns least squares in this way, then they have difficulty transferring this concept to the solutions of noisy systems using least squares and don't think of least squares as a method of approximating solutions, but rather of fitting curves.Murphy Waggonerhttps://plus.google.com/105547390628598253045noreply@blogger.comtag:blogger.com,1999:blog-7315635461469076658.post-68402409481238746782017-05-26T12:42:00.000-07:002017-05-26T12:42:01.987-07:00Applications: A list of projects using matrix operations<h3>Matrix Operations</h3>I've just finished teaching Linear Algebra twice since the beginning of the year, and I'll be teaching it again in the fall. It is time that I cleaned up my applications list and updated the project files. Since I am enumerating them, I might as well do it here. Here is part 1 on matrix operations. Others may be added later.<br /><b><br /></b><b>Seriation in archaeology</b> - Uses incident matrices, matrix multiplication and transposition, and the properties of symmetric matrices to determine relative ages of sites with common artifacts. I haven't used this in my classes yet, but there seem to be some good resources available including "Some problems and method in statistical archaeology," David Kendall, <i>World Archaeology</i>, 1969, which is available in JStor. It also appears in Gareth Williams <i>Linear Algebra with Applications.</i><br /><i><br /></i><b>Color manipulation in images</b> - Uses matrix multiplication to alter colors in the RGB scale. <a href="http://graficaobscura.com/matrix/index.html">This article by Paul Haeberli</a> describes the 4x4 matrices needed to modify colors, including offsets. I haven't used this in class yet, but I could see this as a good project to have students work in Mathematica. It also is a companion for transformations in 3D graphics, which also use 4x4 matrices. The ability to use matrix multiplication to add vectors is common to both areas.<br /><br /><b>Image color conversion</b> - Uses matrix multiplication to convert from, say, RGB to YIQ, color models. I haven't used this in class, but it shows up in Gareth Williams <i>Linear Algebra with Applications</i>. <a href="http://www.poynton.com/PDFs/coloureq.pdf">This article by Ford and Roberts</a> describes a bevy of color models, and it seems that only some conversions are linear. Without a way to test whether the color conversion is correct, I don't see this as an interesting project. However, maybe Mathematica can render the other color models.<br /><br /><b>Transformations in 2D graphics</b> - Uses matrix multiplication to apply rigid and non-rigid transformations to images. May or may not use projective coordinates, depending on whether translations are allowed. Resources abound.<br /><br /><b>Projection of 3D images onto the plane</b> - Uses matrix multiplication to project 3D images onto the plane given the coordinates of the image and the location of the viewer. Uses projective coordinates. I use a paper written by Jeanie Mullen, one of my honors students. This project has worked best for students with programming backgrounds.<br /><br /><b>Two-port in an electrical circuit</b> - Uses matrix multiplication to describe the change in voltage and current through a two-port or a series of two-ports. A simple application of Ohm's law that creates two linear equations that can be described using matrix multiplication. The equations relate the input current and voltage to the output current and voltage. This Wikipedia article has a table of many transmission matrices and their effect.<br /><br />Murphy Waggonerhttps://plus.google.com/105547390628598253045noreply@blogger.comtag:blogger.com,1999:blog-7315635461469076658.post-34280174831550866572017-05-24T12:44:00.000-07:002017-05-24T12:44:11.033-07:00Applications: A list of projects using eigenthings<h3>Eigenthings</h3><a href="http://matrixapps.blogspot.com/2010/07/gould-index-matrix-application-to.html">Gould's accessibility index in a network</a> - The process uses a modified adjacency matrix and the components of the eigenvector associated with the dominant eigenvalue. Students find this approachable and adaptable. Applications to historical geography, air traffic.<br /><br /><b>Discrete dynamical systems</b> - Using linear algebra to study discrete dynamical systems comes in several flavors. Here are some projects that students find interesting and that differ from each other enough that they feel they are not repeating someone else's project.<br /><br /><br /><ul><li><i style="font-weight: bold;">Difference equations and the Fibonacci sequence</i> - Using eigenvalues to write the product of the <i>n</i>th power of a diagonalizable matrix and an initial vector allows one to write a closed form for a recursive formula. Matrices of size 2x2 are needed to write the closed form of the <i>n</i>th Fibonacci number, but students can easily move from there to the closed form of 3rd and 4th order difference equations. This project is always chosen by some student even though it is not applied to a real-world situation.</li><li><br /></li></ul>Murphy Waggonerhttps://plus.google.com/105547390628598253045noreply@blogger.comtag:blogger.com,1999:blog-7315635461469076658.post-29475391102049867382017-05-22T12:45:00.000-07:002017-05-22T12:45:08.846-07:00Applications: A list of projects using matrix inverses<h3>Matrix Inverses</h3><br />I separate these projects from those other using matrix operations, because I make a clear distinction between forward and inverse problems in my classes.<br /><br /><b>Cryptography</b> - These projects come in two varieties: using modular arithmetic and not.<br /><br /><ul><li><i style="font-weight: bold;">Matrices with |determinant| = 1</i> - Uses matrix multiplication to encode a matrix and multiplication of the inverse to decode. Any matrix with determinant 1 or -1 will result in an inverse with integer components. Students tend to be drawn to these projects, but sometimes I find it hard to push them further, such as requiring them to create their own encoding matrices, etc. Resources abound.</li><li><i style="font-weight: bold;">Modular arithmetic and row reduction </i>- Uses matrix multiplication in modular arithmetic to encode and decode a message and row reduction in modular arithmetic to find the inverse. This is not that the decoded matrix is read using mod 26, but rather that the matrix operations are done with, say, mod 37. This project requires a little more tenacity on the part of the student, and <a href="http://www.math.uconn.edu/~kconrad/blurbs/ugradnumthy/modarith.pdf">this article by Keith Conrad</a> discusses inverses of matrices under modular arithmetic.</li></ul><br /><br /><br /><br /><br />Murphy Waggonerhttps://plus.google.com/105547390628598253045noreply@blogger.comtag:blogger.com,1999:blog-7315635461469076658.post-42638018890004138712010-07-31T09:15:00.000-07:002010-08-03T07:39:07.040-07:00Interesting property of the inverses of Magic Squares<div style="text-align: left;">I’m a nerd. I freely admit it. Sometimes I see a result in mathematics that I think is fun, even if it is not immediately useful. I intended for this blog to be about applications of linear algebra, and by that I mean useful, if not a little esoteric, applications; applications that are juicy and interesting and have good visuals. Although the abstract applications of linear algebra to theoretical areas of mathematics are useful to someone, they do not have the hands-on feeling that I want. However, the nerd in me finds some abstract ideas sexy enough to include in this blog. The following is one of them. Although there is a connection between this idea and <a href="http://mathforum.org/alejandre/magic.square.html">Magic Squares</a>, which have constant row sums, I don’t see an application right off. If you know of one, please let me know.</div><br /><div></div><strong>Theorem</strong> (already this post looks different than usual ‘cause it has a theorem): <br />If an invertible matrix <em>A</em> had constant row sums of <em>k</em>, then the inverse of <em>A</em> has constant row sums of 1/<em>k</em>.<br /><br /><div></div><strong>Proof</strong> (Oh, no. A proof. Just when this blog looked like it was just fun stuff): <br />Let <em>A</em> be an <em>m</em>-by-<em>m</em> invertible matrix with constant row sums of <em>k</em>. Let <em>B</em> be the inverse of <em>A</em>. Now, <em>AB</em> = <em>I</em> and the diagonal elements of <em>I</em> are all 1. Note that <em>I</em> has a constant row sum of 1. Hmmm. Let<br /><br /><div></div><div class="separator" style="clear: both; text-align: center;"><a href="http://1.bp.blogspot.com/_NQXH6jG7x6w/TFQ0mInS7PI/AAAAAAAAANg/mkDa0_pBG3I/s1600/Row+Sum+1.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" bx="true" src="http://1.bp.blogspot.com/_NQXH6jG7x6w/TFQ0mInS7PI/AAAAAAAAANg/mkDa0_pBG3I/s320/Row+Sum+1.jpg" /></a> (1)</div><div align="left" class="separator" style="clear: both; text-align: center;"></div><div></div><div class="separator" style="clear: both; text-align: left;">be the elements of <em>I</em>. Then</div><div class="separator" style="clear: both; text-align: left;"></div><div></div><div class="separator" style="clear: both; text-align: center;"><a href="http://4.bp.blogspot.com/_NQXH6jG7x6w/TFQ1jYKcmqI/AAAAAAAAANo/lNPBqZ9N6xw/s1600/Row+Sum+2.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" bx="true" src="http://4.bp.blogspot.com/_NQXH6jG7x6w/TFQ1jYKcmqI/AAAAAAAAANo/lNPBqZ9N6xw/s320/Row+Sum+2.jpg" /></a> (2)</div><div class="separator" style="clear: both; text-align: center;"></div><div></div><div class="separator" style="clear: both; text-align: left;">is the sum of the elements of row <em>i</em> of <em>I</em>, and </div><div class="separator" style="clear: both; text-align: left;"></div><div></div><div class="separator" style="clear: both; text-align: center;"><a href="http://4.bp.blogspot.com/_NQXH6jG7x6w/TFQ7VGKJEmI/AAAAAAAAAOA/hTVjFvNWgGg/s1600/Row+Sum+3.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" bx="true" src="http://4.bp.blogspot.com/_NQXH6jG7x6w/TFQ7VGKJEmI/AAAAAAAAAOA/hTVjFvNWgGg/s320/Row+Sum+3.jpg" /></a> (3)</div><div class="separator" style="clear: both; text-align: center;"></div><div></div><div class="separator" style="clear: both; text-align: left;">is the sum of the elements of row <em>n</em> of <em>A</em>. Now, write the elements of a row of <em>I</em> = <em>BA</em> as the sum of products of elements of <em>A</em> and <em>B</em>:</div><div class="separator" style="clear: both; text-align: left;"></div><div></div><div class="separator" style="clear: both; text-align: center;"><a href="http://3.bp.blogspot.com/_NQXH6jG7x6w/TFQ6qbJTY3I/AAAAAAAAAN4/HAZfjbRJJ5o/s1600/Row+Sum+4.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" bx="true" src="http://3.bp.blogspot.com/_NQXH6jG7x6w/TFQ6qbJTY3I/AAAAAAAAAN4/HAZfjbRJJ5o/s320/Row+Sum+4.jpg" /></a> (4)</div><div class="separator" style="clear: both; text-align: center;"></div><div></div><div class="separator" style="clear: both; text-align: left;">Now, we're ready to put this all together.</div><div class="separator" style="clear: both; text-align: left;"></div><div></div><div align="center" class="separator" style="border-bottom: medium none; border-left: medium none; border-right: medium none; border-top: medium none; clear: both; text-align: left;"><a href="http://3.bp.blogspot.com/_NQXH6jG7x6w/TFQ-vaxT2PI/AAAAAAAAAOI/_acUZuFa-5s/s1600/Row+Sum+5.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" bx="true" height="296" src="http://3.bp.blogspot.com/_NQXH6jG7x6w/TFQ-vaxT2PI/AAAAAAAAAOI/_acUZuFa-5s/s400/Row+Sum+5.jpg" width="400" /></a> </div><div></div><div align="center" style="border-bottom: medium none; border-left: medium none; border-right: medium none; border-top: medium none; clear: both; text-align: left;">Thus,</div><div align="center" style="border-bottom: medium none; border-left: medium none; border-right: medium none; border-top: medium none; clear: both; text-align: left;"><br /></div><div align="center" class="separator" style="border-bottom: medium none; border-left: medium none; border-right: medium none; border-top: medium none; clear: both; text-align: left;"><a href="http://4.bp.blogspot.com/_NQXH6jG7x6w/TFQ-8amoOpI/AAAAAAAAAOQ/6seQzlLFLPg/s1600/Row+Sum+6.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" bx="true" src="http://4.bp.blogspot.com/_NQXH6jG7x6w/TFQ-8amoOpI/AAAAAAAAAOQ/6seQzlLFLPg/s320/Row+Sum+6.jpg" /></a> (5)</div><div align="center" style="border-bottom: medium none; border-left: medium none; border-right: medium none; border-top: medium none; clear: both; text-align: left;"><br /></div><div align="center" style="border-bottom: medium none; border-left: medium none; border-right: medium none; border-top: medium none; clear: both; text-align: left;">but the right-hand side of (5) is the sum of row <em>i</em> of <em>B</em>. </div><div align="center" style="border-bottom: medium none; border-left: medium none; border-right: medium none; border-top: medium none; clear: both; text-align: left;"><br /></div><div align="center" style="border-bottom: medium none; border-left: medium none; border-right: medium none; border-top: medium none; clear: both; text-align: left;">It seems like a trick, and in a way it is, but the trick is legit. What we have done is started with the sum of row <em>i</em> of <em>I</em>, written it in terms of the elements of <em>A</em> and <em>B</em>, and then seen that we could factor out the elements of <em>B</em> leaving row sums of <em>A</em>. To help you understand this, carefully write the elements of a general 3-by-3 <em>BA</em> in terms of the elements of <em>B</em> and <em>A</em>. Now, sum one of the rows of <em>BA</em> and rearrange so you can factor out the various elements of <em>B</em>. The sums of the elements of <em>A</em> left will each be a row sum. This wouldn't be a proof in general, but it should help you understand what is happening in that sum-switching step of the proof, and that it works because the elements of a matrix product are sums and then we sum a row of sums, and the terms within these two sums can be conveniently rearranged.</div><div align="center" style="border-bottom: medium none; border-left: medium none; border-right: medium none; border-top: medium none; clear: both; text-align: left;"><br /></div><div align="center" style="border-bottom: medium none; border-left: medium none; border-right: medium none; border-top: medium none; clear: both; text-align: left;"><strong>Questions</strong>: </div><ol><li><br /><div align="center" style="border-bottom: medium none; border-left: medium none; border-right: medium none; border-top: medium none; clear: both; text-align: left;">We started with an invertible <em>A</em> with constant row sum. What if <em>A</em> had constant column sum of <em>k</em> instead of row sum? Will the inverse of <em>A</em> have constant column sum of 1/<em>k</em> as well? How would the proof go for that? This would be a great exercise in working with sums and indices.</div></li><li><br /><div align="center" style="border-bottom: medium none; border-left: medium none; border-right: medium none; border-top: medium none; clear: both; text-align: left;">This proof will not work if the constant row sum is <em>k</em> = 0. Can a matrix have an inverse if <em>k</em> = 0? If <em>k</em> is not zero, are we guaranteed that <em>A</em> is invertible? Can we determine if a magic square is invertible by the row sum alone?</div></li><li><br /><div align="center" style="border-bottom: medium none; border-left: medium none; border-right: medium none; border-top: medium none; clear: both; text-align: left;">Is there a relationship between the diagonal sums of a magic square and its inverse?</div></li><li><br /><div align="center" style="border-bottom: medium none; border-left: medium none; border-right: medium none; border-top: medium none; clear: both; text-align: left;">Is the inverse of a magic square a magic square? Is the inverse of a <a href="http://mathworld.wolfram.com/SemimagicSquare.html">semi-magic square</a> a semi-magic square?</div></li><li><br /><div align="center" style="border-bottom: medium none; border-left: medium none; border-right: medium none; border-top: medium none; clear: both; text-align: left;">Is the square of a magic square a magic square? Is the square of a semi-magic square a semi-magic square? Cubes? Fourth powers?</div></li></ol><div style="border-bottom: medium none; border-left: medium none; border-right: medium none; border-top: medium none;"></div><div></div><div style="border-bottom: medium none; border-left: medium none; border-right: medium none; border-top: medium none;"><strong>Reference</strong>: Wilansky, Albert, <a href="http://www.jstor.org/pss/2306354">"The row-sums of the inverse matrix,"</a> The American Mathematical Monthly, Vol. 58, No. 9. (Nov., 1951), pp. 614-615.</div>Murphy Waggonerhttps://plus.google.com/105547390628598253045noreply@blogger.com1tag:blogger.com,1999:blog-7315635461469076658.post-3355126161534956742010-07-30T19:28:00.000-07:002012-06-08T22:29:38.694-07:00Euler Characteristic and Planar Graphs<div class="separator" style="clear: both; text-align: center;"><a href="http://3.bp.blogspot.com/_NQXH6jG7x6w/TFOJ2hCjVaI/AAAAAAAAANA/vjeHZe2SjEg/s1600/Euler+1.jpg" imageanchor="1" style="clear: right; cssfloat: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" bx="true" src="http://3.bp.blogspot.com/_NQXH6jG7x6w/TFOJ2hCjVaI/AAAAAAAAANA/vjeHZe2SjEg/s320/Euler+1.jpg" /></a></div>To the right we see a <a href="http://mathworld.wolfram.com/PlanarGraph.html">planar graph</a>. It divides the plane into 5 regions which I have labeled A, B, C, D and E. We call region D a triangle because it has three sides. Regions B, C and D are quadrilaterals since they have 4 sides. Even though A is an infinite region in the plane, it has 3 sides and is called a triangle. The question we address here is whether we can draw planar graphs with all possible combinations of triangles, squares, pentagons, etc., or not. Also, can we determine which combinations are possible? <br /><br />We will use the <a href="http://www.math.hmc.edu/funfacts/ffiles/10001.4-7.shtml">Euler Characteristic</a> for the sphere to solve this problem. I know it looks like the figure above is drawn on the plane, but you can also think of it as drawn on a relatively flat part of a sphere. In this way, region A is not infinite, but we will still call the regions triangles, quadrilaterals, pentagons, etc., even though they now have a curve to them. The Euler Characteristic is <em>V</em> – <em>E</em> + <em>R</em>, where <em>V</em> = number of vertices, <em>E</em> = number of edges (not the region E above) and <em>R</em> = number of regions. The Euler Characteristic depends only on the surface on which the planar graph is drawn, and not the shape of the graph. For the sphere, <br /><br /><div style="text-align: center;"><em>V</em> – <em>E</em> + <em>R</em> = 2, </div><div style="text-align: center;"><br /></div>always. In the example at the above, <em>V</em> – <em>E</em> + <em>R</em> = 6 – 9 + 5 = 2.<br /><br />Let’s do a little counting. In the figure above, <em>E</em> = 9 is the number of edges. However, if we count the sides of the polygons we get 2 triangles x 3 sides each + 3 quadrilaterals x 4 sides each = 18 sides. This is twice as many as the edges, because polygon each side is counted twice for each edge, once for the polygon on one side of the edge and once for the polygon on the other side of the edge. For instance, in the edge count, <i>E</i>, the edge <em>xy</em> is counted for the triangle D and the quadrilateral C.<br /><br />What about the vertices? In the figure above <em>V</em> = 6is the number of vertices. If we count the vertices of the polygons we get 2 triangles x 3 vertices each + 3 quadrilaterals x 4 vertices each = 18. In this case, we get three times as many polygon vertices as graph vertices because there are three polygons meeting at each vertex. For example, polygons A, B and C meet at vertex <em>t</em>. <br /><br />These counting techniques and the Euler Characteristic will give us a system of equations for finding whether graphs with certain combinations of polygons are possible. <br /><br /><strong>Example 1</strong>: Can we draw a planar graph with only triangles so that exactly three triangles meet at each vertex? If so, how many triangles will there be? We can answer this question with a system of linear equations. The first equation is the Euler Characteristic for the sphere:<br /><br /><div style="text-align: center;"><em>V</em> – <em>E</em> + <em>R</em> = 2.</div><br /><div style="border-bottom: medium none; border-left: medium none; border-right: medium none; border-top: medium none;">Each region is 3 sided, but if we count 3<em>R</em> sides that will be double the edges since each side is counted twice:</div><br /><div style="text-align: center;">3<em>R</em> = 2<em>E</em>.</div><br />Each region has 3 vertices, but if we count 3<em>R</em> vertices that will be triple the total vertices since three triangles meet at each vertex:<br /><br /><div style="text-align: center;"><div style="border-bottom: medium none; border-left: medium none; border-right: medium none; border-top: medium none;"><a href="http://4.bp.blogspot.com/_NQXH6jG7x6w/TFOJ_FvGgkI/AAAAAAAAANI/fpAGXXzL3PM/s1600/Euler+2.jpg" imageanchor="1" style="clear: right; cssfloat: right; cssfloat: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" bx="true" height="153" src="http://4.bp.blogspot.com/_NQXH6jG7x6w/TFOJ_FvGgkI/AAAAAAAAANI/fpAGXXzL3PM/s200/Euler+2.jpg" width="200" /></a>3<em>R</em> = 3<em>V</em>.</div></div><br />Solve this square system of 3 equations in 3 unknowns using your favorite method, and we find there is only one way to do this: <br /><br /><div style="text-align: center;"><em>V</em> = 4, <em>E</em> = 6 and <em>R</em> = 4. </div><br />The only solution is to have 4 triangles, 4 vertices and 6 edges as shown on the right, remembering that the outside region is a triangle. So, we could never draw a graph that had 5 triangles such that 3 triangles meet at each vertex. Give it a try to see why it can't be done.<br /><br /><strong>Questions</strong>: Can we draw a planar graph of triangles where 4 triangles meet at each vertex? 5 triangles meet at each vertex? 6 triangles meet at each vertex? How would we change the system above to answer these questions. If the graph exists, try to draw it. <br /><br /><strong>Example 2</strong>: What if there are two different types of polygons? Consider a graph of triangles and quadrilaterals, assuming that three polygons meet at each vertex. We will introduce two new variables: <em>T</em> and <em>Q</em>, the counts of the triangles and quadrilaterals, respectively. Now, the total number of regions is the sum of the two types of polygons,<br /><br /><div style="text-align: center;"><em>T</em> + <em>Q</em> = <em>R</em>.</div><br />Count the edges, 3 for each triangle and 4 for each quadrilateral, and as in Example 1, this counts each edge twice:<br /><br /><div style="text-align: center;">3<em>T</em> + 4<em>Q</em> = 2<em>E</em>.</div><br />Count the vertices, 3 for each triangle and 4 for each quadrilateral, and as in Example 1, this counts each vertex thrice, because 3 polygons meet at each vertex:<br /><br /><div style="text-align: center;">3<em>T</em> + 4<em>Q</em> = 3<em>V</em>.</div><br />Finally, we need the Euler Characteristic:<br /><br /><div style="text-align: center;"><em>V</em> – <em>E</em> + <em>R</em> = 2.</div><br />This time we’ll use a matrix and row reduction to get the solution. The system is underdetermined, so we expect to get infinitely many solutions.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="http://3.bp.blogspot.com/_NQXH6jG7x6w/TFOKHTkswiI/AAAAAAAAANQ/3-YMT9Zltbc/s1600/Euler+3.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" bx="true" src="http://3.bp.blogspot.com/_NQXH6jG7x6w/TFOKHTkswiI/AAAAAAAAANQ/3-YMT9Zltbc/s320/Euler+3.jpg" /></a></div><br /><br />Sure enough, we have a free variable and we can write the general solution as<br /><br /><div style="text-align: center;"><em>T</em> = 12 – 2<em>R</em>,<br /><em>Q</em> = –12 + 3<em>R</em>,<br /><em>V</em> = –4 + 2<em>R</em> and<br /><em>E</em> = –6 + 3<em>R</em>.</div><br />But in this application, the values of <em>T</em>, <em>Q</em>, <em>V</em> and <em>E</em> have physical meaning and must be positive. If <em>V</em> or <em>E</em> is zero, then the graph would be empty. We could assume that <em>T</em> or <em>Q</em> is zero, but we are interested in graphs with both triangles and squares. Now we can solve the inequalities below to see if there is a viable solution, and how many there are.<br /><br /><div style="text-align: center;"><em>T</em> = 12 – 2<em>R</em> > 0 => <em>R</em> < 6<br /><em>Q</em> = –12 + 3<em>R</em> > 0 => <em>R</em> > 2<br /><em>V</em> = –4 + 2<em>R</em> > 0 => <em>R</em> > 2<br /><em>E</em> = –6 + 3<em>R</em> > 0 => <em>R</em> > 4</div><br />Okay, <em>R</em> is an integer and strictly between 4 < <em>R</em> < 6, so <em>R</em> = 5 is the only realistic solution to this underdetermined system. Now,<br /><br /><div style="text-align: center;"><em>R</em> = 5, <em>T</em> = 2, <em>Q</em> = 3, <em>V</em> = 6 and <em>E</em> = 9.</div><br />Draw this graph (don’t forget that the outside region is one of the 5 regions and must be either a quadrilateral or a triangle). The graph is at the bottom of this blog, but don’t peak before you give it a try.<br /><br /><strong>Questions</strong>: <br /><br />1. Can you draw a planar graph with pentagons and hexagons such that three polygons meet at each vertex? If so, how many of each polygon are there? Can you draw them? <br /><br />2. Can you draw a planar graph with triangles and quadrilaterals such that four polygons meet at each vertex? I have written the equations and solved the system for this case, and this may have infinitely many solutions, but I haven’t had the time to draw more than two of the solutions and would like to see an algorithm for drawing all of them.<br /><br />3. Other surfaces, such as a torus (donut) have different Euler Characteristics. How does one draw a graph on a torus? What are the solutions to the questions above if the graphs live on a torus? <a href="http://mathworld.wolfram.com/EulerCharacteristic.html">Wolfram MathWorld</a> has a list of the Euler Characteristics for surfaces, but <a href="http://en.wikipedia.org/wiki/Euler_characteristic">WikiPedia</a> has nice images of those surfaces if you scroll to the bottom of the article.<br /><br />To limit this blog to a few pages, a lot is left unsaid. But again, these posts aren’t meant to give an in-depth discussion of the topic, but just an introduction. Go exploring for more about this topic.<br /><br /><strong>Reference: </strong>Alain M. Robert, <a href="http://www.math.uoc.gr/~ictm2/Proceedings/pap43.pdf">An Approach of Linear Algebra through Examples and Applications</a><br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="http://2.bp.blogspot.com/_NQXH6jG7x6w/TFOKNGYkd3I/AAAAAAAAANY/0eeVxrYO7z0/s1600/Euler+4.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" bx="true" src="http://2.bp.blogspot.com/_NQXH6jG7x6w/TFOKNGYkd3I/AAAAAAAAANY/0eeVxrYO7z0/s320/Euler+4.jpg" /></a></div>Murphy Waggonerhttps://plus.google.com/105547390628598253045noreply@blogger.com0tag:blogger.com,1999:blog-7315635461469076658.post-76028125034224068642010-07-22T09:10:00.000-07:002012-06-22T15:12:51.946-07:00Solving Balance Puzzles with Matrices<div class="separator" style="clear: both; text-align: center;"><a href="http://1.bp.blogspot.com/_NQXH6jG7x6w/TEhuXBbi37I/AAAAAAAAAMw/FxmPwITm8tc/s1600/Balance1.jpg" imageanchor="1" style="clear: right; cssfloat: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" hw="true" src="http://1.bp.blogspot.com/_NQXH6jG7x6w/TEhuXBbi37I/AAAAAAAAAMw/FxmPwITm8tc/s320/Balance1.jpg" /></a></div><div style="text-align: left;">I grew up on puzzles and games. A typical Christmas or birthday present was a puzzle book, and our family spent a lot of quality time together when the Games magazine came in the mail. Being the math nerd that I am, I would sometimes use trial and error for the puzzles, but anything I could convert into equations to solve was a bonus. So, in a way, I was introduced to linear algebra long before I took the class in undergraduate school. </div><div></div><br />These puzzles are from <a href="http://www.gamesmagazine-online.com/">Games magazine</a>, and I hope they forgive me for forgetting the specific issue for a complete citation. They provide a nice visual from which systems of equations can be developed. These systems tend to be underdetermined; however, there are added restrictions on the solutions--they must be integers within a certain range. Thus, these underdetermined systems have a finite number of solutions instead of infinite, specifically because equations are over a range of integers, not over the reals. <br /><div></div><br />Think of these puzzles like building a mobile, where the objects on each side must balance so that the horizontal bars stay horizontal under the following rules.<br /><ul><li>each shape represents a unique positive weight </li><li>each weight is an integer <i>N</i> such that 0 < <i>N</i> < 100 </li><li>the right and left sides of each horizontal beam must balance</li><li>a piece hanging directly below the fulcrum does not affect the balance between the left and right arms</li><li>the size of the pieces has no relation to weight</li><li>these are exercises in balancing number values and do not take into account the distance from the fulcrum</li></ul><strong>Example 1</strong>: For the mobile at the top of the page, the total weight is 36. I have labelled each weight with a variable name, <em>A</em>, <em>B</em> and <em>C</em>. The total weight is 36:<br /><br /><div style="text-align: center;"><em>A</em> + 2<em>B</em> + 2<em>C</em> = 36.</div><br />The left arm must balance the right arm: <br /><br /><div style="text-align: center;">A + 2<em>B</em> = 2<em>C</em> or <em>A</em> + 2<em>B</em> - 2<em>C</em> = 0.</div><br />We create an augmented matrix for this system and row reduce:<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="http://2.bp.blogspot.com/_NQXH6jG7x6w/TEhu9GlP3RI/AAAAAAAAAM4/nRTRTYXrXlw/s1600/BalanceMatrix.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" hw="true" src="http://2.bp.blogspot.com/_NQXH6jG7x6w/TEhu9GlP3RI/AAAAAAAAAM4/nRTRTYXrXlw/s320/BalanceMatrix.jpg" /></a></div><div></div><br />While using a matrix was not necessary for this simple problem, it will be useful for the larger systems below. So, <em>C </em>= 9, <em>B</em> is a free variable, and the general solution is<br /><br /><div style="text-align: center;">(<em>A</em>, <em>B</em>, <em>C</em>) = (18 - 2<em>B</em>, <em>B</em>, 9)</div><br />with some restrictions on B. Since 0 < A < 100,<br /><br /><div style="text-align: center;">0 < 18 - 2<i>B</i> < 100, </div><div style="text-align: center;">-18 < -2<i>B</i> < 82, and</div><div style="text-align: center;">9 > <i>B</i> > -41.</div><br /><div></div>Since <i>B</i> > 0, we find 0 < <i>B</i> < 9, and thus, there are 8 possible answers, one each for <i>B</i> = 1, 2, 3, 4, 5, 6, 7 and 8.<br /><br /><strong>Questions</strong>: First, solve the puzzles below, then consider these questions.<br /><ol><li>What would it take to create one of these puzzles? Can you create a puzzle that has a unique solution?</li><li>How would it change if we did consider distance from the fulcrum? Would it still be a linear system? If so, create a simple puzzle where distance is considered. </li><li>What determines how many equations are required? For instance, in Puzzle 1 below how many equations are described? Don't forget that each horizontal bar needs to balance, not just the top one.</li></ol><strong>Puzzle 1</strong>. The total weight is 80. Only one shape weighs more than 9 and the cube is 1 unit heavier than the octahedron.<br /><div align="center" class="separator" style="clear: both; text-align: center;"><a href="http://2.bp.blogspot.com/_NQXH6jG7x6w/TEhuIJPrbGI/AAAAAAAAAMo/TASTcuVUGSw/s1600/BalancePuzzle1.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" hw="true" src="http://2.bp.blogspot.com/_NQXH6jG7x6w/TEhuIJPrbGI/AAAAAAAAAMo/TASTcuVUGSw/s320/BalancePuzzle1.jpg" /></a></div><div align="center" class="separator" style="clear: both; text-align: center;"><br /></div><div></div><strong>Puzzle 2</strong>. The total weight is 54. The three arms are equal in weight.<br /><div class="separator" style="clear: both; text-align: center;"><a href="http://2.bp.blogspot.com/_NQXH6jG7x6w/TEhtvoIN9aI/AAAAAAAAAMg/sdOR-Q6bNwA/s1600/BalancePuzzle2.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" hw="true" src="http://2.bp.blogspot.com/_NQXH6jG7x6w/TEhtvoIN9aI/AAAAAAAAAMg/sdOR-Q6bNwA/s320/BalancePuzzle2.jpg" /></a></div><div class="separator" style="clear: both; text-align: center;"><br /></div><div style="border-bottom: medium none; border-left: medium none; border-right: medium none; border-top: medium none;"></div><div style="border-bottom: medium none; border-left: medium none; border-right: medium none; border-top: medium none;"><strong>Puzzle 3</strong>. The total weight is 180. The three arms are equal in weight.</div><div style="border-bottom: medium none; border-left: medium none; border-right: medium none; border-top: medium none;"></div><div class="separator" style="border-bottom: medium none; border-left: medium none; border-right: medium none; border-top: medium none; clear: both; text-align: center;"><a href="http://1.bp.blogspot.com/_NQXH6jG7x6w/TEhtR-mfTaI/AAAAAAAAAMY/0oyhxN4KPDA/s1600/BalancePuzzle3.jpg" imageanchor="1" style="cssfloat: left; margin-left: 1em; margin-right: 1em;"><img border="0" hw="true" src="http://1.bp.blogspot.com/_NQXH6jG7x6w/TEhtR-mfTaI/AAAAAAAAAMY/0oyhxN4KPDA/s320/BalancePuzzle3.jpg" /></a></div><div class="separator" style="border-bottom: medium none; border-left: medium none; border-right: medium none; border-top: medium none; clear: both; text-align: left;">---------------------------------------------</div><div class="separator" style="border-bottom: medium none; border-left: medium none; border-right: medium none; border-top: medium none; clear: both; text-align: left;">A later post - December 31, 2011</div><div class="separator" style="border-bottom: medium none; border-left: medium none; border-right: medium none; border-top: medium none; clear: both; text-align: left;"><br /></div><div class="separator" style="border-bottom: medium none; border-left: medium none; border-right: medium none; border-top: medium none; clear: both; text-align: left;">I found a link with more <a href="http://www2.stetson.edu/~efriedma/weight/">balance puzzles</a>. These are different looking, but the idea is the same. In this case you need to take the distance each weight is offset from the balance point into account. For example, a weight of 2 units that is 1 unit from the fulcrum will balance a weight of 1 unit that is 2 units from the fulcrum. Can you use linear algebra to solve these puzzles? If so, how?</div><div class="separator" style="border-bottom: medium none; border-left: medium none; border-right: medium none; border-top: medium none; clear: both; text-align: left;"><br /></div><div class="separator" style="border-bottom: medium none; border-left: medium none; border-right: medium none; border-top: medium none; clear: both; text-align: left;">Here is another page of balance puzzles.<a href="http://battleships.free.fr/balance_i.pdf">http://battleships.free.fr/balance_i.pdf</a></div>Murphy Waggonerhttps://plus.google.com/105547390628598253045noreply@blogger.com0tag:blogger.com,1999:blog-7315635461469076658.post-13731090882993861892010-07-21T10:23:00.000-07:002015-07-31T13:49:23.454-07:00Gould Index - Matrix Application to Geography<table cellpadding="0" cellspacing="0" class="tr-caption-container" style="float: right; margin-left: 1em; text-align: right;"><tbody><tr><td style="text-align: center;"><a href="http://1.bp.blogspot.com/_NQXH6jG7x6w/TEcJmBjbO6I/AAAAAAAAAK4/GB8bKeo4qzY/s1600/TownGraph2.jpg" imageanchor="1" style="clear: right; cssfloat: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" height="170" hw="true" src="http://1.bp.blogspot.com/_NQXH6jG7x6w/TEcJmBjbO6I/AAAAAAAAAK4/GB8bKeo4qzY/s200/TownGraph2.jpg" width="200" /></a></td></tr><tr><td class="tr-caption" style="text-align: center;">Figure 1:<br />Map of 7 towns connected by 9 roads</td></tr></tbody></table><div style="border-bottom: medium none; border-left: medium none; border-right: medium none; border-top: medium none;">The Gould Index has a nice visual that students enjoy, but it also is used to answer a question (important for applications) and can lead to discussions of the PageRank function used by Google. Much of this post is adapted from a paper by Patrick Carlson, one of my linear algebra students. He was interested in networks, and did a great job of understanding and explaining the general nature of the mathematics behind the Gould Index.</div><div style="border-bottom: medium none; border-left: medium none; border-right: medium none; border-top: medium none;"><br /></div><strong>Example 1</strong>: Consider a graph that respresents a set of towns (the vertices) and the travel routes between those towns (the edges) like in Figure 1. Historical geographers were interested in which town would become the trade center for this region. Now, you are saying to yourself that this is obvious in this picture, but let's see if some mathematics can come to the same result we do. If so, then let's apply it to a less obvious graph.<br /><br /><div style="border-bottom: medium none; border-left: medium none; border-right: medium none; border-top: medium none;"><table cellpadding="0" cellspacing="0" class="tr-caption-container" style="float: right; margin-left: 1em; text-align: right;"><tbody><tr><td style="text-align: center;"><a href="http://1.bp.blogspot.com/_NQXH6jG7x6w/TEcNOnFJfMI/AAAAAAAAALA/_0Wo-7JlyMs/s1600/TownMatrix2.jpg" imageanchor="1" style="clear: right; cssfloat: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" hw="true" src="http://1.bp.blogspot.com/_NQXH6jG7x6w/TEcNOnFJfMI/AAAAAAAAALA/_0Wo-7JlyMs/s320/TownMatrix2.jpg" /></a></td></tr><tr><td class="tr-caption" style="text-align: center;">Figure 2: Adjacency matrix for Figure 1</td></tr></tbody></table>First, make the adjacency matrix for the graph (Figure 2). Place a 1 in position (U, V) when U and V have a travel route between them and a 0 in the (W, T) position when there is no direct travel route between W and T. We will also place a 1 in each diagonal position, such as (Q, Q) as if there was a loop there, since clearly if you are in Town Q you can obviously get to Town Q. Notice that this matrix is <em>symmetric</em>, which will make some of the mathematics work but is also a way of checking to make sure you created the matrix correctly.</div><div style="border-bottom: medium none; border-left: medium none; border-right: medium none; border-top: medium none;"><br /></div><div style="border-bottom: medium none; border-left: medium none; border-right: medium none; border-top: medium none;">Now, here's the math. Find the eigenvalues of this matrix and find the largest one in absolute value. We get eigenvalues (2, 0, 4, -1, 0, 2, 0). The third one, 4, has the largest absolute value. Now, find the eigenvector associated with the eigenvalue of 4: <br />(0.3162, 0.3162, 0.3162, 0.3162, 0.6325, 0.3162, 0.3162). Normalize this vector by dividing by the sum of the entries, 2.5297, to get</div><br /><div align="center">(Q, R, S, T, U, V, W) =<br />(0.125, 0.125, 0.125, 0.125, 0.25, 1.25, 1.25).</div><div align="center"><br /></div><div align="left" style="border-bottom: medium none; border-left: medium none; border-right: medium none; border-top: medium none;">These are the Gould indices of each of the vertices, which describes how strongly each vertex is connected to the other vertices. As we knew, U is the most strongly connected with a Gould Index of 0.25, and the others are equally connected because of the symmetry of the graph.</div><div align="left" style="border-bottom: medium none; border-left: medium none; border-right: medium none; border-top: medium none;"><br /></div><div align="left" style="border-bottom: medium none; border-left: medium none; border-right: medium none; border-top: medium none;"><table cellpadding="0" cellspacing="0" class="tr-caption-container" style="float: right; margin-left: 1em; text-align: right;"><tbody><tr><td style="text-align: center;"><a href="http://1.bp.blogspot.com/_NQXH6jG7x6w/TEcT8toFObI/AAAAAAAAALQ/lQupHTQ3RKg/s1600/TownGraph1.jpg" imageanchor="1" style="clear: right; cssfloat: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" height="240" hw="true" src="http://1.bp.blogspot.com/_NQXH6jG7x6w/TEcT8toFObI/AAAAAAAAALQ/lQupHTQ3RKg/s320/TownGraph1.jpg" width="320" /></a></td></tr><tr><td class="tr-caption" style="text-align: center;">Figure 3: Another graph</td></tr></tbody></table><strong>Example 2: </strong>What if we looked at a graph that more realistically represents a set of towns, which may have rivers, mountains or other geographical features preventing travel routes between towns, as in the graph in Figure 3. In this case, would G be the trade center because it is directly connected to the most towns, or would it be C because between C and every other town is at most one town? Create the adjacency matrix (with ones along the diagonal), and find the eigenvalues which are<br />(4.01, -1.37, 1.71, 1, -0.37, -0.56, 2.58, 1, 1). The first is the largest and the eigenvector associated with it is<br />(0.2941, 0.4097, 0.5023, 0.3249, 0.3026, 0.1359, 0.4770, 0.1583, 0.1583) and the sum of the entries is 2.7631. Normalize by dividing by the sum of the entries to get the Gould indices:</div><div align="left" style="border-bottom: medium none; border-left: medium none; border-right: medium none; border-top: medium none;"><br /></div><div align="center" style="border-bottom: medium none; border-left: medium none; border-right: medium none; border-top: medium none;">(A, B, C, D, E, F, G, H, I) =<br />(0.1064, 0.1482, 0.1818, 0.1176, 0.1095, 0.0492, 0.1726, 0.0573, 0.0573).</div><div align="center" style="border-bottom: medium none; border-left: medium none; border-right: medium none; border-top: medium none;"><br /></div><div align="left" style="border-bottom: medium none; border-left: medium none; border-right: medium none; border-top: medium none;">Of course, we can see which Gould index will be largest before normalizing, but there are other applications for which normalized values of the eigenvector will have meaning, so it doesn't hurt to get used to normalizing. We see that C has the largest Gould Index with 0.18, but G comes in a close second with 0.17. In this calculation, more value is given to vertices that are closer to others <em>along paths of length more than 1</em> than to vertices that connect with a path of length 1 to more vertices. Note that I and H have the same smallest index, as expected.</div><div align="left" style="border-bottom: medium none; border-left: medium none; border-right: medium none; border-top: medium none;"><br /></div><div align="left" style="border-bottom: medium none; border-left: medium none; border-right: medium none; border-top: medium none;"><strong>What is going on?</strong> Although we have some empirical evidence that the Gould index does what is expected, what is the theory behind it? A version of the Perron-Frebonius Theorem says that if a matrix is <a href="http://mathworld.wolfram.com/NonnegativeMatrix.html">nonnegative</a> and <a href="http://planetmath.org/encyclopedia/PrimitiveMatrix.html">primitive</a>, then there will be a real eigenvector that dominates the others in absolute value, it will have multiplicity 1, and the eigenvector associated with it will be real and positive [C]. The adjacency matrices above are nonnegative since all the entries are 0 or 1, and for the two above I checked that they are primitive; in Example 1, the square of the matrix was positive, and in Example 2, it took the fourth power of the matrix before getting a positive matrix. We don't use the adjacency <em>A</em>, per se, but instead we use <em>B</em> = <em>A</em> + <em>I</em> when we put 1s in the diagonal. Try a bipartite graph and see that the powers of <em>A</em> will never be positive, and thus <em>A</em> is not primitive in that case, but <em>B</em> = <em>A</em> + <em>I</em> will be.</div><div align="left" style="border-bottom: medium none; border-left: medium none; border-right: medium none; border-top: medium none;"><br /></div><div align="left" style="border-bottom: medium none; border-left: medium none; border-right: medium none; border-top: medium none;">Straffin discusses the how of the Gould index in more detail, and discusses its connection to finding the dominant team in a round robin tournament and measuring the importance in nodes in a communications network. He has a significant list of references to examples of this method along with references to other uses of linear algebra and graphs in geography. This method is a beginning for the mathematics behind the algorithm used in PageRank used by Google; however, the adjacency matrix (with 1s on the diagonal) is not primitive and is too large to find the eigenvalues and eigenvectors directly. But that is a discussion for another day.<br /><br /><strong>Questions</strong>: When this model is applied to historical travel routes, the trade center predicted by the model does not always match the trade center that develops. Non-geographical issues may be involved here, such as politics and wealth, but it is clear that the model does not take into account the time of travel. Maybe there is a train between two towns for quick access, but two others are only accessible on foot through a mountain pass. Can we change the results for Example 2 above by considering a weighted graph instead? If so, should we weight with time of travel or the reciprocal of time of travel? How would the diagonal elements be weighted?<br /><br />The <em>n</em>th power of an adjacency graph gives the number of paths of length <em>n</em> between vertices <em>x</em> and <em>y</em> in the (<em>x</em>, <em>y</em>) position. Could this be used in someway to predict the trade center?<br /><br />In Gould's article is a study of the travel routes of Uganda in 1921 and 1935, and Straffin's paper has references to other studies. Can you reproduce these results?</div><div align="left" style="border-bottom: medium none; border-left: medium none; border-right: medium none; border-top: medium none;"><br /></div><div align="left" style="border-bottom: medium none; border-left: medium none; border-right: medium none; border-top: medium none;"><strong>References</strong>:</div><div align="left" style="border-bottom: medium none; border-left: medium none; border-right: medium none; border-top: medium none;"><br /></div><div align="left" style="border-bottom: medium none; border-left: medium none; border-right: medium none; border-top: medium none;">[C] Hal Caswell, Matrix Popoulation Models, Sinauer, 1989.</div><br />[G] P. R. Gould, "<a href="http://www.jstor.org/pss/621372">On the geographical interpretation of eigenvectors</a>," Transactions of the Institute of British Geographers, No. 42 (Dec., 1967), pp. 53-86.<br /><br />[S] Phillip D. Straffin, "<a href="http://www.jstor.org/pss/2689388">Linear Algebra in Geography: Eigenvectors of Networks</a>," Mathematics Magazine, Vol. 53, No. 5 (Nov., 1980), pp. 269-276.Murphy Waggonerhttps://plus.google.com/105547390628598253045noreply@blogger.com1tag:blogger.com,1999:blog-7315635461469076658.post-11519935964508764682010-07-20T08:57:00.000-07:002010-07-22T09:34:48.031-07:00Solving Number Puzzles with Matrices<a href="http://3.bp.blogspot.com/_NQXH6jG7x6w/TEXZNrNlxWI/AAAAAAAAAKY/P-04Yaxf0ZE/s1600/NumberPuzzle2.jpg"><img alt="" border="0" id="BLOGGER_PHOTO_ID_5496037749236811106" src="http://3.bp.blogspot.com/_NQXH6jG7x6w/TEXZNrNlxWI/AAAAAAAAAKY/P-04Yaxf0ZE/s200/NumberPuzzle2.jpg" style="float: right; height: 200px; margin: 0px 0px 10px 10px; width: 184px;" /></a>The <a href="http://school.discoveryeducation.com/">Discovery Education Classroom Resources</a> has some great classroom tools. One of my favorites is <a href="http://puzzlemaker.discoveryeducation.com/">Puzzle Master</a>. It allows you to create custom puzzles like word searches or cryptograms. I used the <a href="http://puzzlemaker.discoveryeducation.com/NumberBlocksForm.asp">Number Blocks</a> puzzle creator for a linear algebra project on overdetermined and underdetermined systems of equations.<br /><br />An example of a number block puzzle created using Puzzle Master is given above. The numbers to the right an bottom are the sums of various rows, colums and diagonals of the 3-by-3 grid of numbers. The main diagonal sums to 14; the off diagonal sums to 17. The sum of each row is to the right, and the sum of the columns is at the bottom. In this example, there are 6 unknowns and 8 equations, and so this is an overdetermined but <em>consistent</em> system. Puzzle Master will not create a puzzle that does not have a solution.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="http://2.bp.blogspot.com/_NQXH6jG7x6w/TEXbJwWHY3I/AAAAAAAAAKo/Ezx9-Hw3J9g/s1600/NumberPuzzle2System.jpg" style="margin-left: 1em; margin-right: 1em;"><img alt="" border="0" id="BLOGGER_PHOTO_ID_5496039880918524786" src="http://2.bp.blogspot.com/_NQXH6jG7x6w/TEXbJwWHY3I/AAAAAAAAAKo/Ezx9-Hw3J9g/s400/NumberPuzzle2System.jpg" style="height: 195px; width: 400px;" /></a></div><div style="border-bottom: medium none; border-left: medium none; border-right: medium none; border-top: medium none;"><br /></div><div style="border-bottom: medium none; border-left: medium none; border-right: medium none; border-top: medium none;"><br /></div><div style="border-bottom: medium none; border-left: medium none; border-right: medium none; border-top: medium none;"><strong>Questions</strong>: We can create a system of equations for this number puzzle as shown above. There are a lot of questions that can be asked about these number puzzles and the systems that can solve them.</div><ul><li style="border-bottom: medium none; border-left: medium none; border-right: medium none; border-top: medium none;">Given an <em>n</em>-by-<em>n</em> grid of numbers, how many equations are needed to solve the puzzle?</li><li style="border-bottom: medium none; border-left: medium none; border-right: medium none; border-top: medium none;">What determines how many unknows there are?</li><li style="border-bottom: medium none; border-left: medium none; border-right: medium none; border-top: medium none;">Given an <em>n</em>-by-<em>n</em> grid of numbers, how many unknowns must there be for the system to be overdetermined? Underdetermined? Square?</li><li style="border-bottom: medium none; border-left: medium none; border-right: medium none; border-top: medium none;">Are there equations in the system below that can be removed so that the system is not overdetermined but has an equivalent solution? If so, how many and which equations can be removed.</li><li style="border-bottom: medium none; border-left: medium none; border-right: medium none; border-top: medium none;">If a number puzzle is underdetermined, how can a solution be found?</li><li style="border-bottom: medium none; border-left: medium none; border-right: medium none; border-top: medium none;">Is it possible for a number puzzle to have exactly two different solutions? Exactly five different solutions? Explain.</li><li style="border-bottom: medium none; border-left: medium none; border-right: medium none; border-top: medium none;">Is it possible for a number puzzle to have infinitely many solutions? Describe a puzzle for which this would be true, and explain how to describe the infinitely many solutions.</li><li style="border-bottom: medium none; border-left: medium none; border-right: medium none; border-top: medium none;">Puzzle Master won't create a puzzle with no solution, but can you create a puzzle that has no solution and is overdetermined? Underdetermined? Square?</li><li style="border-bottom: medium none; border-left: medium none; border-right: medium none; border-top: medium none;">Create a puzzle using Puzzle Master that would have infinitely many solutions. Can you make a conjecture on how Puzzle Master chose the solution that it gives?</li></ul><div style="border-bottom: medium none; border-left: medium none; border-right: medium none; border-top: medium none;"><br /></div><div align="center"></div>Murphy Waggonerhttps://plus.google.com/105547390628598253045noreply@blogger.com0