Wikipedia:Reference desk/Archives/Mathematics/2007 June 6

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.

June 6

abstract algebra

pls let me know about quitiont field —Preceding unsigned comment added by 59.95.246.25 (talk • contribs)

Our article on quotient field may help you. Gandalf61 15:21, 6 June 2007 (UTC)

There are also quotient rings which happen to be fields, if by any chance this is what you meant. -- Meni Rosenfeld (talk) 15:24, 6 June 2007 (UTC)

Pivoting - linear programming

Hi all, when doing a pivoting operation in the Simplex Method of linear programming, you pivot on the row of the tableau with the smallest ratio. Is there a rule for deciding which one to use if the smallest ratio occurs on two rows? Somewhat urgent as I have an exam on this in about 15 hours and have just found a problem I can't do :-( --YFB ¿ 19:09, 6 June 2007 (UTC)

As mentioned at simplex algorithm, one need not pivot on the smallest ratio; other pivot rules exist, and none is yet known with a good worst-case speed. If you haven't been given specific instructions on this by your teacher, I don't see why you shouldn't pivot on either of the two equal rows. The algorithm's guaranteed to work in either case, though it might take more or less steps. Algebraist 20:27, 6 June 2007 (UTC)

Correction for linear solutions

Is there a fast way to correct the solution x of Ax = b if A changes a bit. That is, if I have

(A + dA)(x + dx) = b

and I already know x that solves Ax = b, what is the best way to find dx? I don't want to find the inverse of A at any stage. deeptrivia (talk) 19:38, 6 June 2007 (UTC)

We have $x={\frac {b}{A}}$, so the derivative of this is ${\frac {dx}{dA}}=-{\frac {b}{A^{2}}}$. This gives the linear approximation $x=-{\frac {b}{A^{2}}}dA+{\frac {b}{A}}$. nadav (talk) 20:17, 6 June 2007 (UTC)

I think that in the question A and dA are n by n matrices, and x, dx and b are vectors of length n.  --Lambiam^Talk 20:44, 6 June 2007 (UTC)

That makes sense. There wasn't much context, but it explains the choice of variables and not wanting to find the inverse of A. nadav (talk) 21:04, 6 June 2007 (UTC)

Instead of computing the inverse of A, you can solve an equation like Ax = b more efficiently using Gaussian elimination or LU decomposition. The notation dA instead of ΔA suggests that the change is extremely small. If that is the case, you may be able to use the formula in the article "Derivative of inverse matrix". PlanetMath.. However, I don't think that is actually faster. If no more than k entries of ΔA are nonzero, then there is an O(kn²) method for computing (A+ΔA)⁻¹ from A⁻¹ and ΔA.  --Lambiam^Talk 21:28, 6 June 2007 (UTC)

What is the nature of dA? If we have already computed, say, a QR decomposition for A, then we have methods to update the decomposition for some kinds of changes to A. As I recall, Gene Golub was one of the first to explore this, for optimization problems, and his well-known book Matrix Computations, 3/e (ISBN 978-0-8018-5414-9) discusses this in §12.6, Updating the Q-R Factorization. --KSmrq^T 21:43, 6 June 2007 (UTC)

Actually I'm using an iterative method to solve Ax = b, and I guess it's simple, because I only need to do matrix vector multiplications in these methods (e.g., conjugate gradient, GMRES). So, using the original solution as a starting point, and considering that dA is sparse, I can achieve this easily. Any better ways? deeptrivia (talk) 22:19, 7 June 2007 (UTC)

Would iterative_methods#Linear_systems be useful? --mglg_(talk)

If you're already using an iterative method, then why did you write that you "don't want to find the inverse of A at any stage"? How large are these beasts we're talking of? How important are speed, precision, and ease of implementation? How sparse is ΔA? Which iterative method do you actually use?  --Lambiam^Talk 23:30, 7 June 2007 (UTC)

ΔA will be quite sparse, and will perhaps have only some terms on the diagonals. If I were to find out inv(A), I've heard there are methods to correct it for inv(A + ΔA) using only scalar multiplications, matrix additions, etc. But A is huge (say 1000000 x 1000000 of complex numbers) , so storing the inverse all at once is hard, and it will take a long time to find it. deeptrivia (talk) 04:47, 10 June 2007 (UTC)

Proving ≤ in Surreal number is reflexive and transitive

I've been fiddling around with Surreal numbers and am a little stuck trying to prove that the relationship $\leq$ described in the article is either reflexive or transitive. That is, given the rules for Construction and Comparison in the article, I'd like to prove the following two statements for all surreal numbers A, B and C :

• Reflexivity - $A\leq A$
• Transitivity - If $A\leq B$ and $B\leq C$ then $A\leq C$

Note that since 0 = {|} I can easily prove that $0\leq 0$ but I'm stuck on the general cases. Thanks. Dugwiki 20:06, 6 June 2007 (UTC)

That's not recursion, it's reflexivity. Algebraist 20:13, 6 June 2007 (UTC)

Oops! Must have had the word "recursion" on the brain. I fixed my post above. Dugwiki 20:43, 6 June 2007 (UTC)

Reflexivity can be (fairly easily proved) by induction. i.e. suppose that all elements of the left and right sets of A are reflexive, and show that A itself is (using the definition). Probably transitivity is similar, but I haven't checked yet. Algebraist 20:19, 6 June 2007 (UTC)

Easy for you maybe, but obviously I'm not as smart as you. :) I still can't seem to get the inductive step to work.

Assume $\forall x\in A_{L}$ $x\leq x$ and $\forall y\in A_{R}$ $y\leq y$. Then we want to show that $A\leq A$. That is, we want to show that there is no $a\in A_{L}$ such that $A\leq a$ and that there is no $b\in A_{R}$ such that $b\leq A$. That's where I'm stuck. How do you prove that statement from the definition of $\leq$ and the inductive assumption that every member in A is reflexive in $\leq$ ? Dugwiki 21:03, 6 June 2007 (UTC)

Ok, I think I finally got it for reflexivity. Proof by contradiction.

Assume that $\exists a\in A_{L}$ such that $A\leq a$. Then there is no $x\in A_{L}$ such that $a\leq x$. But by the inductive assumption we know that $a\leq a$ and $a\in A_{L}$. So by contradiction there is no $a\in A_{L}$ such that $A\leq a$. A similar proof works to show the second half of the definition as well. Dugwiki 21:11, 6 June 2007 (UTC)

(after ec) Well done. My wasting time trying to find the tex for "not less than or equal to" has allowed you to solve it yourself. Still haven't done transitivity or totality, but induction must be involved. In an emergency, see On Numbers and Games or Knuth's Surreal Numbers: How Two Ex-Students Turned on to Pure Mathematics and Found Total Happiness. Algebraist 21:20, 6 June 2007 (UTC)

Thanks. This is kind of a fun topic, actually. I think I might start collecting some proofs on a user page for future reference. Still have to do transitivity and totality next. Dugwiki 21:29, 6 June 2007 (UTC)

Still haven't done them (and I should really go to bed), but it might be helpful to simultaneously induct for totality and transitivity. Algebraist 21:31, 6 June 2007 (UTC)

I also just realized that if I can prove $\leq$ is total, then those that mean's it's reflexive as well. So the above proof wouldn't even be needed in that case. Dugwiki 22:38, 6 June 2007 (UTC)

$\not \leq$ —The preceding unsigned comment was added by 129.78.64.102 (talk • contribs) 02:51, June 7, 2007 (UTC) – Please sign your posts!

The intention of the above anon's contribution is apparently to give the code for "not less than or equal to": <math>\not\le</math>.  --Lambiam^Talk 09:33, 7 June 2007 (UTC)

Algebraist said "My wasting time trying to find the tex for "not less than or equal to" has allowed you to solve it yourself."

Ecclesiastes said "Everything is a waste of time."

I just wanted to post briefly to follow-up. I toyed with the problem last night and constructed some proofs for transitivity and totality. I won't post the whole detailed thing here, but basically the trick I used was to first prove by induction that for a given surreal number A that $\forall x\in A_{L}x\leq A$ and $\forall x\in A_{R}A\leq x$. Once you have those two lemmas and reflexivity proven it becomes easier to show by induction that $\leq$ is both total and transitive. Dugwiki 15:42, 7 June 2007 (UTC) In case anybody is curious I posted proofs to all the above stuff on my userspace at User:Dugwiki/Surreal numbers. Original research proofs, so not appropriate for an article, but ok for my userspace and fun to work out. Dugwiki 16:19, 8 June 2007 (UTC)