# Math Fun

Fun with Polygons:  Recently, I ran across an incredibly charming example of how theory, application and computation blend together beautifully in linear algebra.  The example is the subject of the SIAM 2018 John von Neumann Lecture delivered by an outstanding researcher of numerical linear algebra, Charles Van Loan, where he made some fascinating observations on how to systematically “untangle” a randomly selected polygon, no matter how convoluted it is. The idea is as follows: Say that the polygon is described by distinct vertices (x0, y0),…,(xn, yn), where the last vertex is connected to the first. Consider this iterative process for constructing successive polygons:

1. Construct the initial polygon by a random selection of x- and y-coordinates for n+1 vertices, (x0,y0),…,(xn, yn).
2. Translate the polygon so that the centroid of the resulting polygon is at the origin (obtained by averaging each of the sums of x- and y-coordinates, dividing by n+1 and subtracting the results from each coordinate).
3. Use the vector 2-norm to normalize the size of the polygon so that the norms of the vectors of x- and y-coordinates coordinates are both one.
4. Plot this polygon in the xy-plane.
5. Construct a new polygon from the old by replacing each vertex (xi, yi ) by the midpoint vertex ((xi, yi) + (xi+1, yi+1))/2 of the segment connecting these two points of the polygon, where the indices are computed mod n+1.
6. Repeat steps 3-5 until the polygon shapes settle down to an approximately constant form.

The tools in this exploration are two ALAMA calculator programs (VanLoanExampleN.alm and VanLoanExampleNcplx.alm) which are available in the in the folder ALAMAprograms, or you may write your own programs that achieve the same results. The suffix ’N’ means that the standard normal distribution was used to generate it.  In addition, the suffix “cplx” means that the following alternative method was used in place of steps 3 and 4: View the x- and y-coordinates of a point as coordinates of the complex number z = x + yi, normalize the resulting vector of complex numbers with the complex 2-norm, plot the resulting polygon in the complex plane and construct a new polygon by averaging successive vertices. Here are pictures of the results where the number of vertices is 14 and 10 iterations of the process above are used to generate each figure using the real and complex versions of the algorithm. The figures are scaled up by factors of 3 and 4, resp., and colors for successive figures starting with the random polygon are black, red, green, blue, dark yellow and cyan:

Every time you repeat this experiment, you get similar results: The limiting polygon takes a familiar shape.  How to explain this settling down to a constant convex figure?  Linear algebra to the rescue, and I’ll leave the full explanation for the reader to explore, but here’s the first step: the averaging of step 5 can be viewed as a matrix/vector multiplication, where the vectors are vectors of x- and y- coordinates (or a single vector with complex coordinates x + yi in the case of the complex version).

Fun with Number Theory: I’m a fan of Great Courses offerings and recently I had the pleasure of watching the offering “Introduction to Number Theory” by Professor Edward Burger. The course was designed for those who may have been long away from their high school algebra (as it should have been), so it wasn’t terribly exciting for me personally until he made this delightful “come-on” in Lecture 2: You are assured that there is some power of 2 whose first nine digits are exactly your social security number. I had to wait till Lecture 21 to begin to see some justifications for this “powers of 2” assertion. I was intrigued by some unproved statements concerning this claim, so I went about writing my own proofs in the spirit of Professor Burger’s course: requiring no more than high school algebra and geometry. In fact, I ended up writing a brief essay, which includes a modest introduction to number theory complete with a few exercises. You can see it in the following pdf file, which you may  have to download if your viewer doesn’t show it.

FunWithNumbers

ALAMA Calculator helped me in two ways: First, experimentation with it gave me the clues that I needed to write proofs of the necessary results substantiating the “powers of 2” claim.  Secondly, I had a bit of fun verifying simpler versions of the claim which are included as exercises at the end of “Fun with Numbers”.  If you want to play around with these ideas there are a few ALAMA Calculator programs that you might find helpful, namely a sorting program, programs to construct/deconstruct continued fractions and just for fun, a gcd program.  Another program that I found useful in my experimentation was InsertionSortCndx.alm.  This program sorts a list of numerical data, but also preserves the initial indices of the sorted items, so that the initial positions of each sorted item held before sorting are known.  These are contained in the folder ALAMAprograms.

Fun with Coding: Speaking of “sorting”, some standard topics in an introductory computer science course are algorithms and their complexity.  The problem of sorting a list of numbers (or words or anything else that can be linearly ordered) can be used to illustrate these ideas.  In fact, I needed a sorting program to help me find proofs of certain theorems in the “FunWithNumberTheory” pdf.  I have claimed that ALAMA Calculator is fully programmable, so I decided to put my feet to the fire and write suitable sorting programs on it.  To add to the challenge, I decided that the programs should only use the single variable C that consists of the list of numbers to be sorted as a row vector augmented by two entries that are the start and finish of the section of C to be sorted.  One reason for this constraint is that ALAMA Calculator only has 10 named variables, so in case others are already in use, one should try to use as few extra variables as possible.

So, what algorithms to use?  I decided to try two well known methods:  insertion sort and quicksort, which resulted in the ALAMA programs InsertionSortC.alm and QuickSortC.alm.  (Aside to programmers: Along the way I realized that it was very helpful to expand the functionality of the Rpt() command, which I did in version (1.1.1).)  Given that n items are to be sorted, the insertion sort algorithm is known to have best, average and worst case complexities of  O(n), O(n^2) and O(n^2), respectively.  For quicksort, the corresponding complexities are O(n log(n)), O(n log(n)) and  O(n^2). Accordingly, one is tempted to always use quicksort instead of insertion sort.  On average, this is ok, but it’s  instructive to experiment with different lists of items and compare the timings for each method.  Try this experiment on ALAMA Calculator:

B = [RndN([1:400]), 1, 400];
C = B;

Now load the program InsertionSortC.alm and execute the command Rpt(1,1), but also use a timer to determine time of execution.  Next, set C equal to B again (to insure that we’re comparing sorting of the same list) and repeat this experiment with the program QuickSortC.alm. My timing results on my mac were about 22 second for insertion sort and about 3 seconds for quicksort.  This is what you’d expect, right?  Next, repeat the whole experiment with these initial values: B = [Ones(1,400), 1, 400]; C = B; My timing results were surprising: about 6 seconds for insertion sort and 25 seconds for quicksort.  One learns in a detailed study of these algorithms that quicksort has more of a problem with many equal items in the list.  Moral:  Matters are a bit more nuanced than one might expect if one depended only on the average complexities of these algorithms.

Fun with Probability: Here’s a not-too-uncommon situation: You’ve shown symptoms of a certain disease, so your physician had you take a test for the disease.  The results come back positive:  Should you be worried?  I collected data for a very specific example. To the best of my knowledge, the data are reasonably accurate.

Example.  The following estimates are drawn from various sources of data. It is estimated that for women in the United States under the age of 40 , the mammogram test for breast cancer has a sensitivity of 71.3% (the probability of the test returning a positive result, given that you have the disease) and a specificity of 85.9% (the probability that the test will return a negative result, given that you do not have the disease).  It is also estimated that breast cancer for these women occurs in approximately 115 out of 100,000 individuals. Now suppose that you are a woman under the age of 40 and your mammogram tests positive for cancer. How concerned should you be?

Well, that depends, doesn’t it?  The message of this exercise is that you should be cautious about rushing to judgment — initial intuitions can be inaccurate.  I’m just going to give you the answer, which I computed with a simple one-line ALAMA Calculator program (BayesTest.alm): Your likelihood of having breast cancer is about 0.58%.  This is a rather surprising result – not to say that there should be no concern about the outcome of this test, but the possibility of a false positive is very high, namely approximately 99.42%. So how and why is this so?  Well, if you’re know enough enough probability theory that you’ve seen Bayes’ Theorem and its applications, you can guess the answer.  If not (or you’ve long forgotten the relevant material), I’ve written an elementary introduction to probability theory that concludes with a full explanation of the above example:

FunWithBayes

Fun with Sudoku: OK, there really isn’t a whole lot of math in this section. It’s more a programming discussion. We know how Sudoku works: We’re given a 9×9 table (matrix, really) of entries, some blank and others with integers between 1 and 9. It can also be viewed as a 3×3 table of 3×3 subsquares, which are commonly termed blocks.   The idea is to fill in the blanks in such a way that each row, column and block contains all of the integers between 1 and 9 exactly once.

Of course some Sudoku puzzles are more difficult than others, depending on the number of specified entries and their locations. Accordingly, it’s customary to classify these puzzles as ‘Very Easy’, ‘Easy’, ‘Medium’ or ‘Hard’. So more strategies are needed as the difficulty of the puzzle increases

We will implement the very simplest strategies, namely what could be called 1-entry strategies:  If a row, column or block had a blank entry that could only contain a specific integer n, then insert n into the blank entry.  Conversely, if an entry already contains an integer n, see to it that every other blank entry in this entry’s row, column and block is disallowed from containing n.  It turns out that these two strategies seem to be sufficient to completely solve Very Easy and Easy puzzles.  For the more difficult puzzles more sophisticated strategies which utilize 2-entry and 3-entry behaviors.  Nonetheless, the 1-entry strategies can be a good start on solving the more difficult puzzles.

Enter the program ‘SudoTool1.alm’, which executes the 1-entry strategies repeatedly until they yield no further improvement.  Currently, the program is only available in the latest versions (1.1.3) of the Mac and Windows calculator downloads.  For all versions, I have included the program and additional sample problems in the compressed folder Sudo.zip below.  The program will solve the Very Easy and Easy puzzles completely and at least give you a start on Medium and Hard puzzles.  I’m pleased that the humble ALAMA calculator, even with only ten named variables, was able to implement the strategy in about 130 lines of code.  As I have commented before, ALAMA calculator is very programmable, but it takes a bit of cleverness to get the job done.  Programmers will note that the key to getting things to work is to set up the right sort of data variables.  The 9×9 matrix variable ‘A’ contains the current version of the initial input matrix, with zero entries representing blanks in the puzzle.  There’s more (every named variable gets used), but I’ll just add that the variable ‘B’ in the program is designed to describe the current status of each entry, where the entries are indexed row by row in increasing order and the corresponding row index of the 81×14 matrix ‘B’ describes the state of that entry.

So let’s see how it works. In the ALAMACalculator folder and the Sudo folder in the zipped file at the bottom of this page are some programs named ‘SudoAxy.alm’.  Here A stands for the matrix A,  x could be E, VE, M or H, and optional y is a number. Each of these ‘programs’ is actually just a copy of variable A in which the Sudoku puzzle is stored. You have to load one of these first. Next, load the program ‘SudoTool1.alm’ and issue the command ‘Rpt(1,1)’. You’ll have to wait a bit. After all, the program can only see one entry variable at a time and that can get complicated and involve long searches.  Eventually, you will see a listing of row vectors whose third and fourth entries are the number of nonempty entries after and before the current iteration, followed at the end by the new value of the matrix A calculated by the program. Let’s try it out:

Fire up the calculator and load the file ‘SudoAE.alm’. This is the A-matrix for an Easy difficulty puzzle. Type ‘A<Enter>’ and you should get this output:

Out>A :
0, 0, 0, 0, 0, 0, 0, 7, 0 ;
0, 3, 5, 0, 8, 0, 0, 0, 6 ;
0, 0, 0, 0, 0, 0, 0, 0, 4 ;
0, 0, 0, 0, 7, 2, 0, 9, 3 ;
0, 0, 0, 0, 9, 8, 1, 0, 0 ;
9, 0, 0, 0, 0, 0, 6, 2, 0 ;
8, 0, 0, 7, 0, 3, 0, 0, 2 ;
6, 0, 0, 0, 0, 0, 0, 0, 0 ;
0, 0, 2, 0, 1, 0, 8, 5, 0

Here the zeros represent blank entries in the puzzle. Now load the program ‘SudoTool1.alm’ and execute it with ‘Rpt(1,1)’ and wait a bit. You’ll get this output:

Out>v(3) = Sum (Max ([2 – B([1: v(2)], v(1) + 1), 0 * Ones(v(2), 1)])) :
9, 81, 27, 25
Out>v(3) = Sum (Max ([2 – B([1: v(2)], v(1) + 1), 0 * Ones(v(2), 1)])) :
9, 81, 40, 27
Out>v(3) = Sum (Max ([2 – B([1: v(2)], v(1) + 1), 0 * Ones(v(2), 1)])) :
9, 81, 45, 40
Out>v(3) = Sum (Max ([2 – B([1: v(2)], v(1) + 1), 0 * Ones(v(2), 1)])) :
9, 81, 54, 45
Out>v(3) = Sum (Max ([2 – B([1: v(2)], v(1) + 1), 0 * Ones(v(2), 1)])) :
9, 81, 55, 54
Out>v(3) = Sum (Max ([2 – B([1: v(2)], v(1) + 1), 0 * Ones(v(2), 1)])) :
9, 81, 59, 55
Out>v(3) = Sum (Max ([2 – B([1: v(2)], v(1) + 1), 0 * Ones(v(2), 1)])) :
9, 81, 77, 59
Out>v(3) = Sum (Max ([2 – B([1: v(2)], v(1) + 1), 0 * Ones(v(2), 1)])) :
9, 81, 81, 77
Out>v(3) = Sum (Max ([2 – B([1: v(2)], v(1) + 1), 0 * Ones(v(2), 1)])) :
9, 81, 81, 81
Out>A :
2, 4, 8, 9, 6, 1, 3, 7, 5 ;
7, 3, 5, 2, 8, 4, 9, 1, 6 ;
1, 6, 9, 5, 3, 7, 2, 8, 4 ;
4, 8, 6, 1, 7, 2, 5, 9, 3 ;
5, 2, 3, 6, 9, 8, 1, 4, 7 ;
9, 1, 7, 3, 4, 5, 6, 2, 8 ;
8, 9, 1, 7, 5, 3, 4, 6, 2 ;
6, 5, 4, 8, 2, 9, 7, 3, 1 ;
3, 7, 2, 4, 1, 6, 8, 5, 9

Interesting… So what this tells us is that SudoTool1 was able to solve the problem completely, starting with 25 nonempty entries, but the first pass of the program’s algorithm only determined two more entries and it took eight more passes to completely solve the puzzle. OK, let’s try a Medium level puzzle with a similar number of initial nonempty entries. Load up the file ‘SudoAM.alm’ and type ‘A<Enter>’ and you should see output

Out>A :
0, 0, 3, 0, 0, 4, 0, 8, 0 ;
0, 6, 5, 0, 8, 7, 0, 0, 0 ;
0, 0, 0, 0, 0, 9, 0, 0, 0 ;
0, 0, 0, 2, 0, 0, 0, 7, 0 ;
0, 0, 0, 6, 4, 0, 0, 0, 8 ;
0, 0, 8, 0, 0, 0, 5, 6, 0 ;
0, 0, 0, 7, 0, 0, 0, 0, 0 ;
0, 4, 0, 0, 0, 0, 0, 1, 2 ;
0, 0, 9, 0, 0, 3, 0, 0, 7

Now load the program ‘SudoTool1.alm’ and execute it with ‘Rpt(1,1)<Enter>’ and wait a bit. You’ll get this output:

Out>v(3) = Sum (Max ([2 – B([1: v(2)], v(1) + 1), 0 * Ones(v(2), 1)])) :
9, 81, 24, 23
Out>v(3) = Sum (Max ([2 – B([1: v(2)], v(1) + 1), 0 * Ones(v(2), 1)])) :
9, 81, 30, 24
Out>v(3) = Sum (Max ([2 – B([1: v(2)], v(1) + 1), 0 * Ones(v(2), 1)])) :
9, 81, 34, 30
Out>v(3) = Sum (Max ([2 – B([1: v(2)], v(1) + 1), 0 * Ones(v(2), 1)])) :
9, 81, 36, 34
Out>v(3) = Sum (Max ([2 – B([1: v(2)], v(1) + 1), 0 * Ones(v(2), 1)])) :
9, 81, 36, 36
Out>A :
0, 0, 3, 0, 0, 4, 0, 8, 0 ;
0, 6, 5, 0, 8, 7, 0, 0, 0 ;
0, 0, 0, 0, 0, 9, 0, 0, 0 ;
0, 0, 0, 2, 3, 8, 0, 7, 0 ;
0, 0, 0, 6, 4, 5, 0, 0, 8 ;
0, 0, 8, 9, 7, 1, 5, 6, 0 ;
0, 0, 0, 7, 0, 2, 0, 0, 0 ;
0, 4, 7, 8, 0, 6, 0, 1, 2 ;
0, 0, 9, 4, 1, 3, 0, 5, 7
Out>

Uh oh, looks like 1-entry strategies were not up to the job here. SudoTool1 was only able to fill in 13 more entries.  That’s why Medium problems aren’t Easy problems!  What are needed are more sophisticated 2-entry, 3-entry, etc., strategies. These are based on a simple idea related to the pigeonhole principle: If n distinct numbers are to be placed in n entries with no more than one number per entry, then every entry must contain exactly one of the n numbers.  So if you find two entries in a given row, column or block whose only possible numbers are m and n, then those numbers will go in these two entries and nowhere else in that row, column or block.  Ditto for three entries.  When working harder problems by hand, I follow the common strategy of identifying the 2-entries (and subsequently, if needed, 3-entries) by annotating the two choices in a corner of the entry and looking for a matching pair in a given row, column or block.  If a match is found in the same row, column or block, we can remove those two entries as possibilities in every other entry of that row, column or block.  If the 2-entries are of no assistance, we could move onto 3-entry triples.  Or … You could simply make guesses and see what happens.

Looking over the output of our Medium problem, I could only see eleven  2-entries, and the only ones of any value in reducing choices were the (7,5)th and (8,5)th entries in the fifth column, where the only possible numbers in those two entries are 5 and 9. That helped a little bit since it generated a new 2-entry pair at entries (1,5) and (3,5), where the only possible numbers for them became 2 and 6. But that was all that jumped out at me. So I decided to try a guess, and the natural entries to use for this strategy are 2-entries. Look for one that is richest in connections to other entries. My choice was (9,2)th entry, where the only possible numbers were 2 and 8. OK, now which one goes in this entry? Well, let’s try 8 — but being lazy we’ll have SudoTool1.alm help us out. First, in order to rerun ‘SudoTool1.alm’ with our guess, issue the commands

In> A(9,2)=8

In>Rpt(1,2,2)

Do so and you should see as final output

Out>A :
9, 1, 3, 5, 2, 4, 7, 8, 6 ;
4, 6, 5, 3, 8, 7, 9, 2, 1 ;
8, 7, 2, 1, 6, 9, 4, 3, 5 ;
6, 5, 4, 2, 3, 8, 9, 7, 1 ;
7, 9, 1, 6, 4, 5, 2, 3, 8 ;
3, 2, 8, 9, 7, 1, 5, 6, 4 ;
1, 3, 6, 7, 5, 2, 8, 4, 9 ;
5, 4, 7, 8, 9, 6, 3, 1, 2 ;
2, 8, 9, 4, 1, 3, 6, 5, 7
Out>

Great! So it was a good guess, right? Well, maybe not! Scroll up a bit in the Output window and you see seemingly  infinitely many “Invalid coordinates” lines, which is suspicious. Well, you could eyeball it and find the problem, or be lazy and use ALAMA calculator:  If each row and column contains the numbers 1 through 9 once each, then the sum each row or column should be 45 (remember that introduction to proof by induction showing the sum of the first n positive integers is n(n+1)/2?). Let’s check, rows first: Issue the command “Tran(Sum(A))” and you should see

Out>Tran (Sum (A)) :
45, 45, 45, 45, 45, 45, 45, 45, 45

So far so good. Now issue the command ‘Tran(Sum(Tran(A)))’ and you should see

Out>Tran (Sum (Tran (A))) :
45, 45, 45, 45, 45, 45, 53, 39, 43

Whoops! There’s a problem all right, the last three columns are bad!  So the guess of A(9,2)=8 was wrong. We’ll have to start over, so load ‘SudoAM.alm’ again. But this time let’s cut to the chase and enter the command

In> A(9,2)=2

Then load up ‘SudoTool1.alm’ and run it.  You should see at the end of the output

Out>A :
1, 9, 3, 5, 2, 4, 7, 8, 6 ;
4, 6, 5, 3, 8, 7, 2, 9, 1 ;
7, 8, 2, 1, 6, 9, 4, 3, 5 ;
6, 5, 4, 2, 3, 8, 1, 7, 9 ;
9, 7, 1, 6, 4, 5, 3, 2, 8 ;
2, 3, 8, 9, 7, 1, 5, 6, 4 ;
5, 1, 6, 7, 9, 2, 8, 4, 3 ;
3, 4, 7, 8, 5, 6, 9, 1, 2 ;
8, 2, 9, 4, 1, 3, 6, 5, 7
Out>

Now do our checks of rows and columns (you’ll have to eyeball the blocks separately):

Out>Tran (Sum (A)) :
45, 45, 45, 45, 45, 45, 45, 45, 45
Out>Tran (Sum (Tran (A))) :
45, 45, 45, 45, 45, 45, 45, 45, 45

And there you have it. A single entry addition to our Medium problem turned it into an “easy” problem and ‘SudoTool1.alm’ was able to crank out the solution. Of course, this isn’t going to happen every time, but it gives you an idea of the possibilities.

One more note about ‘SudoTool1.alm’: It’s constructed in a such a way that it will work on 4×4 and even (heaven forbid!!) 16×16 or 25×25 Sudoku-like puzzles. Here’s the program and lots of examples to play with: