403 – Homework 2

February 28, 2013

This new set is due Monday, March 11, at the beginning of lecture.

  • Write a program that, given a square matrix A, computes approximations to its eigenvalues using the QR-algorithm. Ideally, the user can decide the dimensions of the matrix and, more importantly, the error within which the approximations will be found. Apply your method to a 4\times 4 matrix, and check the number of iterations the process requires.

Please turn in: The code (best if you email it to me), a write up explaining what your code does, the matrix you applied the method to, and the result. For this, you can work in groups of two or three. In case you cannot find anybody to work with, and do not know ow to program, let me know as soon as possible, and we will find an alternative.

(As extra credit problem, write a program for Francis’s algorithm as well, together with an explanation of your code, and apply the algorithm to the same 4\times 4 matrix.)

For the remaining problems, you should turn in your own work. You can still collaborate with others, but please make sure to give appropriate credit and indicate clearly who you worked with, what references you consulted, etc:

  • Give an example of a matrix for which the power method fails. (Include a proof that this is indeed the case.)
  • Let A be an n\times n matrix with complex entries. Consider it as a linear transformation A:\mathbb C^n\to\mathbb C^n. Verify explicitly that A^* is the unique matrix with the property that u\cdot A^*v=(Au)\cdot v for all vectors u,v. Recall that for u=(u_1,\dots,u_n)^T and v=(v_1,\dots,v_n)^T, their dot product u\cdot v is given by u\cdot v=u_1\bar{v_1}+u_2\bar{v_2}+\dots+u_n\bar{v_n}.
  • Check that if A=A^*, then the eigenvalues of A are real. To see this, let u be an eigenvector of A, and consider (Au)\cdot u. In particular, this means that the eigenvalues of a symmetric matrix are real.

More significantly, for any Hermitian matrix A, that is, one that satisfies A=A^*, there is a basis consisting of eigenvectors of A. We will prove this in due time.


170 – Homework 2

February 28, 2013

This set is due Friday, March 8, at the beginning of lecture.

  • Solve problem 2 from Chapter 7. In each case, use the bisection method to approximate within 0.01 a value of x for which we have f(x)=0. Recall that in the bisection method, at each stage we have an interval {}[a,b] and we know that a<x<b and f(a)<0<f(b) (or f(b)<0<f(a)). We let c be the midpoint of the interval. If f(c)=0, we let x=c and we are done. More likely, either f(c)<0, and we have c<x<b, our new interval is {}[c,b], and we iterate the process, or 0<f(c), and we have a<x<c, our new interval is {}[a,c], and we iterate the process.
  • Solve problem 3 from Chapter 7. As before, approximate x within 0.01.
  • Find the first few convergents to \sqrt5, and use them to find \sqrt5 within 0.0001. Recall that the convergents of \sqrt5 are obtained by the following process:

Define a_0,a_1,a_2,\dots so that: a_0 is the largest integer below \sqrt5. Let t_1=1/(\sqrt5-a_0), and let a_1 be the largest integer below t_1. Let t_2=1/(t_1-a_1), and let a_2 be the largest integer below t_2. Let t_3=1/(t_2-a_2), and let a_3 be the largest integer below t_3, etc.

The first convergent to \sqrt5 is the number a_0. The second convergent is \displaystyle a_0+\frac1{a_1}. The third convergent is \displaystyle a_0+\frac1{a_1+\frac1{a_2}}. Etc.

The number \sqrt5 is sandwiched between the convergents, in the sense that it is larger than the first, smaller than the second, larger than the third, smaller than the fourth, etc.

  • Approximate \sqrt2 following the following algorithm: Let x_0 be an arbitrary number that you choose, presumably not too far from \sqrt2. Given x_n, we define a new approximation x_{n+1} by the formula \displaystyle x_{n+1}=\frac{1}{x_n}+\frac{x_n}{2}. Check with the help a calculator that these numbers approach \sqrt2 very quickly. Use this to find the first 10 digits of \sqrt2.
  • Extra credit problem: Why does the algorithm of the last problem work?

Office Hours this week

February 20, 2013

I have a little conflict so I need to start office hours late this week. I also need to leave at 5 to pick up my son, so: Office Hours this Thursday, Feb. 21, are 3:45-5:00. (As usual, please email me if you need to schedule a different meeting time.)


BEST 2013

February 19, 2013

After a short hiatus, the BEST conference is back this year: http://math.boisestate.edu/~best/ The 20th BEST will take place at the University of Nevada, Las Vegas during June 16–19, 2013, as part of the 94th Annual Meeting of the AAAS Pacific Division.

Please email me or Marion Scheepers for further details, and let people who may be interested know. We expect we will be able to offer some (limited) financial support for students and postdocs. I will be posting more details as they materialize.


6th Young set theory workshop

February 19, 2013

The 6th Young Set Theory Workshop will take place this year at the Santuario di Oropa, in Biella, Italy, on June 10th – June 14th.

There will be tutorials by James Cummings, Sy Friedman, Su Gao, and John Steel, and invited talks by Tristan Bice, Scott Cramer, Luca Motto Ros, Victor Torres Perez, and Trevor Wilson.

Here is the official page for the workshop. (I am part of the scientific committee.)


Is mathematics created or discovered?

February 19, 2013

Last Friday, Feb. 15, I had the opportunity to host a Friday Forum discussion at the Honors College on whether Mathematics is created or discovered.

One can address the question from a technical metaphysical point of view, but currently I do not find this approach too illuminating or interesting. This was the path followed by Kit Fine in a talk he gave here about two years ago (April 15, 2011). I commented briefly on Fine’s talk on Twitter: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, and 11:

http://news.boisestate.edu/update/2011/03/23/kit-fine/
I attended yesterday a public lecture by Professor Fine, entitled “Mathematics: Invented or discovered”. The auditorium was packed.
I didn’t like some of the points Fine made, and the direction in which he took the discussion, but there were some interesting highlights.
His conclusion: The heart of mathematics is not axioms but procedures for extending the domain of discourse.
For example, we extend the concept of “number” from “natural” to “integer”, “rational”, “real”, …
Fine introduced a calculus based on dynamic logic for “extension procedures”.
This was the core of his talk, one of the parts I mostly disagreed with. Another: Fine seems to think there “is”, e.g., a unique “number 1”.
(As opposed to: this makes no sense, but there are many essentially equivalent representations.)
A cute detail was his portrayal of constructivism, equating it with writers creating fictional characters.
(It made me think all I do is write fan fiction, which made me smile (snicker?).)
I guess Fine’s conclusion is that mathematics is both invented and discovered as they are different parts of his “extension procedures”.

The Friday Forum was a very nice experience. The problem is complex and has a long history. One of the questions it leads to is how to explain the applicability of mathematics. I consulted several references while preparing for the forum, and I think someone else may find at least some of them useful. Let me list a few. Books:

Papers:


170 – Homework 1

February 8, 2013

Homework 1 is due Friday, February 15 at the beginning of lecture. Select and solve 2 exercises from each of chapters 1-4 in Spivak’s book. Make sure that you find at least one of the exercises in each chapter somewhat challenging (let me know which ones). Please write the statements of the questions. Also, try to write your answers so they can be understood when read by someone else, not just by you, meaning in particular that I want to see sentences, not just symbols, and I want to see your final work, rather than your scratch work.

Aside: I posted on my webpage some examples of graphs produced with SAGE (the 3d graph is here). It may be a good idea to practice with some graphing software and a few unfamiliar graphs, specially from now on, as we start exploring unfamiliar concepts.