Wikipedia:Reference desk/Archives/Mathematics/2008 February 7

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.

February 7

Singular Value Decomposition

Suppose that I want to decompose ${\begin{bmatrix}3&0\\0&-2\end{bmatrix}}$ using singular value decomposition. So I define $B=A^{T}A={\begin{bmatrix}9&0\\0&4\end{bmatrix}}$. Since B is a diagonal matrix, the eigenvalues of B are simply the diagonal entries so I label the singular values of A as $\lambda _{1}=3,\,\lambda _{2}=2$. So the right and left eigenvectors are just $e_{1}$ and $e_{2}$ and their transpose. So the decomposition comes out to:

${\begin{bmatrix}3&0\\0&-2\end{bmatrix}}={\begin{bmatrix}1&0\\0&1\end{bmatrix}}{\begin{bmatrix}3&0\\0&2\end{bmatrix}}{\begin{bmatrix}1&0\\0&1\end{bmatrix}}$ which is obviously not true because of the minus sign in front of 2 in our original matrix A. So the question is how are these eigenvectors chosen. I know that this decomposition is not unnique. Since, there is an infinite number of left and right singular vectors to choose from, how do we choose the eigenvectors? I thought, the standard was to choose some unit vector but that still seems not to be enough. A Real Kaiser (talk) 04:41, 7 February 2008 (UTC)

Let's see. $A=VBU$. In the case of distinct singular values, V is determined uniquely up to multiplying by some diagonal matrix of unimodular values on the right. For square matrices and a fixed B and V, U is uniquely determined. In this case, once you had chose to use the identity on the right, you would have been forced to choose the diagonal matrix with 1 and -1 on the left. You must always use unit eigenvectors to make U and V unitary, and I believe the procedure is to choose V and then find U. This is in Johnson and Horn, Matrix Analysis, Theorem 7.3.5. (Sorry, I know that this could use some wikilinks) 134.173.92.17 (talk) 05:58, 7 February 2008 (UTC)

Real Analysis

On a completely different note, let $\Omega$ be a set and let F be a $\sigma$-algebra on $\Omega$. Let $\mu$ be any measure on $(\Omega ,\,F)$. In my real analysis class, our teacher told us that if ${A_{n}}$ is a nested decreasing sequence in F (meaning $A_{n}\subset A_{n+1}$) then we have that

$\mu (\cap _{n=1}^{\infty }A_{n})=\lim _{n\rightarrow \infty }\mu (A_{n})$

The question is that is this still true if $\mu (A_{1})=+\infty$? If not, can anyone provide a counterexample because I think that this would be false if the measure of $A_{1}$ is infinite to begin with. A Real Kaiser (talk) 05:00, 7 February 2008 (UTC)

Example 1.20 (c) in Rudin's Real and Complex Analysis, Third Edition: "Let $\mu$ be the counting measure on the set $\{1,2,3,\dots \}$, and let $A_{n}=\{n,n+1,n+2,\ldots \}$. Then $\bigcap A_{n}=\emptyset$ but $\mu (A_{n})=\infty$". —Preceding unsigned comment added by 134.173.92.17 (talk) 05:42, 7 February 2008 (UTC)

Just a small correction: If it's a nested decreasing sequence, then you mean $A_{n}\supset A_{n+1}$. —Bkell (talk) 06:14, 7 February 2008 (UTC)

That is of course what I meant. Thanks a lot. I actually have the book and this is exactly what I was looking for. Awesome!

A Real Kaiser (talk) 06:36, 7 February 2008 (UTC)

Points on a plane

If I give a number of random points and asked them to be expressed by an equation. (i.e. the points must be able to be crossed by an shape that is able to be defined by an equation. As in, a line, parabola, the edge of a square. etc.) What is the maximum number of points for which there is definitely an equation to express them? I know that it is possible to use a circle to express 3. Is it possible to express 4? Thanks ahead of time. 99.226.39.245 (talk) 05:20, 7 February 2008 (UTC)

Well, for any finite number of points, you can always find a polynomial that goes through all of those points. Just like how you need a straight line to go through two points, you need a parabola to go through three points. So, if you give me any arbitrary n points (that are distinct, of course), I can always find at least one polynomial of degree n-1 that goes through all of those points.A Real Kaiser (talk) 06:38, 7 February 2008 (UTC)

A Real Kaiser is correct, but the resulting polynomial may be very ugly. --Gerry Ashton (talk) 07:45, 7 February 2008 (UTC)

It would be best to read the article Polynomial interpolation (and probably Interpolation) for the actual equation. --Martynas Patasius (talk) 14:05, 7 February 2008 (UTC)

That article only talks about polynomials in one variable (ie. y=P(x)), which makes it impossible to have two points with the same x coordinate. Certainly in some cases it is possible to use a polynomial in both x and y to go through points in the same vertical line (eg. given points (1,0),(0,1) and (0,-1) the polynomial x^2+y^2=1 goes through them), is that always possible? --Tango (talk) 17:30, 7 February 2008 (UTC)

Sure. If you want to go through $(x_{1},y_{1}),\ldots (x_{n},y_{n})$ say, just use the equation $(x-x_{1})\ldots (x-x_{n})=0$ (say). It's not very edifying, but it's a polynomial equation, as desired. Algebraist 18:22, 7 February 2008 (UTC)

Or you could use $\prod _{i=1}^{n}((x-x_{i})^{2}+(y-y_{i})^{2})=0$, which gives you exactly the points you want. Algebraist 18:29, 7 February 2008 (UTC)

A more interesting version of your question is whether, given finitely many points in the plane, there exists an algebraic variety containing all of them. I strongly suspect that there is, but can't immediately see how to prove it and can prove it. Just transform co-ordinates by rotating the axes slightly until no two points share the same x co-ordinate and use the Kaiser's idea. Algebraist 18:34, 7 February 2008 (UTC)

Thank you! 99.226.39.245 (talk) 21:49, 10 February 2008 (UTC)

Fitting regular polygons inside each other

Is there any existing proof out there proving that it's impossible to fit EXACTLY (all corners must touch a side) a regular pentagon inside a square? or a regular pentagon inside a regular hexagon?

What about a general test to determine if a polygon with X equal sides can fit EXACTLY inside another polygon with (X+1) or (X-1)equal sides?

Oh, yeah is there any special name to the polygons with such relationship? --Kvasir (talk) 18:40, 7 February 2008 (UTC)

My initial thought for the first one (the others are probably similar) is that it can't be done because the circle circumscribing the pentagon would intersect the square 5 times. Assuming the square and pentagon are concentric (I doubt it will work in the non-concentric case, but can't prove it yet), the circle would intersect the square an equal number of times on each side, by symmetry, so that's 0, 4 or 8 intersection points. So you have to go with 8 (the only one bigger than 5), and those 8 points will have a rotational symmetry of order 4, so I think that would end up requiring the pentagon to have a 4-symmetry, which it doesn't. So basically, you end up needing an n-gon to have a rotational symmetry of order n-1, which is only the case for n=2, which isn't really a polygon. I'm not 100% sure on that last bit, and I can't think of how to approach non-concentric polygons, but I think that's almost an answer to your question. --Tango (talk) 21:19, 7 February 2008 (UTC)

I think you can fit a pentagon in a hexagon by putting a vertex of one in a vertex of the other. Black Carrot (talk) 22:00, 7 February 2008 (UTC)

OK how do you prove that such a hexagon exist Black Carrot? or any other polygon with n>=5?

I should rephrase the question. The polygons need not be concentric. I should illustrate it better as I have already tried it both ways:

A: This is to fit the largest possible (n+1)-gon inside n-gon. Start with a circle (n=1) of a given area, then insert a triangle (n=3, n=2 doesn't form a regular polygon), then a square (n=4) inside the triangle. But there is no way to fit a regular pentagon (n=5) inside the square where all 5 vertices touch the square. Has anyone proven that it's impossible? Has anyone proven that the fitted (n+1)-gon has the maximum area when it is fitted inside the n-gon this way?

B: This is to enclose an n-gon with the smallest possible (n+1)-gon. Start with a circle of a given area, then enclose it with a triangle where the circle intersect the triangle exactly 3 times. Then the triangle is fitted inside a square; and the square is fitted inside a pentagon. I can only get this far, I could not get the pentagon to fit inside any hexagon where all 5 vertices end up on the sides of hexagon. Similarly, has anyone proven that it's impossible to fit a regular pentagon inside a regular hexagon? Has anyone proven that the fitted (n+1)-gon has the minimum area?

A related part of the question would be a generic formula to get the area of n-gon that fits exactly inside (n-1)-gon or (n+1)-gon of a given area, if it exists. --Kvasir (talk) 22:12, 7 February 2008 (UTC)

Here's a simple proof that you can't fit a regular pentagon inside a square in the way you describe. Suppose a regular pentagon fits inside a rectangle (which might be a square) so that all five vertices of the pentagon touch a side of the rectangle. Then one side of the rectangle must touch two vertices of the pentagon, so one of the sides of the pentagon must be part of one of the sides of the rectangle. Then obviously the other three vertices of the pentagon must touch the other three sides of the rectangle. Now consider the distance between parallel sides of the rectangle. One set of parallel sides is separated by the distance from a vertex of the pentagon to the midpoint of the opposite side of the pentagon, and the other set of parallel sides of the rectangle is separated by the distance between two nonadjacent vertices of the pentagon. Plainly these distances are not equal, so the rectangle is not a square. (This would be a lot easier to describe with a picture, but hopefully this is clear.) —Bkell (talk) 06:01, 8 February 2008 (UTC)

I was imagining it wrong. I tried to draw it, and it didn't work. Incidentally, part of what Bkell suggested works for all polygons. To fit an n+1gon inside an ngon, they must share a side. That is, a side of the inner one must be part of a side of the outer one. Imagine this side at the bottom, flat to the ground. Both shapes have a vertical axis of symmetry. If the inner one is touching the outer one correctly on both sides, their axes of symmetry must match, so the inner one must be centered on the bottom of the outer one. That means there's only one diagram to work out for each n, which isn't bad. (BTW, this isn't true for a triangle on the inside, since it doesn't have two points to compare to each other, and it isn't true for a square on the inside if the outer shape has a flat top. Not that a pentagon does, but still.) Black Carrot (talk) 06:30, 8 February 2008 (UTC)

A similar argument applies if the two polygons share a vertex, call it A. Imagine A at the bottom. For each pair of symmetric vertices of the inner one, there's a circle centered at A and going through both of them that can only (I think) intersect the outer polygon in two points, which will be symmetric with each other. If the inner polygon hits both these points, its axis of symmetry must be vertical. Black Carrot (talk) 06:38, 8 February 2008 (UTC)

That last one works best if you choose the two vertices adjacent to A. Black Carrot (talk) 07:14, 8 February 2008 (UTC)

Ok this is what I should've uploaded at the start. Yes, this does illustrate why (n+1)-gon can't fit inside an n-gon except for a square inside a triangle as Bkell explained. What about the other way? fitting an n-gon inside an (n+1)-gon? As you can see I've gotten as far as a pentagon. Is there a proof that the pentagon is the smallest there is to enclose the square? How can one disprove or prove that a hexagon in this series exist? I'm surprised no Chinese or Greek mathematician has pondered over this before. --Kvasir (talk) 15:59, 8 February 2008 (UTC)

Bkell's argument doesn't prove it can't be done for an n+1gon in an ngon (other than pentagon in square), it just shows that there's only one diagram to consider. You'd still have to work out the measurements. Black Carrot (talk) 19:03, 8 February 2008 (UTC)

I suppose I'm not looking for THE proof per se, more like a reference of someone who have worked this out before or at least have a name of this series of polygons. Hey may be I can make a thesis out of it! I'm currently working out a proof whether or not a hexagon exist, and if it does, if a heptagon exist, and so on. So far i've proven that no hexagon exists if any of the spaces between the hexagon and the pentagon form a quadrilateral. If such a hexagon exists, there must be five triangles formed in the spaces between the hexagon and the pentagon. --Kvasir (talk) 06:32, 9 February 2008 (UTC)

I can't help you with references, but I'd be surprised if nobody's worked out the answer before. Since I ran out of ideas and had some time, I trig-bashed my way through the general case. If you want to know how, I can explain it, but it shouldn't be anything new to you. Unless I made a mistake, there's not way to fit more than four consecutive vertices of a regular polygon to the inside of another regular polygon with one side more or fewer. Black Carrot (talk) 09:15, 9 February 2008 (UTC)

You can consider this as a system of equations and do some simple analysis to see if you get an overdetermined system. An n-gons is completely determined by 4 parameters, say the position of centre of the polygon and the one of the vertices. Now consider each vertex, for it to fit in another given polygon the vertex must lie on one of the straight line which make the second polygons boundary, so it must satisfy the equation ax+by+c=0 of the straight line. So to fit an n-gon inside another polygon we have a system of n-equations in 4 unknowns. This indicates that you would expect a one parameter family of triangles to fit in any other polygon (3 equations in 4 unknown). You would expect to find a finite number of squares which fit (4 eqn in four unknowns) but not expect pentagons or hexagons to fit. There is of course a caveat in that symmetry may mean that some of the equations are degenerate. Indeed an n-gon will fit trivially inside a 2n-gon. --Salix alba (talk) 10:59, 9 February 2008 (UTC)

A regular-pentagon does not fit inside a square. Take a pentagon with the distance from the centre to each vertex is 1, and arrange it so that one edge in horizontal. Now calculate its height and width, for it to fit in the square in the diagram above the height and width must be equal. If θ=π/5 we find the height is 1+cos(θ)=1.809 and its width is 2 sin(2 θ)=1.902, these are quite close so thy may look fine visually but they don't actually fit. --Salix alba (talk) 11:29, 9 February 2008 (UTC)

Yeah i know that pentagon in the diagram doesn't fit inside the square, that's why it's coloured blue. --Kvasir (talk) 14:02, 9 February 2008 (UTC)