Wikipedia:Reference desk/Archives/Mathematics/2008 November 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.

November 6

Labeled graph with non-scalar labels

What is the term for a labeled graph if the labels are something other than scalars (e.g. geometric points, matrices, vectors, strings)? NeonMerlin 04:22, 6 November 2008 (UTC)

If you are referring to vertex labels, usually there is no term needed. The definition of graph specifies a set of things called "vertices" and another set of things called "edges" which are pairs of vertices. But there isn't anything in the definition that says what "vertices" actually must be. The vertex set of a graph can be any set. So normally when the vertices of a graph represent something (like geometric points, matrices, vectors, or strings), we just say that the things being represented actually are the vertices, and so we have just an ordinary old graph except that we know exactly what things the vertices are. —Bkell (talk) 06:26, 6 November 2008 (UTC)

Bkell is correct that you can consider various objects to be the vertices of the graph, but there are many applications where vertices have some identity which is different from the labels attached to the vertices. For one thing, different vertices might have the same label, but even if that is not true labels can be vertex properties rather than the vertices themselves. It really depends on what is natural in the circumstances. I would just refer to the graph as a "labelled graph", or as a "vertex-labelled graph". McKay (talk) 08:18, 6 November 2008 (UTC)

Matrix question

If I have the matrix ${\begin{bmatrix}a&b\\c&d\end{bmatrix}}$

the absolute value can be found by ad-bc, but what if the matrix is not square? How do I find the || of a non-square matrix? —Anonymous Dissident^Talk 06:38, 6 November 2008 (UTC)

The formal term for | | of a matrix is not 'absolute value' but rather the determinant of that matrix. You can't find the determinant of a non-square matrix but you can in general find the determinant of an n x n matrix where n is a non-negative integer. See determinant. Topology Expert (talk) 09:05, 6 November 2008 (UTC)

The Determinant isn't defined for non-square matrices. The determinant corresponds to the ratio of how an area or volume (or n-volme) element changes size when the 2, 3 or n-space it is in is linearly transformed. NxM matrices always either introduce redundancies or flatten things. The best that can be done by way of generalizing determinants is have a set of values rather than a single value. This leads into something called Exterior algebra which isn't quite as bad as it sounds but not exactly kindegarten either. Dmcq (talk) 09:13, 6 November 2008 (UTC)

As an aspiring analyst, I would argue that exterior algebras are, in fact, as bad as they sound. :-) 76.126.116.54 (talk) 15:14, 6 November 2008 (UTC)

I'll make a small guess you have just looked at the Hodge dual and you're twisting your mind around to relate it to a triple product. :) Actually it is very worth while trying to get this all nailed down properly. Dmcq (talk) 23:39, 6 November 2008 (UTC)

Actually there is a formula for some non-square matrices, and it is used in the calculation of areas of polygons in Analytic geometry: $S={\frac {1}{2}}{\begin{vmatrix}x_{1}&x_{2}&x_{3}...x_{n}\\y_{1}&y_{2}&y_{3}...y_{n}\end{vmatrix}}$, where $x_{n},y_{n}$ are the cartesian coordinates of an n-gon. Mdob | Talk 18:27, 6 November 2008 (UTC)

How is that expression defined? Algebraist 18:30, 6 November 2008 (UTC)

determinant=$x_{1}*y_{2}+x_{2}*y_{3}+x_{3}*y_{n}-(x_{2}*y_{1}+x_{3}*y_{2}+x_{n}*y_{3})$ Mdob | Talk 18:46, 6 November 2008 (UTC)

That is, the same formula for the 2x2 determinant, but extended to the left. Mdob | Talk 18:50, 6 November 2008 (UTC)

The above should read and/or evaluated as $S={\frac {1}{2}}{\begin{vmatrix}x_{1}&x_{2}&x_{3}...x_{n}&x_{1}\\y_{1}&y_{2}&y_{3}...y_{n}&y_{1}\end{vmatrix}}$. Saintrain (talk) 20:34, 6 November 2008 (UTC)

Saintrain: thanks for the correction! Mdob | Talk 23:39, 6 November 2008 (UTC)

"Simply" integrate

According to Maxwell speed distribution:

"If you want to find the probability of a particle to be between two different velocities v0 and v1, simply integrate this function with those numbers as the bounds."

Is it even possible to find the integral of that expression? If so, how? Sorry if the problem is actually trivial; I'm not good with Google or calculus. --99.237.96.81 (talk) 07:01, 6 November 2008 (UTC)

Since the integral of e^-x² is the error function, the solution will be expressed in terms thereof. With that in mind, the integral can be done rather easily. The other (and probably most "simple" way) is to just give it to a computer and to let it compute the integral numerically. Greets, David 08:30, 6 November 2008 (UTC)

I've edited some of the excessively informal language in this article, but it could still do with some more tidying up by someone familiar with topic. AndrewWTaylor (talk) 11:21, 7 November 2008 (UTC)

What's the most general model for random graphs?

In the language of probability it is customary to call "random object $X$ of the set $S$ " any measurable map $\scriptstyle X:\Omega \to S$ from a base probability space $\scriptstyle (\Omega ,{\mathcal {F}},P)$ to $S$ (once a sigma algebra has been fixed in $S$). According to this, I would expect that "random graph", say with (possibly infinite) vertex set $V$, in the most general meaning should refer to any measurable map $\scriptstyle X:\Omega \to 2^{K}$, where $K$ is the set of all unordered pairs of $V$, and of course, the power set $2^{K}$ is equipped with the product sigma algebra. In other words, in this wider definition any probability distribution of edges is allowed, not assuming independency of edges, nor that they are i.d., like it is e.g. in the Erdős-Rényi model or in the percolation models. I am not an expert in the field, and I just wonder if random graphs are studied in this full generality. (I put this query in the discussion page of random graphs, but here maybe it's quicker). Thanks in advance! --PMajer (talk) 12:40, 6 November 2008 (UTC)

Hmm, kind of too bad about that article. This isn't the direction that you're asking about, but the interesting thing is that in some sense there's a unique random graph; the article doesn't seem to talk about that (though I only glanced at it so I'm not sure about that.

More precisely, the random graph is the one that you get by starting with a countably infinite set of vertices and defining a measure on all graphs on those vertices by saying that any two nodes are connected with probability 1/2 (or 1/3, or 2/π, or anything between 0 and 1) and extending that to a probability measure in the obvious way. Then it turns out that there's a measure-1 subset of this set of graphs that are all isomorphic to one another. Up to isomorphism these are all the random graph. --Trovatore (talk) 09:54, 7 November 2008 (UTC)

Thanks! So, I guess the random graph should not be unique in the wider class I mentioned... --PMajer (talk) 20:06, 7 November 2008 (UTC)

Well, actually it probably is, with only minor restrictions on the generality of your measure. The random graph is in some sense very robust. For example it's also the "generic graph" (that is, a comeager set of graphs on a countably infinite set of vertices are isomorphic to the random graph).

I was thinking about it last night, and I think all you need, to ensure that a graph is isomorphic to the random graph, is the following criterion: Given any disjoint finite sets of vertices A and B, there's a node in the graph that connects to all the nodes in A and none of the nodes in B. Given two such graphs, you run a simple back-and-forth argument to show that they're isomorphic. And it's easy to see that the criterion holds for almost all graphs (given A and B, for each node, the probability that the node is connected to everything in A and nothing in B is positive, and you have infinitely many nodes to try, so it holds with prob 1 for each fixed A and B, but there are only countably many pairs A, B). Similarly for generic. --Trovatore (talk) 20:47, 7 November 2008 (UTC)

I think I got it... very nice. So seems that for your criterion to hold you just need the probability of edges to be bounded away from 0 and from 1, or something even weaker. You have to assume the edges to be independently distributed, right? If not there are silly examples like : all edges open / all edges closed ,together, with probability 1/2. --PMajer (talk) 21:35, 7 November 2008 (UTC)

Well, you could certainly get by with less than full independence, but sure, independence is the simplest thing that works. You want to stay away from, say, something that would make the probability of having an edge from node x to node y fall off quickly enough with the number of nodes already attached to x that there would be a positive probability of x winding up with finite degree. Every node in the random graph has infinite degree (and infinite, what do you call it, co-degree? the number of nodes it's not attached to). --Trovatore (talk) 21:54, 7 November 2008 (UTC)

Thanks, very clear. --PMajer (talk) 12:58, 8 November 2008 (UTC)

See Rado graph. Algebraist 13:12, 8 November 2008 (UTC)

Thank you guys! I have to say that I find the definition of the Rado graph as given in the quoted article a little unsatisfactory... Instead, I find more clear the property mentioned above by Trovatore (listed there as the fourth), that, as he taught me, is in fact a carachterization up to isomorphisms, and therefore may serve as an alternative definition. Also, it suggests a simple realization of the Rado graph (I guess it's standard). I added a remark in the discussion page there.--PMajer (talk) 12:11, 10 November 2008 (UTC)

left hand on wall of maze...wtf?

i've heard this several times before, if you are in a maze, put your left hand on the corresponding wall and follow the wall. Eventually, you will get out. How does this work? Is there some sort of mathematical reason for this? Please help, i cant sleep because of this :) 31306D696E6E69636B6D (talk) 14:20, 6 November 2008 (UTC)

Doesn't work in every maze. See Maze#Wall follower. -- Jao (talk) 14:41, 6 November 2008 (UTC)

It's kind of practical joke. The maze is ring-shaped, you put your hand on the wrong wall and stay there turning around forever :) But if you enter the maze with a hand on the wall of the gate from the beginning, then you will eventually exit --maybe form another gate-- just because the the path followed by your hand must have another endpoint, wich is necessarily a gate--PMajer (talk) 14:52, 6 November 2008 (UTC)

(after ec) : Not 'if you are in a maze' but rather 'when you are entering the maze'. When you're inside it's too late. Imagine you put your hand on the pillar – you certainly will go round and round, not getting any closer to the exit.

The mathematical reason is (for 'planar', that is one-level mazes, without any ramps or stairways) that each wall, when watched from above, forms a line on a plane, possibly forking in a shape of some topological tree. The tree has finite size, so when you walk along the tree edges, turnig around their free ends, you must eventually get to the starting point. If you start you walk iat the maze entrance, then you eventually get back to the entrance from outside. That means some time before you certainly get outside the maze, and walk around the whole or part of it (depends if there are more than one entrance/exit from the maze, and if they are internally connected). --CiaPan (talk) 14:43, 6 November 2008 (UTC)

I asked that same question 5(?) years ago here in the Reference Desk (that time tough there was not yet a separate RD for maths. Is there a way to search past questions to avoid this sort of things (asking the same question twice?) Mdob | Talk 18:40, 6 November 2008 (UTC)

You can try a Google search like [1] or [2], depending on how old it is. If it's older than 2004, you'll have to look through archives 1 to 8 at the bottom of Wikipedia:Reference desk/Archives. --WikiSlasher (talk) 23:52, 6 November 2008 (UTC)

The rule works if the maze is simply connected (that is any loop inside the maze, can deform to a point). This is equivalent to the statement that all walls in the maze, are connected to the boundary (this may have been mentioned; I have not read the whole thread).

Topology Expert (talk) 03:39, 7 November 2008 (UTC)

Let's clarify something. If you start using the "left hand" rule from the entrance, it will eventually take you back to the entrance in any (finite) maze - doesn't have to be connected, doesn't even have to be planar. So you won't get lost. What the "left hand" rule won't necessarily do is take you on a tour of the whole maze - so if you have a specific goal in mind (centre of maze, exit that is different from entrance), you may not reach it. Gandalf61 (talk) 07:29, 7 November 2008 (UTC)

Of course, all the hand-on-wall rule really guarantees is that you eventually end up where you started. Which, when you think about it, isn't necessarily that useful: there's no guarantee that you'll eventually end up in any particular part of the maze (including the outside), unless you already start there. Nor, assuming you simply want to go for a stroll in the maze and be sure to get back out, does the hand-on-wall method make any guarantees about the distance you'll have to walk, beyond it being somewhere between zero and the combined total length of all the walls in the maze. In a big simply-connected maze, you could be walking for days, traversing every dead end in sequence — or, if you happened to start with you hand on a pillar, as CiaPan notes above, your relaxing stroll might last only seconds.

Also, if the designer of the maze was tricky enough, you might have to be careful about how you define a "wall". A good definition might be "any obstacle that you can't or don't want to cross, or would not be willing or able to cross if coming from any other direction". The important part is the symmetry criterion: if the maze has any one-way obstacles (such as a ramp leading to a vertical drop, or a door that only opens from one side), it's easy to construct a wall-following path that never gets back where it started. (Of course, with such obstacles and a sufficiently evil maze designer, the maze could be constructed so that, past some point, one can never get out at all...) —Ilmari Karonen (talk) 09:39, 7 November 2008 (UTC)

That's easy, though. Just toss in a pit with some spikes at the bottom. Or a grue. It's hard to escape when you're dead. Black Carrot (talk) 04:52, 9 November 2008 (UTC)

sphere - ball, circle -> ??

If a "sphere" is a two-dimensional plane wrapped around a three dimensional "ball", is a "circle" a one-dimensional line wrapped around a two-dimensional _________?

Duomillia (talk) 14:47, 6 November 2008 (UTC)

Disc Algebraist 14:51, 6 November 2008 (UTC)

Hmmm. It's always the obvious answer in the end :( Duomillia (talk) 14:55, 6 November 2008 (UTC)

Indeed. :) You can just say "n-sphere" and "(n+1)-ball" (some people say "(n+1)-disc") if you want to talk more generally. --Tango (talk) 15:48, 6 November 2008 (UTC)

Disk. Michael Hardy (talk) 23:25, 6 November 2008 (UTC)

If the line in question is infinite, then the circle is its one-point compactification. If this line is finite (i.e a line segment), it is like gluing the endpoints of the line together (to form a circle). Formally, the circle is the quotient space of the unit interval obtained by setting the endpoints of the interval to be equivalent. A similar relation holds between the unit disc and the unit sphere. See ball (mathematics).

Topology Expert (talk) 03:43, 7 November 2008 (UTC)

Least prime greater than n

Let n be a composite number. How do I find the next (probable) prime after it (not just a prime greater than n, but the least prime greater than n.)? for example, given n = a trillion (1,000,000,000,000), it should output 1,000,000,000,061 (but not 1,000,000,000,063 or any greater value). Mdob | Talk 18:02, 6 November 2008 (UTC)

First, there is no such thing as "being a probable prime", it only makes sense to ask for, say, a base-a strong pseudoprime, where a is some specific number. Second, I don't think there is any shortcut to compute such numbers faster than checking all potential candidates; for primality, this can be arranged by sieving a reasonably sized interval, though I don't know of any analogue for pseudoprimes, so you might need to test them one by one in turn. — Emil J. 18:24, 6 November 2008 (UTC)

Strange... I could swear I've read somewhere (OpenSSL documentation?) that there is an algorithm (besides the sieving one). Well, thanks nonetheless. Mdob | Talk 18:36, 6 November 2008 (UTC)

There is nothing better known than sieving an interval above n to some limit L and then making probable prime tests on each number where sieving found no factor below L. When sieving, compute n modulo p for each prime p < L, and use that to see which values above n are divisible by p. Many math programs have built-in routines to search primes. Here is a PARI/GP call to find the right answer in your example:

? nextprime(1000000000000)
%4 = 1000000000039

1000000000061 is next and then comes 1000000000063. PARI/GP works on arbitrary size but PrimeFormGW [3] is faster on numbers with more than around 500 digits. Both are free. PrimeHunter (talk) 22:16, 6 November 2008 (UTC)

density (per unit volume) vs density (per unit area) or per unit hypervolume even

(you can skip my rambling attempt to justify this post, and answer the bottom sentence)

I am accustomed to calling "per cubic meter" terms as density such as density of water is a "per unit cubic meter" property. My book is calling "per unit square meter" terms also density. Is there a word to distinguish different kinds of density? Also, what do you mathematicians do about properties of 4-d functions that vary by just a constant with hyper-volume? I'm OCD about this, since if I chose to not make a big deal about this, the problem will nag me later when I review my notes.

Usually the property suffices to distinguish the meaning of the word density, such as the density of water, or the density of a unit field-line emanating from a surface. Are there any possible ambiguities down the road, in higher math/science classes?

If a 4-sphere is made out of hyperkryptonite, and let hyperkrptonite have lots of properties. Couldn't some other hypermaterial have the same energy per unit volume but different "per unit hypervolume" properties of the same thing being measured (such as a potential energy for some hypothetically useful application)?

I wish I didn't have to bother anyone over this nonsense question, but upon reading the disambig page[4] on density and then clicking a link[5] which re-ambiguates my obfuscation has now 30 thousand of my neurons all leading to a question mark brain cell, and I have the curse of inquisitive scientist mentality and I get obsessive & restless about this kind of stuff, and it will grow to 90 thousand if I have to keep digging and learn all about the origin of the term etc... when its only helpful if I can get an answer before I go to sleep that way 85 thousand of the neural connections will be re-routed asap before they solidify into long-term memory. There's a discovery channel edisode about some guy who is a savant and certain numbers have language-connotations, and vice versa. Density is the only word I've found for me, that has the distinct meaning of: the reciprocal of the exponent 3 (or a function thereof). I'm like the physics teacher who would flunks[6] his students if they interchange the term voltage instead of electric potential difference.

Math is the only thing that makes sense to me in this world, so when I've wrongly believed that density can't refer to area as well, my brain goes into a consuming repair process. The word "linear density" is redundant if per meter^2 and per meter^3 don't need such a qualifier.

This question in a nutshell: is there an obvious word I'm not aware of, if my vocabulary is like swiss cheese. If density can be basically mean "per unit anything" then is there a specific word for "per unit volume" or "per unit area"? Biologicithician (talk) 23:14, 6 November 2008 (UTC)

OK, its all good now. As I was grammar fixing my post, my brain (which was on overload trying to do problem solving & creativity) decided to test the word "areal" to see if it got those red squiggly lines under it, but it was clean. Then I verified that it was the word I was looking for! So since all of you are wikipedia editors, you can keep this in mind when you go about editing. In fact this phrase returns more hits in a google search than "linear density" (although further search engine statistical inference shows wikipedia is the #1 hit for linear density, but #4b when one searches "areal density" ). Also the disambiguation page http://en.wikipedia.org/wiki/Density_(disambiguation) has not a single occurrence of the word areal, but it does worsen the reader's understanding because as written it specificates the property of mass. Furthermore clicking on the article area density seems also inaccurately too specific. The area density page defines it in a way that contradicts the dictionary definition (dicdef: of or relating to area) since the area density article defines it as the reciprocal of area per unit mass, instead of X per unit area where X could also be "unit field lines" (a term I made up to aid my notes, let a hollow vandegraff sphere of fixed amount of charge be imaginarily divided into N tiles) which then readily lends to seeing more equations once a tile is defined to have 1 field line of magnitude 1 potential difference per meter.

1. The disambiguation page here first sentence needs to be worded more like Density and dense usually refer to a measure of how much of some entity is within(over?) a fixed amount of some other entity. Types of density include: but obviously better worded but equally inclusive.
2. Also on the same page, the item area density needs to be updated to reflect that things other than mass have areal density. If it were up to me, I'd argue that area is a noun, areal is an adjective, line is a noun, linear is an adjective, line:linear::area:areal NOT line:linear::area:area (and in case anyone is wondering, 3:volumetric and likely 4:hypervolumetric)

I'd do these edits myself, but I may still be partially wrong and if there are other things wrong with our encyclopedia, best not let it go only partially fixed. Maybe there's an item #3 and #4 that someone else may be aware of, in reviewing other possible inaccuracies stemming off the disambig page. For starters, the lead intro to density above the navigation box, should at least mention that 2d density is common, rather than linking to a bad disambig page (but if the disambig page is good, then the density article need not mention it, if its taken care of elsewhere, where a reader can find it). Biologicithician (talk) 23:14, 6 November 2008 (UTC)