Wikipedia:Reference desk/Archives/Mathematics/2014 January 29

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.

January 29

elementary row operations

Hello,

why don't elementary row operations change the solution set of system of linear equations? thanks! 2.55.125.148 (talk) 12:34, 29 January 2014 (UTC)

Because elementary row operations correspond to valid algebraic manipulation of the equations. The three elementary row operations are: scaling a row; swapping two rows; and adding one row to another. These respectively correspond to: multiplying both sides of one of the equations by a constant; rearranging the equations; and adding one equation to another. None of those actions change the solution set of the equations.--149.148.255.145 (talk) 14:23, 29 January 2014 (UTC)

Using more official terminology, it's because row operations don't change the linear span of the column space. 149...145 gives a good rationale for this above, but it is also rigorously proven in many introductory texts on linear algebra. SemanticMantis (talk) 15:57, 29 January 2014 (UTC)

How to solve this without using hit and trial?

If x² + y² = 25 and x³ + y³ = 91, then find the value of x and y. 182.66.55.153 (talk) 16:37, 29 January 2014 (UTC)

Not sure this will help but the first equation is for a circle so we could change it x=5*sin(t) y=5*cos(t) and then the second equation becomes sin³t + cos³t = 91/125, but I can't solve that off hand. RJFJR (talk) 17:24, 29 January 2014 (UTC)

There's not much hit or miss. Assume this is a human word problem, so an integer solution and x and y positive. Then for the first eq, we have the Pythagorean triple (3,4,5). Plugging in x = 3 in the second gives y=4. For more general constants, solving for x and combining equations gets you a 6th order equation that in general can't be solved analytically. --Mark viking (talk) 19:06, 29 January 2014 (UTC)

You could also factorise x³ + y³ into (x + y)(x² - xy + y²) and note that 7 times 13 is 91 (I actually solved it this way whilst trying unsuccessfully to solve it algebraically), but I agree that the answer is obvious if only positive integer solutions are required. Dbfirs 19:56, 29 January 2014 (UTC)

Bezout's theorem says there should be six solutions and a sketch of the graphs indicates that four of them are real. I get x=4.61313, y=-1.92847 and x=-1.92847, y=4.61313 as the other two real solutions. I can derive algebraic expressions for all solutions but it will take some time to write it up. --RDBury (talk) 22:14, 29 January 2014 (UTC)

Notice both equations are symmetric in x and y. This implies that both curves are symmetric about the line y=x so one approach might be to change variables to rotate the axes by 45 degrees. Instead, rewrite the equations in terms of the symmetric polynomials s=x+y and p=xy, Note that x and y can be recovered from s and p as the solutions to z²-sz+p, or

$x,y={\frac {s\pm {\sqrt {s^{2}-4p}}}{2}}$

From x² + y² = s²-2p and x³ + y³ = s³-3sp, the equations are s²-2p = 25 and s³-3sp=91. Solve both for p and eliminate to get, after a bit of simplification, s³-75s+182=0. If you guessed the x=3, y=4 solution to the original problem then you get s=7 as a solution to this equations, otherwise substitute the 16 divisors of 182 into the equation, see rational root theorem. In any case, the equation becomes (s-7)(s²+7s-26)=0 and, applying the quadratic equation for the second factor, the solutions are s = 7, (-7±3√17)/2. From s²-2p = 25, s²−4p=50-s² which has values 1, (-1±21√17)/2 for the three values of s. For s=7 the resulting values of x and y are x=(7±1)/2, y=(7∓1)/2 or (x, y)=(3, 4) or (4, 3). For s = (-7+3√17)/2 the resulting values are

$x={\frac {-7+3{\sqrt {17}}\pm {\sqrt {-2+42{\sqrt {17}}}}}{4}},\,y={\frac {-7+3{\sqrt {17}}\mp {\sqrt {-2+42{\sqrt {17}}}}}{4}}.$

In this case all the square roots are of positive numbers so these solutions are real and are the two I mentioned above. For s = (-7-3√17)/2 the resulting values are

$x={\frac {-7-3{\sqrt {17}}\pm i{\sqrt {2+42{\sqrt {17}}}}}{4}},\,y={\frac {-7-3{\sqrt {17}}\mp i{\sqrt {2+42{\sqrt {17}}}}}{4}}.$

These are the two imaginary solutions. --RDBury (talk) 23:23, 29 January 2014 (UTC)

Nice analytic work for the other roots! --Mark viking (talk) 03:18, 30 January 2014 (UTC)

If you solve algebraic equations numerically the expression using square roots is not a shortcut. The equations are 0=182−75s+0s²+1s³=(25−s²)+2p=p−sx+1x². In J (programming language) it is solved like this

   ] s =. > {: p. 182 _75 0 1
_9.68466 7 2.68466
   ] p =. , > {: |: p. (25-s^2) ,. 2
34.3963 12 _8.8963
   ] x =. |: > {: |: p. p ,. (-s) ,. 1
 _4.84233j3.3088 4  4.61313
_4.84233j_3.3088 3 _1.92847

and the original equations are checked like this

   +/x^2
25 25 25
   +/x^3
91 91 91

Bo Jacoby (talk) 21:02, 2 February 2014 (UTC).

Web page for finding factors of large numbers

Anyone know of a web page that uses programming to find prime factors of large numbers?? I know of one:

http://www.alpertron.com.ar/ECM.HTM

To a higher extent than all other web pages I know, it tries hard. It does a good job with numbers up to about 90 digits. With larger numbers, however, there can be a problem. In general, it's hard to find factors of a number if it says it is composite, but finds no factors after 325 curves. (Why 325?? Up to that point, each curve takes several seconds. Starting at curve 326, it takes even longer per curve to finish, and it becomes a little inappropriate to wait if more than 325 curves are needed.) Anyone know of a web page that finds prime factors of large numbers even better?? Georgia guy (talk) 23:37, 29 January 2014 (UTC)

Not an answer to your Q, but when a program suddenly gets much slower from adding one more thing to it, this sounds very much like it has filled up the RAM and has gone to swapping data in and out of paging space, which is much slower. StuRat (talk) 03:52, 30 January 2014 (UTC)

It has no competition among online factorisation programs. If you want faster factorization then you must download and run a program yourself. Efficient factorization is a complicated art with good algorithms depending on many aspects like the form and size of the number, the size of the factors you hope to find, the factorization work already done on the number, the available ram and other hardware issues. It isn't just a question of "Program X is fastest". Good factorization algorithms also have multiple stages where different programs may be fastest for different stages, and some programs don't implement all stages. Most of the efficient programs are listed at http://mersenneforum.org/showthread.php?t=3255. http://www.alpertron.com.ar/ECM.HTM uses several algorithms. The curve counts refer to ECM (elliptic curve method). A program, or the user for many programs, can choose parameters for an ECM curve. It's recommended to start with parameters which give fast curves and a good chance to find small factors but a poor chance for larger factors. If such curves fail to factor the number completely then the parameters can be changed several times to give increasingly slow curves with better chances of larger and larger factors. The website says: "The program runs 25 curves with limit B1 = 2000, 300 curves with limit B1 = 50000, 1675 curves with limit B1 = 1000000 and finally it uses curves with limit B1 = 11000000 until all factors are found." This matches your observation. The first 25 and next 300 curves are faster than the following curves. People and programs make different choices for such B1 values and curve counts. See http://www.loria.fr/~zimmerma/records/ecm/params.html for a strategy with more steps. A program can even have an option to automatically increase B1 slightly each time and only run 1 curve with each B1 value. PrimeHunter (talk) 13:37, 30 January 2014 (UTC)

(Nice opportunity to flaunt your relevant username :) ) SemanticMantis (talk) 21:47, 31 January 2014 (UTC)