Wikipedia:Reference desk/Archives/Mathematics/2012 September 10

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 10

Matrix subgroup

I'm interested in identifying the subgroup of GL(n,Z) generated by the squares of transvection matrices (i.e. squares of matrices that differ from the identity matrix by replacing a single zero with a one) -- in particular, I'd like to know a presentation. It's not too difficult to see (or maybe it is) that any matrix in this subgroup must have odd entries on the diagonal and even entries elsewhere, and so it is contained in the level 2 principal congruence subgroup (it might perhaps be the whole congruence group?). Any pointers towards a presentation, or just an identification of this group would be appreciated! Thanks, Icthyos (talk) 10:11, 10 September 2012 (UTC)

Related to your earlier question - Wikipedia:Reference_desk/Archives/Mathematics/2012_March_27#Homomorphisms_from_GL.28n.2CZ.29_into_a_symmetric_group.3F ? The wikilinks there, especially the 4th & 5th section of Special linear group & Steinberg group (K-theory) should help - there's a presentation of SL (n, Z) there. Has to be some modification of the Steinberg relations, and the group you are looking at should (nearly?) generate the congruence subgroup, as the elementary matrices / transvections generate SL. A look at the first chapters of Milnor's book on should help (even if not directly, because it is Milnor).John Z (talk) 09:14, 11 September 2012 (UTC)

It's not completely relevant to that question, I just always seem to end up mapping into GL(n,Z)! I've realised that I can throw in inversion matrices too if I want, as well as squares of transvections, and I'm *pretty* sure that together they generate the level 2 congruence group (the transvection squares alone, however, do not). So, it comes down to finding a presentation of the congruence subgroup...but surely someone must have done this before? I mean, it's a finite index subgroup, so I can definitely churn out a finite presentation using Reidemeister-Schreier, but...really? Must I? Thanks for the suggestions, Icthyos (talk) 09:51, 11 September 2012 (UTC)

Standard metrics for quality of multi-objective optimization?

Tried looking through relevant articles on optimization but couldn't find any notice. Is there any "standard" metric to judge the quality (i.e. how close to the Pareto front are the results found) for a heuristic optimization algorithm? This is in the setting of discrete input variables (hence finite state space). A concrete case study is available for direct comparison of the solutions found, but it would be nice to learn if such metrics are (generally) used.

For example, say the Pareto front lies for two variables to be maximized lies on (0,10), (8,8), and (10,5), but the algorithm identifies (0,10), (7,7) and (10,5), thereby missing one solution on the front (and none in between), out of a state space of size 128? Of course such a metric can be "made up" (e.g. share of missed solutions better than the identified Pareto border, area of the space between identified and real border), but I want to know if there is any such metric which is used as a "standard". 130.237.57.87 (talk) 14:53, 10 September 2012 (UTC)

I don't know if there is a standard for this, but if there is one I would predict that it would take this form: the average, over all points identified by the algorithm, of the squared Euclidean distance to the nearest point on the true Pareto front.

One could simulate the heuristic algorithm, and its resulting average of squared Euclidean distances, over a large number of hypothesized problems for which the entire Pareto front is known, then take an average (of the averaged Euclidean distances) over the set of all hypothesized problems. It seems to me, however, that this approach will be sensitive to the choice of hypothesized problems, so one would have to choose that set carefully based on what sort of problems, with what frequencies, one plans to use the heuristic for.

A possible flaw in the above suggested metric is that it fails to penalize heuristics that don't offer many candidate points Duoduoduo (talk) 17:35, 11 September 2012 (UTC)

Since in this case we have concrete case studies, it would be relatively easy to get such metrics (throwing many problems at the algorithm will be done slightly later...). There is a problem that it penalizes algorithms that have "gaping holes" (i.e. misses obvious candidates which are "on their own" so don't have close borders on the Pareto front...), but at least it's a start. If there was no standard I was thinking about something along those lines too... 130.237.57.87 (talk) 09:09, 12 September 2012 (UTC)

Another approach, which I have not seen, would be this: Make the Pareto front continuous by interpolating between points, perhaps linearly. Do the same with the heuristically generated front. Then take the area between the two continuous fronts. That should penalize a paucity of generated points (since the linear interpolation between two points with a big gap between them will generate a lot of area), and it should also penalize an algorithm which fails to find any point nearest to some point on the front. (That is, if point P on the Pareto front is not the nearest point to any of the generated points, that failure would be penalized.) Duoduoduo (talk) 14:14, 12 September 2012 (UTC)

Thanks, good idea. I actually had it too... 85.228.20.17 (talk) 19:32, 12 September 2012 (UTC)

What is a cross-over point in a rational funciton?

My daughter's math class is working with rational functions and graphing them. What is a "cross-over point" of a function such as y = 3x/(x+4)? IS it where the horizontal and vertical asymptotes cross, (-4,3) in this case? Bubba73 ^{You talkin' to me?} 20:53, 10 September 2012 (UTC)

That sounds reasonable. The only other possibility I can think of is if it refers to the X- and Y-intercepts (both (0,0), in this case). StuRat (talk) 21:12, 10 September 2012 (UTC)

Her textbook doesn't seem to say and she can't remember what the teacher said. But as I thought about it, it was all I could think of that made sense. They are working on asymptotes. Bubba73 ^{You talkin' to me?} 22:44, 10 September 2012 (UTC)

While I've never heard that terminology myself, I believe you have given the most reasonable interpretation. One other thought though, it might be a trick question, with the answer being "this curve never crosses over either asymptote" (some curves do). StuRat (talk) 23:53, 10 September 2012 (UTC)

In a case like this, I just give every bit of info I have:

• The 2 asymptotes cross at (-4,3).
• The curve does not cross either asymptote.
• The X-intercept is at (0,0).
• The Y-intercept is at (0,0).

StuRat (talk) 00:01, 11 September 2012 (UTC)

There were three of these on a test she got back today, so I doubt it was a trick question. (She missed all three.) Bubba73 ^{You talkin' to me?} 00:22, 11 September 2012 (UTC)

Sorry to hear that. Did any of those curves cross the asymptotes ?

In any case, since this terminology was apparently made up by the teacher, she better ask the teacher what it means, so she will know for the finals. StuRat (talk) 00:24, 11 September 2012 (UTC)

Do you mean did they cross the X- or Y-axis? Bubba73 ^{You talkin' to me?} 01:43, 11 September 2012 (UTC)

There were three rational functions. For each they were to graph it, give the x- and y-intercepts, the horizontal and vertical asymptotes, the cross-over point, and the hole. The hole is a point that is not on the graph in the original function, but is after reducing the function by cancelling. She missed cross-over point on all three, and neither of us know what it is. Bubba73 ^{You talkin' to me?} 04:19, 11 September 2012 (UTC)

No, I meant a curve which crosses it's asymptote(s). Here's an example: [1]. That one crosses many times, but it's also possible to have a curve which crosses it's asymptote just once. StuRat (talk) 05:00, 11 September 2012 (UTC)

Two more examples of rational functions, whose graphs cross theis asyptotes just once, can be found in Rational function#Examples. --CiaPan (talk) 05:16, 11 September 2012 (UTC)

Resolved

I got email back from the teacher, and the cross-over point is where the function crosses the horizontal asymptote. Bubba73 ^{You talkin' to me?} 14:42, 11 September 2012 (UTC)

Interesting that it's just the horizontal asymptote. Why have a special term for this special case, and exclude vertical asymptotes and all others ? This is sounding less and less like a standard mathematical term and more like one invented by the teacher. It's up to you, but you could lodge a complaint that the teacher is using non-standard terms not included in the text, and potentially get those questions excluded from the test. (I was once placed in a remedial math class because I answered all the division problems on a test correctly, but in fractional form, when they wanted them in the much inferior remainder form.) StuRat (talk) 18:05, 11 September 2012 (UTC)

It was a function like this one File:RationalDegree2byXedi.svg. I don't see the significance of the point where it crosses the horizontal asymptote. The term isn't in the index of the textbook and I read the entire section on rational functions that they had just covered, and it isn't in there. Bubba73 ^{You talkin' to me?} 18:58, 11 September 2012 (UTC)

Yes, and I didn't find it by Googling either. StuRat (talk) 19:01, 11 September 2012 (UTC)

(responding to "exclude vertical asymptotes" above) A function can't cross a vertical asymptote. I reread the section and now I see where it comes from. The book gives guidelines for sketching rational functions. One step is to see if it crosses the horizontal asymptote and (if it does) plot that point. But it does not use the "cross-over point" terminology. Bubba73 ^{You talkin' to me?}

Well, a function in the form y = f(x) won't typically cross a vertical asymptote, but one in the form x = f(y) often will, as will those in polar coordinates. Also, there can be asymptotes which are neither horizontal nor vertical. StuRat (talk) 19:51, 11 September 2012 (UTC)

Any function f:R → R can be "graphed" which means to plot the value of the function along the y-direction for each argument x. Obviously you can make other 2D representations, but this particular one is standard and in this context we can say a rational function can never cross a vertical asymptote. Rckrone (talk) 00:19, 12 September 2012 (UTC)