September 2010 - mathfun@mailman.xmission.com

[math-fun] Singular value decomposition
by Dan Asimov 09 Sep '10

09 Sep '10

The discussion about polar decomposition reminds me of an interesting interpretation of the SVD that isn't often mentioned: Let P, Q be two K-dimensional planes in R^L. To describe their relative position in R^L, it suffices to find the smallest angle theta_1 between any vector v in P and any vector w in Q; then to iteratively do the same for <v,w>^perp. (I.e., in the space <v,w>^perp we find the least angle between the subspaces (P \int <v,w>^perp) and (Q \int <v,w>^perp). This gives a sequence of angles theta_1,...,theta_K. (If P and Q intersect nontrivially, some of these will be 0.) Associated to these angles there are also orthonormal bases for P and Q consisting of the vectors that were found to be nearest. Now consider any orthonormal bases V = (v_1,...,v_K) of P and W = (w_1,...,w_K) of Q. Form their dot-product matrix: M = V^t W whose (i,j)th entry is v_i*w_j. Then by twiddling these bases by orthogonal matrices R, S, to get new bases VR and WS, it can be arranged that (VR)^t (WS) = D where D is diagonal with elements d_j = cos(theta_j) for all j = 1,...,K. Hence R^t V^t W S = D, so V^t W = R D W^t, i.e., M = R D W^t. The singular values -- the (necessarily nonnegative) cosines of the theta_j's that are the elements of D -- satisfy: M^t M = W D R^t R D W^t = W D^2 W^t and so the singular values are the square roots of the eigenvalues of the (symmetric positive semi-definite matrix) M^t M. --------------------------------------------------------- Thus the singular values are a complete set of invariants for the relative position of the K-planes P and Q in R^L. I.e., given any rotation O of R^L, then starting with the subspaces OP and OQ in the above will result in the same D, and conversely. --------------------------------------------------------- --Dan _____________________________________________________________________ "It don't mean a thing if it ain't got that certain je ne sais quoi." --Peter Schickele

1 0

[math-fun] Polar Decomposition
by Fred lunnon 09 Sep '10

09 Sep '10

In numerous recent publications, it is claimed that the "polar decomposition" of a (real) matrix M = Q S as the product of orthonormal ("orthogonal") and symmetric factors is unique, at any rate provided M is nonsingular. See for example http://en.wikipedia.org/wiki/Polar_decomposition or the very readable (and available for free download) Ken Shoemake, Tom Duff "Matrix Animation and Polar Decomposition" As it stands, the claim is obviously false. A trivial example is M = [[0,1],[1,0]] which factorises as M I or as I M. There is no mention of uniqueness on page 6 of Gantmacher "Theory of Matrices" vol 2 though he does point out that the factors commute if M commutes with its transpose, as in the counterexample above. The claim of uniqueness may be possibly result from confusion connected with the Higham 1986 reference in Shoemake, where there is an algorithm giving Q such that Q - M has minimal 2-norm. Can anyone cast light on this? Is the decomposition unique under the minimality constraint? Are there less onerous constraints guaranteeing uniqueness (and minimality)? Have I simply misunderstood something, or is this another rhinoceros' pancreas? Fred Lunnon

3 4

[math-fun] polar decomposition
by Jean Gallier 08 Sep '10

08 Sep '10

Dear Fred, The confusion has to do with the fact that there are two polar decompositions: M = QS_1 M = S_2Q where Q is orthogonal and S_1, S_2 are symmetric, POSITIVE semi-definite. In general, S_1 \not= S_2. The matrix M = [[0, 1], [1, 0]] has eigenvalues +1 and -1, so it is not positive and only the decomposition M I is acceptable. If M is invertible, then these decompositions are unique. If M is normal, then S_1 = S_2. Proofs can be found as early as in Chevalley, Theory of Lie Groups , 1946. I have a proof in my book (Chapter 12, Thm 12.1.3): http://www.cis.upenn.edu/~cis610/geombchap12.pdf I hate to say this but Ken Shoemake (who was once a student at UPenn is not a very reliable source. Best, -- Jean Gallier

2 1

[math-fun] polar decomposition
by Jean Gallier 08 Sep '10

08 Sep '10

Sorry, I should have mentioned, the "bible" Matrix Analysis, Vol 1, by Horn and Johnson, see pages 411-415. Best, -- Jean Gallier

1 0

Re: [math-fun] Polar Decomposition
by Henry Baker 08 Sep '10

08 Sep '10

Perhaps "unique" means unique only once you choose whether you want the symmetric matrix on the left or the right? At 03:26 PM 9/8/2010, Fred lunnon wrote: >In numerous recent publications, it is claimed that the "polar decomposition" >of a (real) matrix M = Q S as the product of orthonormal ("orthogonal") >and symmetric factors is unique, at any rate provided M is nonsingular. > >See for example > http://en.wikipedia.org/wiki/Polar_decomposition >or the very readable (and available for free download) > Ken Shoemake, Tom Duff "Matrix Animation and Polar Decomposition" > >As it stands, the claim is obviously false. A trivial example is > M = [[0,1],[1,0]] >which factorises as M I or as I M. > >There is no mention of uniqueness on page 6 of > Gantmacher "Theory of Matrices" vol 2 >though he does point out that the factors commute if M commutes with its >transpose, as in the counterexample above. > >The claim of uniqueness may be possibly result from confusion connected with >the Higham 1986 reference in Shoemake, where there is an algorithm giving Q >such that Q - M has minimal 2-norm. > >Can anyone cast light on this? >Is the decomposition unique under the minimality constraint? >Are there less onerous constraints guaranteeing uniqueness (and minimality)? > >Have I simply misunderstood something, or is this another rhinoceros' pancreas? > >Fred Lunnon

1 0

[math-fun] Recursive tiling
by Robert Munafo 07 Sep '10

07 Sep '10

Thanks for the reply Bill -- I looked at those PDFs when you sent them last week. They are part of the reason I asked my question. My simplistic pentagon-triangle tiling came out of this discussion I had with a reader back in 2004: http://www.mrob.com/users/ivan-freyman/20040506.html I see how "my" tiling is related to your spacefilling rules, and if I am tracing the curve correctly, I would guess that your "hemis.gif" example is using the trapezoid (hemi-hexagon) rep-tile rule (as seen in the image http://www.mrob.com/users/ivan-freyman/www.armcorp.us/200405-trapezoid.gif) As you can see from those images, my purpose for tilings is related to computer art. It does not matter to me whether there is "a fixed number of different tiles" (as Tom Karzes points out), or that "density variations [...] become unbounded in the limit" (Bill Gosper, referring to his pentagonfill.pdf) because the computer can be programmed to subdivide a tile only when that tile is larger than a desired minimum size. Of course, I knew about the various Penrose tilings but I wanted the artwork to contain actual regular pentagons, and for aesthetic reasons only one other shape which would be an isosceles triangle. I was expecting someone would reply and say "oh, that's a Jenkins quasi-foo tiling, read his 1962 paper" or "that's a class B3 recursive quux tessellation", but apparently there is as yet no such nomenclature. I suppose it is because these tilings have little application beyond art. Marjorie Rice's page (on archive.org here: http://web.archive.org/web/20071011074636/home.comcast.net/~tessellations/t… ) looks familiar, at any rate seems to cover well-known territory (see e.g. http://www.mathpuzzle.com/tilepent.html) - Robert On Mon, Sep 6, 2010 at 03:53, Bill Gosper <billgosper(a)gmail.com> wrote: > This is precisely the tiling behind > www.tweedledum.com/rwg/pentagonfill.pdf and > http://gosper.org/pentfill.pdf . (And that stick-length illusion.) > > Martin Gardner once fowarded me a set of ingenious but cryptic > frac-tiles by Ammann. I don't know where they are, so I hope > someone else has a copy. They all lead to spacefills, probably of > the pentfill type, since they were based on algebraic numbers. > Martin was intrigued by Ammann's constantly shifting return address, > and repeatedly requested some biographical data. Ammann finally > replied that he was a parking lot attendant. Uh-huh. > > Here's an easy one with two equal tiles. Your hemispheres are > not quite alike: www.tweedledum.com/rwg/hemis.gif . > > I think I've finally figured out that pentagram snowflake S. > Witham found (and my tutors rediscovered) in Minsky rug plots. > Has anybody else worked on it? > --rwg On Thu, 19 Aug 2010, Bill Gosper wrote: > Yesterday I told tutor Julian an idea for spacefilling a pentagon, and he said I could > just conformally map Peano's filled square onto whatever, but then he got into it and > helped make www.tweedledum.com/rwg/pentagonfill.pdf . It self-contacts, but the median > curve doesn't. Note the density variations, which become unbounded in the limit. I > don't have a fix, but I can turn a slight variant of this one into one of those exact > continuous maps of the rational unit interval onto some dense set of algebraic > points. This would permit sampling at various frequencies and phases, which has proven > interesting in previous cases (www.tweedledum.com/rwg/sampeano.htm, > www.tweedledum.com/rwg/sam306090.htm ). > --rwg -- Robert Munafo -- mrob.com -- twitter.com/mrob_27

1 0

[math-fun] Combinatorics of continued fractions?
by Mike Stay 07 Sep '10

07 Sep '10

Generating functions have a pretty clear combinatorial interpretation: the coefficient on x^n is the number of ways to put a particular structure on an n-element totally ordered set. Is there any clear combinatorial interpretation of the terms of a simple continued fraction? -- Mike Stay - metaweta(a)gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com

3 4

[math-fun] Can you please tell me the name of this pretty group?
by Marc LeBrun 06 Sep '10

06 Sep '10

Can any of you please tell me the name of this pretty group? 0 1 2 3 4 5 6 7 1 0 4 5 2 3 7 6 2 4 0 6 1 7 3 5 3 5 6 0 7 1 2 4 4 2 1 7 0 6 5 3 5 3 7 1 6 0 4 2 6 7 3 2 5 4 0 1 7 6 5 4 3 2 1 0 What do you think would be the best way of answering similar queries? Thanks! --MLB

3 3

[math-fun] Robert Ammann [was Help wanted ...]
by Bill Gosper 06 Sep '10

06 Sep '10

DanA>RWG wrote: << Martin was intrigued by [Robert] Ammann's constantly shifting return address, and repeatedly requested some biographical data. Ammann finally replied that he was a parking lot attendant. Uh-huh. >> < http://en.wikipedia.org/wiki/Robert_Ammann > Apparently he was a very smart guy who didn't have professional training. Another such story with Marjorie Rice: < http://en.wikipedia.org/wiki/Marjorie_Rice >. There's something about tiling. --Dan -------------------------- There's a nice segment on Rice in http://www.youtube.com/watch?v=eAGKzFDxmUA . (Or maybe part 5. I don't have the bandwidth to check.) Following the Ammann Wiki Amateur Mathematicians link leads to: In 1876, [President-to-be James A.] Garfield discovered a novel proof[41] of the Pythagorean Theorem using a trapezoid while serving as a member of the House of Representatives.[42] I wonder what that idiot assassin deprived us of. --rwg

3 2

Re: [math-fun] Can you please tell me the name of this pretty group?
by N. J. A. Sloane 06 Sep '10

06 Sep '10

Marc, I already sent you this, a week ago! Neil It is abelian (table is symmetric), and every element squares to the identity There for it is C2 X C2 X C2, the direct product of three cyclic groups of order 2 If wrutten additively, it is the additive group of binary vectors of length 3 Your name My name 0 000 1 001 2 010 1+2=4 011 3 100 1+3=5 101 2+3=6 110 1+6=7 111 if you exchange the names of 3 and 4, then you can just write your name in base 2 to get my name! Best regards Neil

1 0