Mathematics desk
< March 24	<< Feb \| March \| Apr >>	March 26 >

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

March 25

Circle

Hey all. I was surfing the web, looking for nothing in particular one night, and I came upon a short math quiz on some website. Most of the questions were pretty easy, but there's one that had me stuck. It goes something like, "I have three semicircles, with radii of 3, 2, and 1 unit respectively. The semicircle with radius 2 is externally tangent to the semicircle of radius 1, and both the semicircles of radii 1 and 2 are internally tangent to the one with radius 3. There is a circle which is externally tangent to the semicircles of radii 1 and 2, and internally tangent to that with radius 3. What is its radius?" At first I thought it had something to do with derivatives, but that just led me to a dead end. Thougths? —Preceding unsigned comment added by 99.13.219.136 (talk) 03:15, 25 March 2010 (UTC)[reply]

Just eyeballing it, it looks to be a bit smaller than the radii 1 circle, maybe (3^½)/2 or 0.866 ? StuRat (talk) 03:32, 25 March 2010 (UTC)[reply]

There is no diagram? Hope I'm getting this pictured correctly, the semi-circle (SC) of radius 3 contains SC 1, SC 2, and circle of unknown radius inside. Very interesting, I'll get back to you on that. --Kvasir (talk) 03:49, 25 March 2010 (UTC)[reply]

I'm getting hung up on why they're explicitly semicircles - the way I'm imagining things laid out (r1 & r2 side-by-side hills, r3 joining over them, the circle of unknown radius nestled in the valley between r1 & r2), the problem would be exactly the same if it was circles of radius 1, 2 & 3. The fact that they explicitly mention "semicircles" indicates that this may be a "gotcha" problem, where the "real" way to solve it is not the obvious one. -- 174.21.224.236 (talk) 05:08, 25 March 2010 (UTC)[reply]

I also drew a full R3, R1 and R2 circles thinking it wouldn't change the problem, except there would be 2 of the same unknown circles fitting on either sides of the R1 and R2 circles. I think one of the keys of solving this is to think outside the box and draw the full circles. I think it's still a geometry problem, not a system of equation type question. --Kvasir (talk) 06:05, 25 March 2010 (UTC)[reply]

The arrangement of semicircles you describe is called an arbelos. But I agree that in this case the fact that they're semicircles seems to be a bit of a distraction and it would be simpler to describe with just circles. Descartes' theorem is probably what you're looking for. —David Eppstein (talk) 07:16, 25 March 2010 (UTC)[reply]

I placed the circles in a Cartesian coordinate system so that C3 centre is (0,0) and C1 centre is (2,0), built a three equations system, solved it and got r and Cr centre... Err, is it OK to put the answer here...? --CiaPan (talk) 07:45, 25 March 2010 (UTC)[reply]

I expect Circles of Apollonius helps - but I haven't read it through yet.And Problem of Apollonius is definitely relevant. -- SGBailey (talk) 11:32, 25 March 2010 (UTC)[reply]

I sort of cheated with the help of Autocad, the radius of the circle is approximately 0.8571 unit. (AutoCad can draw a circle given 3 tangent points, so there must be some sort of logarithm.) I'm still trying to look at the geometric relationships there. Stay tuned. --Kvasir (talk) 14:43, 25 March 2010 (UTC)[reply]

That is accurate to 4 decimal places, but there are no logarithms involved, only rational numbers. Gandalf61 (talk) 15:19, 25 March 2010 (UTC)[reply]

oh yeah... I meant to say algorithm, hahah. --Kvasir (talk) 15:33, 25 March 2010 (UTC)[reply]

Hmm check out Bankoff circle. It's nice not needing to re-invent the wheel, so to speak. --Kvasir (talk) 15:42, 25 March 2010 (UTC)[reply]

That article is little more than a stub, and seems to be poorly written, in that the labels in the discussion don't appear to match those in the diagram (C₁, C₂, C₃, vs. C"₆ ?). I also can't follow what they mean by "r = AB/AC". From the diagram, "r = AB" would be correct. Finally, "R", I assume, is the radius of the red circle in the diagram, which is not the one we want. Would anyone be willing to fix this article and diagram ? StuRat (talk) 17:17, 25 March 2010 (UTC)[reply]

Yeah the Bankoff circle is not the circle referred to by the OP. The only thing that is helpful from the article is the diagram illustrating this particular problem here. --Kvasir (talk) 17:32, 25 March 2010 (UTC)[reply]

In case anyone has problem solving it, the exact value confirmed the previous estimation above using Descartes' Theorem suggested above. The answer is 6/7 ~ 0.8571. This was fun. --Kvasir (talk) 17:59, 25 March 2010 (UTC)[reply]

So my hand drawn sketch and eyeballing the answer were off a bit, but 0.866 is pretty good for that kind of estimate (just over 1% off). StuRat (talk) 18:34, 25 March 2010 (UTC)[reply]

Cute problem. I now think I can express the answer in what some might consider "closed form", although it's a bit hairy. Michael Hardy (talk) 21:41, 27 March 2010 (UTC)[reply]

A matrix M raised to the i-th power (i being imaginary), or the natural base raised to the M-th power (M being a matrix).

What is that? Eliko (talk) 10:36, 25 March 2010 (UTC)[reply]

The second one presumably refers to matrix exponential.—Emil J. 11:11, 25 March 2010 (UTC)[reply]

... and for the first one, if M has a matrix logarithm then the natural way to define Mⁱ would be Mⁱ = exp(i log(M)). Gandalf61 (talk) 11:15, 25 March 2010 (UTC)[reply]

...but that's not unique (even if it exists), is it?—Emil J. 11:21, 25 March 2010 (UTC)[reply]

No. Relatedly, e^M could be interpreted to mean exp(M log(e))=exp(M (1+2niπ)), which is also multivalued, with the standard matrix exponential as one of its values. Algebraist 11:42, 25 March 2010 (UTC)[reply]

For a sufficiently well-behaved matrix, you can use the principal logarithm. -- Meni Rosenfeld (talk) 11:46, 25 March 2010 (UTC)[reply]

So ? The i-th power of a real or complex number isn't unique either, for the same reason. Gandalf61 (talk) 12:16, 25 March 2010 (UTC)[reply]

Eliko, you say on your user page that you're a native speaker of English. Please get clear on this: it's a matrix, not a "matrice". The plural of "matrix" is "matrices". Michael Hardy (talk) 02:44, 27 March 2010 (UTC)[reply]

Yes, you are right. I've fixed it. Eliko (talk) 21:34, 27 March 2010 (UTC)[reply]

Dissections in Riemann Integration

Hi. I'm currently going through my notes on an Analysis course and am a bit confused on a Lemma regarding dissections. It says

"If D₁ and D₂ are any two dissections then $S(f,D_{1})\geq S(f,{D_{1}}\cup {D_{2}})\geq s(f,{D_{1}}\cup {D_{2}})\geq s(f,D_{2})$ , where S(f, D) denotes the upper sum of f wrt D and s(f, D) the lower sum."

My main problem comes from the two extremes, ie that $S(f,D_{1})\geq s(f,D_{2})$ . If we know nothing about these dissections then how can we make such a statement? Thanks. 92.11.43.155 (talk) 15:38, 25 March 2010 (UTC)[reply]

Any upper sum is greater than the integral, and any lower sum is less than the integral, so any upper sum is greater than any lower sum.

This of course is an intuitive explanation for cases when the integral exists - for a proof in the general case, that's exactly what the lemma gives. -- Meni Rosenfeld (talk) 16:48, 25 March 2010 (UTC)[reply]

Thank you Meni! 92.11.43.155 (talk) 17:42, 25 March 2010 (UTC)[reply]

Two dimensional representation of an arbitrary distance matrix

Given a set of items and a complete set of arbitrary pairwise "distances" between them (with the property that d(a,b) = d(b,a)), is there a technique for assigning 2D positions to them, such that the set of pairwise 2D euclidean distances "best" (e.g. in a least squares/expectation maximization sense) matches the set of starting distances? -- 174.21.224.236 (talk) 17:03, 25 March 2010 (UTC)[reply]

Would you want to keep all the distances, or toss out those that don't fit with the rest ? StuRat (talk) 18:30, 25 March 2010 (UTC)[reply]

Yes. From the distance matrix compute a kernel matrix, apply kernel PCA and take the first two components.

To find the kernel matrix, enumerate the items as

\{v_{1},\ldots ,v_{n}\}

. Let

S_{i}=\sum _{j}d(v_{i},v_{j})^{2}\;\!,

S={\frac {\sum _{i}S_{i}}{2n}}\;\!,

\|v_{i}\|^{2}={\frac {S_{i}-S}{n}}\;\!.

Then

K_{i,j}=(\|v_{i}\|^{2}+\|v_{j}\|^{2}-d(v_{i},v_{j})^{2})/2

.

Note that your distance matrix should satisfy the triangle inequality - otherwise the results may be unpredictable.

This is closely related to Nonlinear dimensionality reduction, you may find some relevant information there. -- Meni Rosenfeld (talk) 19:32, 25 March 2010 (UTC)[reply]

Thanks! Nonlinear dimensionality reduction was what I was looking for. A few followup questions: In the proceedure you suggest, am I correct in stating that you transform the distance matrix with the kernel K, and then do PCA on the transformed matrix? If so, I'm a little confused on how to use the first two principle components to compute the (x, y) positions of the original points. For principle component vectors C₁ and C₂, is the coordinate for item v_i simply ( C_1,i, C_2,i), or do I have to "backtransform" the components through the kernel? Additionally, is there a particular reason you selected kernel PCA from the list of techniques at nonlinear dimensionality reduction, and how did you select the kernel function? Finally, the matrix is only "distances" in that it's somewhat analogous to a separation between the two objects. I'm uncertain whether they will always satisfy the triangle inequality. Is there a (simple) way around that, or what do you mean by "unpredicable"? -- 174.31.194.126 (talk) 16:32, 26 March 2010 (UTC)[reply]

The orthogonal diagonalization of K will give you

K=UDU^{-1}

where

U^{T}U=I

and the diagonal entries of D are with decreasing magnitude. Letting

C_{1},\ C_{2}

be the first two columns of U and

\lambda _{1},\ \lambda _{2}

be the corresponding eigenvalues, the coordinates of point i are

\left((C_{1})_{i}{\sqrt {\lambda _{1}}},(C_{2})_{i}{\sqrt {\lambda _{2}}}\right)

.

The techniques of dimensionality reduction typically deal with data that is explicitly embedded in some high-dimensional Euclidean space, and they construct a distance matrix as part of the solution. If this is your "real" problem they may all be applicable, but you have given the distance matrix as part of the problem.

The kernel I've described is the matrix of inner products in the hi-dim Euclidean space in which the data is embedded (if there is one, and assuming wlog that the mean of all points is 0). So the output of the kernel PCA will be equivalent to the projection to a 2-dimensional subspace with the minimal total distance of the points from their projection.

If there is no triangle inequality, the points are not embedded in an Euclidean space and the theory behind PCA is void. The kernel matrix will have negative eigenvalues. It might still work and you may get good results, but I wouldn't count on it.

Multidimensional scaling is based on a different optimization criterion and it might be more suitable for arbitrary dissimilarity matrices (maybe the end result is the same for both, I'm not sure).

If the only distances that are meaningful are local, between nearby points, then Isomap and MVU are worth a look. Others might be good too but I have no familiarity with them (as opposed to these two with which I have little). -- Meni Rosenfeld (talk) 20:32, 27 March 2010 (UTC)[reply]

Perhaps I'll say a few more words on how this works.

PCA does the following:

Start with an $m\times n$ matrix X, representing a set of n points in $\mathbb {R} ^{m}$ whose total is 0.
Calculate the kernel matrix $K=X^{T}X$ .
Let $K=UDU^{-1}$ , $Y=D^{1/2}U^{T}$ .
It can be shown that Y (as a matrix whose columns represent vectors) is just a rotation of X, so they are geometrically equivalent. However, in Y the entries are uncorrelated and are in decreasing significance, so you can take $k$ entries of each vector and obtain a low-dimensional approximation for the data.

Kernel PCA is the same, but there is no explicit embedding in hi-dim space; rather, you obtain the kernel matrix some other way, and it represents what

X^{T}X

would be if you did embed the data explicitly. Taking all components will give you an n-dimensional embedding of just those n-points, equivalent to the subspace spanned by those points in some even higher-dim space. Taking a few components will give you an approximation, as usual.

Any positive semidefinite matrix K is valid. However, you need every row of K to sum to 0 (corresponding to the vectors totaling 0), if it's not this way to begin with you need to use the trick described in Kernel PCA to make it so.

In my response I have used the matrix that follows necessarily if we assume that all distances given should be observed. Many dim-reduction methods assume that only local distances need to be observed, and the key step is constructing a kernel which observes the local distances and "unfolds" the data to describe the global structure with as few dimensions as possible. -- Meni Rosenfeld (talk) 09:58, 28 March 2010 (UTC)[reply]

Normed field

I am looking at a problem in a book, which I know how to do, except that I wonder if the question is slightly off. The full question is:

Prove that in a normed field the following assertion holds: Let <a_n> be a Cauchy sequence, but not a null sequence. Prove there exist a number c > 0 and a positive integer N such that for all n > N either a_n > c or a_n < -c.

My question is, does the very last part make sense in an arbitrary normed field, a_n > c or a_n < -c? It does not say c is a real number. It just says it is a number, which could mean a field element. I mean, I think I can think of a counterexample, which would be the field of 2 elements with trivial norm and the sequence 1, 1, 1, 1, ... which is Cauchy but not null. However, there is no such c. I guess in such a field c > 0 may not even make sense? I don't know. What's going on here? Thanks! StatisticsMan (talk) 17:52, 25 March 2010 (UTC)[reply]

What, in the opinion of your book, is a normed field? Algebraist 17:59, 25 March 2010 (UTC)[reply]

(e/c) The statement as given only makes sense in an ordered field (interpreting c as a field element rather than a real number), and for it to hold you'd also need some compatibility conditions linking the order to the norm (which, I suspect, would imply that the field is Archimedean, and therefore a subfield of the reals, so you are back to square zero). Presumably the book wanted to say that the norm of a_n is at least c.—Emil J. 18:11, 25 March 2010 (UTC)[reply]

...where, with regard to Algebraist's question, I assumed that a normed field means a field equipped with an absolute value (algebra).—Emil J. 18:23, 25 March 2010 (UTC)[reply]

The book definition of a normed field is a field with a norm on it. The definition of field and norm are standard. Now that I've thought about it, I believe it's just that the author took a theorem about real numbers and didn't think to change it to work for a general normed field. So, I assume it should just be changed to "there exists a REAL number c > 0" and "such that for all n > N we have ||a_n|| > c". Thanks for your help. StatisticsMan (talk) 23:59, 25 March 2010 (UTC)[reply]

Periodic formula of an EKG shape?

Are there any formulas that would give me a repeating EKG type shape? --70.167.58.6 (talk) 19:07, 25 March 2010 (UTC)[reply]

A function of the form

f(t)=a_{0}+\sum _{k=1}^{n}(a_{k}\cos(k\omega t)+b_{k}\sin(k\omega t))

should give a good fit. The parameters

\omega ,a_{k},b_{k}\;\!

can be computed from data. See also Fourier series and Fourier transform. -- Meni Rosenfeld (talk) 19:40, 25 March 2010 (UTC)[reply]

In reality though, the heartbeat is never perfectly periodic; although it is often very close. We are all human and we all have quirks in our workings. A Fourier Series expansion is only any good for a short term model, under constant conditions. For example, the subject must not move, must not sleep, must not get excited, etc. •• Fly by Night (talk) 23:18, 25 March 2010 (UTC)[reply]

Reverse engineering a graph

This is a broader follow up to my question above. Are there any websites or apps that can reverse engineer a graph? For example, I draw my EKG shape in vector with Adobe Illustrator. Could I upload that image to a site that would spit out a trig formula that is similar to that curve? If I do it with a vector app, would there be some sort of PostScript data I could extract to make that curve as a trig function? --70.167.58.6 (talk) 19:12, 25 March 2010 (UTC)[reply]

Curve fitting has links, and says that it's a common feature for statistical programs. -- Finlay McWalter • Talk 19:16, 25 March 2010 (UTC)[reply]

Since the function is known to be roughly periodic, the generic techniques in that article are not the right tool for the job. You should attempt a Fourier transform. -- Meni Rosenfeld (talk) 19:44, 25 March 2010 (UTC)[reply]

Number of non-isomorphic graphs in n vertices?

Is there a known result to the following question; How many graphs are there in n vertices such that all of the graphs are non-isomorphic to each other graph? A math-wiki (talk) 23:49, 25 March 2010 (UTC)[reply]

OEIS: A000088. —David Eppstein (talk) 00:18, 26 March 2010 (UTC)[reply]

I figured as much, most of what that linked to was beyond my knowledge but em I correct in thinking the formula for the sequence they arrived at was $f(n)={\frac {2^{\frac {n(n-1)}{2}}}{n!}}$ A math-wiki (talk) 00:51, 26 March 2010 (UTC)[reply]

No. Stopping reading a formula at the first * sign is not a good route to understanding it. Algebraist 01:06, 26 March 2010 (UTC)[reply]

Then I must inquire as to what my result is missing. I arrived at that formula via a counting argument. I first asked how many possible edges (max) does a graph of n vertices have? This can by shown to be the sum of the first n-1 integers greater than 0 or ${\frac {n(n-1)}{2}}$ from the formula for sum of the first n integers. Then when thinking about the 'edge list' for any graph of n vertices any of those edges is either present or absent, and this there are 2 choices per edge in the 'list' and furthermore these choices are independent of each other. This gives $2^{\frac {n(n-1)}{2}}$ possible lists. This however counts the same graph numerous times as their are multiple ways to name some graphs (e.g. symmetric graphs) such that their 'edge list' remains unchanged, and furthermore there are different 'edge lists' that are, in fact, isomorphic to one another. The number of times each graph counted is precisely the number of ways its vertices can be named, since for any graph to be isomorphic to another, their must exist a bijection between their vertices that preserves their 'edge list.' Naming them from an ordered list (e.g. 1,2,3...) we can see their are n choices for the first name, n-1 for the second and so forth, so their are n! was to name each graph, so I concluded that $f(n)={\frac {2^{\frac {n(n-1)}{2}}}{n!}}$ gave the correct count for n vertices (not at most n, exactly n) It doesn't consider graphs with loops or with multiple edges between the same pair of vertices, but it does allow for non connected graphs and lone vertices with no edges connected with them. A math-wiki (talk) 02:00, 26 March 2010 (UTC)[reply]

If every graph were asymmetric (like the Frucht graph, having no nontrivial graph automorphisms), then

{\frac {2^{\frac {n(n-1)}{2}}}{n!}}

would be the correct formula: there are

2^{\frac {n(n-1)}{2}}

ways of writing down an adjacency matrix for a graph, and n! different adjacency matrices that result from the same graph. But when a graph has some symmetries, then there are fewer adjacency matrices that it can generate. Most graphs (in a technical sense, almost all of them) are asymmetric, so the formula is close to accurate, but it is not exact. The precise correction terms needed for situations like this, where you're trying to count things that may have symmetries, are given by the Pólya enumeration theorem.

There's also a very simple explanation for why your formula can't possibly be the correct answer: it's not an integer. The numerator has only factors of two in its prime factorization, while the denominator has other prime factors that can't be cancelled by anything in the numerator. As a non-integer it can't be the answer to a counting problem such as this one. —David Eppstein (talk) 02:39, 26 March 2010 (UTC)[reply]

Ok, that makes sense now, I should've noticed that it'd give non-integer answers most the time. A math-wiki (talk) 15:55, 28 March 2010 (UTC)[reply]