Jump to content

Wikipedia:Reference desk/Archives/Mathematics/2007 April 25

From Wikipedia, the free encyclopedia
Mathematics desk
< April 24 << Mar | April | May >> April 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.


April 25

[edit]

Conic Section

[edit]

Can someone point me in the right direction with these problems:

  • How do I find the coordinates of the endpoints of the major and minor axis of the ellipse:
  • Knowing that the angle of rotation is 108.43°, how do I unrotate:

?

and
.
I have plugged in the prime values for x and y, and substituted 108.43° for θ. How do I get x'y' to cancel out?

Thanks -- Sturgeonman 01:03, 25 April 2007 (UTC)[reply]

For the first part, I'd say you need to find the two angles with the maximum radius and the two angles with the minimum radius, then convert those 4 angles and radii to rectangular coords. StuRat 08:07, 25 April 2007 (UTC)[reply]
One is trivial; the other, mistaken.
  1. In polar coordinate form, the endpoints you seek are the maximum and minimum values of r. Look at the denominator, and think about where sin θ achieves its extremes of −1 and +1.
  2. For the hyperbola given by the second equation, the center is not at the origin, nor is the rotation angle what you "know". One easy trick is to find the asymptotic directions. In the projective plane, these are the two points where the hyperbola cuts through the "line at infinity". Formally, switch to homogeneous coordinates, (x:y:w), then set w to zero. The result is 0 = 4x2−6xy+2y2, which factors as 2(xy)(2xy). This does not give us the center, but it does tell us the slopes, thus implying the rotation. We have two choices, the smallest one being halfway between 45° (for x = y) and 26.565° (for 2x = y), namely 35.7825°. I believe if you try this you will find that the xy term does vanish.
Just curious; what was the source of that 108.43° angle? --KSmrqT 18:07, 25 April 2007 (UTC)[reply]
PS: The nature of contact with the line at infinity shows us what kind of nondegenerate conic we have. A parabola is tangent to infinity, so has a double factor. A hyperbola pierces infinity in two distinct places, so has two distinct factors. And an ellipse (including a circle) does not touch infinity. This should sound familiar, suggesting the discriminant of a quadratic equation. (There's also a pretty method for finding the center, here at (12,1512), using matrices.) --KSmrqT 14:46, 26 April 2007 (UTC)[reply]

Inverse of NxN Matrices Mod M (Hill cipher)

[edit]

I'm looking for an efficient method to find the inverse of arbitrarily sized matrices under an arbitrary modulo. The 2x2 case is trivial and I have already implemented it. Any ideas for bigger matrices? I need this in order to write a version of the Hill cipher. The easier the method the better (I'm not keen on coding gaussian elimination). I'm coding in Ruby if that's any help (any library's i don't know of?). BrokenSegue 04:46, 25 April 2007 (UTC)[reply]

as long as (det A, m) = 1. This is the formula given in Rosen's Elementary Number Theory and Its Applications. Though it is given in a previous section, it is referenced in the section on Hill Ciphers as the way to find the inverse of a matrix. StatisticsMan 05:12, 25 April 2007 (UTC)[reply]
Though as noted at Invertible matrix, this will become inefficient for large matrices (not sure how large before it becomes terrible). I think Gaussian elimination is the best method known in general. Algebraist 08:18, 25 April 2007 (UTC)[reply]
To invert a matrix by hand, I think it becomes tedious already at a 3x3 matrix. Going up to a computer, I can say that mine manages to invert a 1000x1000 matrix in about 2 seconds, but it gets much worse rapidly as you increase the size. A 10000x10000 matrix is a horror to invert, and puts my computer out of commission for half an hour at least (so I don't even try that anymore). Applied mathematicians go to great lengths to avoid inverting large matrices, often of the order of 100000 x 100000, because doing so is an operation. Indeed, they go to great lengths to avoid solving a system of equations with large matrices with Gauss elimination, (this is a considerably easier process) because of the time constraint, this is why so much effort has been used on iterative methods such as Conjugate gradients. Sjakkalle (Check!) 14:52, 25 April 2007 (UTC)[reply]
Any general approach will require bookkeeping and nested loops. Since you insist on arbitrary modulus, not just prime, the question of invertible elements complicates matters. Computing the adjugate and the determinant requires only ring operations, not inversion, so the only potential obstacle is inverting the determinant; but if the determinant is not an invertible element of the ring, the matrix is not invertible.
Gaussian elimination is preferred in numerical analysis for two reasons, though it typically takes the form of LU decomposition. One reason is that it can be more efficient than inversion. Another is numerical behavior. As a practical matter, we almost always include partial pivoting, permuting rows as necessary to avoid problematic inversions. For example, without pivoting we would have a problem with
With modular arithmetic and a modulus with small factors we might be forced to use full pivoting (permuting columns as well as rows) to guarantee success. That complicates the algorithm and increases the cost. (But note that any invertible element is fine; we need not sort magnitudes.)
My tentative suggestion is to try coding the adjugate/determinant method. If it is too complex for your tastes, I doubt you will be happy with any method. If it is too slow, then consider LU decomposition with full pivoting.
Another alternative, depending on your circumstances, is to let a system like SAGE or PARI/GP do the inversion. --KSmrqT 16:11, 25 April 2007 (UTC)[reply]
Ah thanks very much guys. I was hoping there was some secret mathematical method that mathematicians keep to themselves to make inversion both fast and easy. I guess I'll use the adjugate/determinant method (speed isn't so critical). One follow-up question: do I take the mod only after I've found the adjugate or do I do it as I'm calculating it? I think it's the former. BrokenSegue 19:22, 25 April 2007 (UTC)[reply]
Of course we have a secret method, but we aren't going to give it up that easily. In answer to your question, either will work. If I'd ever programmed a computer in my life I would hazard a guess at which would work faster. Algebraist 19:38, 25 April 2007 (UTC)[reply]
Mod as you go to keep the numbers small. If all the numbers fit in a standard integer anyway, it will be faster to mod after. As the matrix grows larger, the excessive growth is more likely. Mathematically, it makes no difference. (Ring homomorphism strikes again.) --KSmrqT 21:30, 25 April 2007 (UTC)[reply]
Thanks everyone, you guys are great. I just got it all working. When I clean it up, I'll post it somewhere online. As an aside, what math would I take to learn about ring theory? Or does it stand on its own? I've never heard of it before. BrokenSegue
Ring theory lives within abstract algebra. You already know a great deal about it, because the integers are the most important example, for many reasons. Other important examples are integers modulo n, as we've been discussing, and polynomials. We can add, subtract, and multiply, but not necessarily divide. Addition is always commutative; multiplication may not be. For example, square matrices of a given size form a ring with noncommutative multiplication.
Rings are interesting as objects themselves, but they are also heavily used for other mathematics. For example, cohomology theory gives more information about topology than homology theory (its twin) because it supports the extra structure of a ring, using the cup product for multiplication. Without the multiplication we have only a group. If every nonzero element has an inverse, and the multiplication is commutative, the ring becomes a field. --KSmrqT 23:01, 25 April 2007 (UTC)[reply]
Thanks for the mini-lecture. Sounds cool, even though I'm not sure how much of that I really understand. I'll start sifting through the ole wiki. BrokenSegue 05:37, 26 April 2007 (UTC)[reply]
You might like to look at NArray a Ruby class which can solve linear equations. Searching for ruby matrix solve may turn up other suitable libraries. --Salix alba (talk) 08:11, 26 April 2007 (UTC)[reply]

Help with surds

[edit]

Hi,
I can't get the formula thing to work so sqrt is a square root. But anyway, how do you solve this surd?

If it was just a as the denominator I could do it. Also, if it was I could do it (with the difference of two squares). But I don't know how to do this. Can you please help me?My Username is... 18:39, 25 April 2007 (UTC)[reply]

Not actually sure what you are looking for, but is it this?
x42bn6 Talk 18:58, 25 April 2007 (UTC)[reply]
No, I have to simplify . I know the answer is . I don't know how they get this though! Sorry about the wait, I was trying to get the formulae to come up properly. My Username is... 19:25, 25 April 2007 (UTC)[reply]
x42bn6's comment explains how to simplify . What makes you think the answer is ? (it isn't, by the way) Algebraist 19:35, 25 April 2007 (UTC)[reply]

Oops, I meant to write . When I do I get and you can't get this to . Sorry if I'm being thick!My Username is... 19:51, 25 April 2007 (UTC)[reply]

I hope my editing of your tex represents what you meant (remember you use forward slashes to close html-style tags!). How do you obtain ? Algebraist 20:10, 25 April 2007 (UTC)[reply]
Thanks for that! I meant it to say . Copying and pasting bits of other formulae doesn't work very well apparently (or not for me anyway!)My Username is... 20:12, 25 April 2007 (UTC)[reply]
Now I'm just confused. What do you consider to equal, and why? Algebraist 20:15, 25 April 2007 (UTC)[reply]
because cancels out the ...doesn't it?My Username is... 20:20, 25 April 2007 (UTC)[reply]

, by the normal rules of multiplying fractions. Now what is ? Algebraist 20:26, 25 April 2007 (UTC)[reply]

It's 6. Isn't it? My Username is... 20:33, 25 April 2007 (UTC)[reply]

Indeed. thus . Where have you been having trouble? Algebraist 20:35, 25 April 2007 (UTC)[reply]
(edit conflict) So it's 2root 6 over 30 (I've given up with <math>. Which is root 6 over 15! Thanks for your help and time! I think it's just I didn't understand the basic rules properly!My Username is... 20:39, 25 April 2007 (UTC)[reply]
Simplify , what do you get? Or, without multiplication you could simplify . Multiply that by . Root4(one) 13:42, 26 April 2007 (UTC)[reply]

Factors

[edit]

How many factors do each prime number 1-100 have? 68.193.147.179 20:38, 25 April 2007 (UTC) Example: 2=? factors, 3=? factors, 5=? factors, ....[reply]

Do negative factors count? Algebraist 20:40, 25 April 2007 (UTC)[reply]
In any case you should probably think about the definition of a prime number. Algebraist 20:46, 25 April 2007 (UTC)[reply]