Wikipedia:Reference desk/Archives/Mathematics/2007 May 15

Mathematics desk
< May 14	<< Apr | May | Jun >>	May 16 >

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.

May 15

Table of Integrals

Historically, how is the first Table_of_integrals created? It's like a chicken and egg situation. To solve an integral, you need a table. To create a table, you need to solve that integral. So you can neither solve an integral nor create a table of integrals. 202.168.50.40 01:37, 15 May 2007 (UTC)

You don't need a table. When someone sets out to learn calculus, they do the integrals without this help. Integration is merely the inverse process of differentiation, which is not hard to do. So if you know a lot of derivatives, and understand some basic properties of integrals (such as linearity), then you can already integrate a lot of the functions you usually come across. nadav 01:50, 15 May 2007 (UTC)

Of course, then come more powerful methods such as substitution, integration by parts et cetera. -- Meni Rosenfeld (talk) 08:23, 15 May 2007 (UTC)

I really hope this is a joke... I knew engineers, scientists etc were given tables of integrals, but I always assumed it was "here's a bunch of integrals done for you by people who know maths," not "here's a bunch of integrals that have come into being without human agency" Algebraist 14:54, 15 May 2007 (UTC)

The first time Moses went up the mountain, he came back with the Tables of Multiplication. The second time he came back with the Tables of Integrals. Scientists are still trying to figure out where the Tables of Logarithms came from.  --Lambiam^Talk

I take it addition is the product of feeble human intellect, then? Algebraist 17:49, 15 May 2007 (UTC)

Addition was derived from the multiplication tables. For example, $6+6=6*2=12$ and $8+4=4*2+4=4+4+4=4*3=12$. The prominent theory regarding the Tables of Logarithms is that they were dug up from the ruins of an ancient alien civilization with transfinite intelligence. -- Meni Rosenfeld (talk) 19:16, 15 May 2007 (UTC)

Fractal Artwork

This is part Math Desk, part Humanities. I've been looking around a bit, and I've noticed that everybody who does art with fractals seems to favor either the abstract, or the obviously self-similar. There are, of course, the many fractal-based images of ferns and mountains and occasionally snail shells, some of them gorgeous, some of them even realistic, but the closest I've found to an attempt to capture concrete nonfractal objects with fractal techniques was a gallery of rather unconvincing fractal "faces". Can anyone point me towards someone who's doing that kind of work? Or, if nobody is, do you think there would be a market for it? Black Carrot 05:32, 15 May 2007 (UTC)

Could the reason that these "faces" were rather unconvincing be that fractals are not a good approach to capturing non-fractal objects?  --Lambiam^Talk 10:27, 15 May 2007 (UTC)

See "fractal compression"; though I don't know who, if anyone, is actively pursuing research in this area today, as mainstream compression eventually produced better compression than Barnsley's initial optimistic claims. But you may be interested in neighboring topics such as cellular automata and Lindenmayer systems. A group of researchers at Calgary has produced some beautiful results. --KSmrq^T 11:37, 15 May 2007 (UTC)

BERMUDA TRIANGLE

What is BERMUDA TRIANGLE?
Where can I find pictures of it?

Donlesnar 08:55, 15 May 2007 (UTC)

Try Bermuda Triangle. --CiaPan 09:11, 15 May 2007 (UTC)

linear programming

Hi there just doing some pre-uni work on my course coming up to get up to the required level. I am currently teaching myself linear programming and have come across this gem of a question.

tasks 1,2,3,4,5 are to be undertaken by individuals A,B,C,D and E. Each person has to do one task. Each task has to be undertaken by one person. The table below shows who can do which task - y=yes

	A	B	C	D	E
1	y		y
2			y	y
3	y				y
4		y		y	y
5		y		y

Formulate as an LP the problem. How would i go about doing this on LINDO

Thank you very much for you time, sorry its a bit long winded but i really want to get on top of this before uni :) chemaddict

This is a special case of the assignment problem, which is a special case of the transportation problem, which is a special case of the minimum cost flow problem, which is a special case of linear programming. That gives you as many ways to solve this problem as you could wish for, and if you learn all of them, you'll know as much linear programming as any sane pre-uni student could want, IMO. Algebraist 14:50, 15 May 2007 (UTC)

I rejigged your table. Hope you don't mind. Algebraist 15:17, 15 May 2007 (UTC)

LP problems have an objective function to be maximised or minimised, in the case of the assignment problem it would be the total effectiveness or time (respectively) of the allocation of jobs to people. Your problem doesn't have such an OF, but it does have multiple feasible solutions (eg A1 B4 C2 D5 E3 or A1 B5 C2 D4 E3) - there is no criterion to select the best. .. 81.151.82.52 16:46, 15 May 2007 (UTC)

That's not a problem. Just set each job-person allocation to have effectiveness 1 (or whatever) so you're maximising the number of people allocated to jobs. Then both solutions given are optimal. Algebraist 17:48, 15 May 2007 (UTC)

If I understood the description correctly, this can also be solved as an exact cover problem, which is a type of constraint satisfaction problem. Of course, that's not actually LP, but it is a related topic. —Ilmari Karonen (talk) 08:51, 17 May 2007 (UTC)

In fact, the table form you gave the problem in makes solving it as an exact cover problem particularly simple: Pick any "y", (mentally) cross out the row and column it's on, and repeat until done. If you get stuck with an incomplete solution, backtrack. This is essentially Knuth's algorithm X; for large tables, an efficient computer implementation of the process is dancing links. —Ilmari Karonen (talk) 09:09, 17 May 2007 (UTC)

Jordan Normal Form & the Structure Theorem

I'm attempting to do this:

Calculate the Jordal Normal Form for the following matrix A by calculating the invariant factor matrix of $\textstyle xI-A\in M_{4}(\mathbb {C} [x])$ .

$A={\begin{bmatrix}-2&0&0&1\\1&1&0&1\\2&0&1&-2\\-1&0&0&0\end{bmatrix}}$

What are the characteristic and minimal polynomials of A?

I've taken xI - A and reduced it to its invariant factor matrix, which I got as a diagonal 4x4 matrix with 1, 1, x-1, (x-1)(x+1)² down the leading diagonal (and zeroes elsewhere). Earlier today I asked my lecturer and he said the way to do this is to then find the invariant factor decomposition. Going from my notes, I -think- that the invariant factor decomposition is

$A\cong {\mathbb {C} \over {\langle 1\rangle }}\oplus {\mathbb {C} \over {\langle 1\rangle }}\oplus {\mathbb {C} \over {\langle x-1\rangle }}\oplus {\mathbb {C} \over {\langle (x-1)(x+1)^{2}\rangle }}\cong {\mathbb {C} \over {\langle x-1\rangle }}\oplus {\mathbb {C} \over {\langle (x-1)(x+1)^{2}\rangle }}$,

where I'm using the angle bracket notation <f(x)> to denote "the ideal generated by f(x)". I think the primary decomposition is then

$A\cong {\mathbb {C} \over {\langle x-1\rangle }}\oplus {\mathbb {C} \over {\langle x-1\rangle }}\oplus {\mathbb {C} \over {\langle (x+1)^{2}\rangle }}$.

This would make the primary factors (x-1)¹, (x-1)¹, (x+1)², and so the minimum polynomial is μ(x) = (x-1)(x+1)². And I'd hazard a guess that the characteristic polynomial is χ(x) = (x-1)²(x+1)², which would mean the JNF of A is a (mostly) diagonal 4x4 matrix with 1, 1, -1, -1 down the leading diagonal, and a 1 underneath the first -1 (and zeroes elsewhere).

Have I done this correctly? If I've made a mistake at any step of the process, please point it out to me. Thanks. Maelin (Talk | Contribs) 12:53, 15 May 2007 (UTC)

I think your argument is correct (I knew this stuff properly for a brief period around exam time last year). I can confirm that your answer is right, since (0,1,0,0), (0,0,1,0) are linearly independent 1-eigenvectors, and (1,-1,0,1) is the unique evec with val -1, while the fact the trace is zero means the last diagonal entry must be another -1. Algebraist 14:39, 15 May 2007 (UTC)

Assuming that your $xI-A$ matrix was row-reduced correctly, you can say with confidence that your invariant factors are the diagonal entries of that matrix (usually called the Smith normal form, if I'm not mistaken). The characteristic polynomial of A is always the product of the invariant factors, so you are not "hazarding" any guess when you claim that the characteristic polynomial is what it is. Lastly, the minimal polynomial is always the largest of the invariant factors (under the divisibility ordering), so your minimal polynomial is also correct. As for your Jordan form, I'm not sure I quite understand you, so here's what it should be:

$\left({\begin{array}{rrrr}1&0&0&0\\0&1&0&0\\0&0&-1&1\\0&0&0&-1\end{array}}\right)=(1)\oplus (1)\oplus \left({\begin{array}{rr}-1&1\\0&-1\\\end{array}}\right)$

Of course, you can permute the Jordan blocks however you like. –King Bee ^{(τ • γ)} 15:25, 16 May 2007 (UTC)