Wikipedia:Reference desk/Archives/Mathematics/2015 April 8

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 8

Find Quotation

I realize this is not directly a math question, but I did not know where to put it: Someone once told me a quotation going something like "The term gaussian means there is nice math involved" with the alleged source being some "famous" mathematician (whose name i sadly cannot remember). I would like to find the proper source and wording. Does anyone this? (or could propose a method of finding the desired information) — Preceding unsigned comment added by 129.217.158.241 (talk) 08:39, 8 April 2015 (UTC)

Gaussian in general refers to the indeed rather famous mathematician Karl Friedrich Gauss. JoergenB (talk) 15:36, 8 April 2015 (UTC)

Okay, i phrased it badly. What the quote I search for intends to say is "When you stumble upon something called 'Gaussian X' you know it is going to be nice math", because that is how Gauß worked etc. I want to use it in a talk, where i talk about some Gaussian X and my point here is that it cant be too bad, because it is called _Gaussian: X. — Preceding unsigned comment added by 129.217.158.241 (talk) 07:58, 9 April 2015 (UTC)

How to parametrize a simplex in a "natural" way?

For a d+1 simplex, the most natural parametrization is the convex combination of the extreme points. But when I look at the simplex as an intersection of (d+1) half-spaces, I can't figure it out how to do it in a "natural" ("elegant"/"nice") way. The (d+1) inequalities can be turned into (d+1) equalities by introducing (d+1) slack variables.

But this set of equations is over-determined.

For simplicity, look at a triangle in the plane. If the triangle has extreme points (0,0), (a, 0) (0,b) there is an obvious choice of slack variables corresponding to the x- and y-axis, ignoring the variable corresponding to the diagonal. Can this be generalized, or is there another "natural" way to get rid of the over-determination? 95.112.207.202 (talk) 21:10, 8 April 2015 (UTC)

Your example generalizes straightforwardly: the points (x₁, ..., x_d) with all x_i ≥ 0 and Σ(x_i/a_i) ≤ 1 are a d-simplex. It's not a regular simplex, but you could fix that by setting all a_i to 1 and mapping (x₁, ..., x_d) to (x₁, ..., x_d, 1 − Σx_i) in one more dimension. -- BenRG (talk) 23:20, 8 April 2015 (UTC)

I'm not sure if I understand you correctly. Those x_i are the slack variables that happen to coincident with the x_i-axis in my simplified example? If so, how would that generalize to a general triangle (a₁, b₁), (a₂, b₂), (a₃, b₃)? 95.115.187.155 (talk) 11:49, 9 April 2015 (UTC)

Now I'm confused; are you given points or half spaces? Either way you need to solve systems of linear equations, but the problems aren't the same. Could you give a more typical example of the type of problem? --RDBury (talk) 17:10, 9 April 2015 (UTC)

Actually if you're given points P₀, P₁, ... P_n then a parametrization is X = t₀P₀ + t₁P₁ + ... t_nP_n with t₀+t₁+...t_n=1. Or, if you want to eliminate a variable, X = (1-t₁-...t_n)P₀ + t₁P₁ + ... t_nP_n with t₀+t₁+...t_n≤1. If you are given hyperplanes then you can find the points of intersection to reduce to the other case and use the solution just given, but you'd still need to solve equations as stated below. --RDBury (talk) 17:42, 9 April 2015 (UTC)

Sorry, I can't make sens of it all. My question, primarily, is not to reduce computation complexity (but any hint given on this aspect is truly welcome). The case in which from the known extreme points any other point is parametrizes by the convex hull of the extreme points is understood.(Hopefully so.) What I'm asking for is the case of (d+1) "random" half-spaces (given by (d+1) known "random" points in d-dimensional space). Then there are (d+1) slack variables,

but only d of them are independent. Of course, I can arbitrarily pick one of those and eliminate it using the given equations.

But what I'm asking for is, if there exists some "natural" way to do it, some kind of "normalization" of the problem. I'd be glad if I had some proper phrase to put my toughs in, but at the moment, this is the best hat I can do.95.115.187.155 (talk) 20:06, 9 April 2015 (UTC)

If you're given n+1 "random" half-spaces in n-space and want to parametrize the intersection, assuming it's non-empty, it seems to me you have to do at least as much work as it takes to find the vertices, each of which is the solution of n equations in n unknowns. Since if you has such a parametrization then you could get the vertices just by plugging in certain values. But the process shouldn't be much harder than Gaussian elimination. In fact, you can do it by finding the inverse of an n+1 by n+1 matrix. --RDBury (talk) 02:17, 9 April 2015 (UTC)

Maybe it's best to show what I have in mind through an example. Suppose you want to find a parametrization of the intersection of 2x+y≥2, x+y≤3, and y≥3x-5. That should be random enough so that the calculations are nontrivial. The first thing to do is to introduce slack variables s=2x+y-2, t=3-x-y and u=y-3x+5.Write the equations in vector form as (s t u) = (1 x y)A where A is

${\begin{pmatrix}-2&3&5\\2&-1&-3\\1&-1&4\end{pmatrix}}$

Multiply both sides by B=A^-1 to get (1 x y) = (s t u)B where B is

${\frac {1}{12}}{\begin{pmatrix}4&8&4\\5&7&-4\\1&-1&4\end{pmatrix}}$

Note that you can read off the points of intersection in projective coordinates as rows of B, that is (4, 8, 4) which is x=2, y=1; (5, 7, 4) which is x=7/5, y = -4/5; and (1, -1, 4) which is x=-1, y=4. Also note that the first column of B is positive, otherwise the intersection of the half planes is either empty or not bounded, in other words not a simplex. From the equation (1 x y) = (s t u)B you get the parametrization x=1/12(8s+7t-u), y=1/12(4s-4t+4u), s, t, u ≥ 0 and 1 = 1/12(4s+5t+u). A more standard parametrization can be obtained by scaling s by 4/12, t by 5/12 and u by 1/12, which would give x=2s+7/5t-u, y=s-4/5t+4u, s, t, u ≥ 0, s+t+u=1. You can also write this as (x, y) = sP₀ + tP₁ + uP₂ where P₀, P₁, P₂ are the three points of intersection found above. --RDBury (talk) 00:03, 10 April 2015 (UTC)

There exist algorithms, such as Finding the intersection of n half-spaces in time O(nlogn), to convert the half-space intersection problem into a convex hull problem. --Mark viking (talk) 00:17, 10 April 2015 (UTC)

Well, obviously my original question was more confusing then clear. So I try to rephrase it. I have a "random" set of half-planes given by ${\vec {n}}_{i}\cdot {\vec {x}}\leq b_{i}\;$ (and it is of low importance if they were given first hand or derived from the extreme points). Now I don't like inequalities and change them by introducing slack variables: ${\vec {n}}_{i}\cdot {\vec {x}}+s_{i}=b_{i}\;$. For every choice of the $s_{i}\geq 0$ there is at most one ${\vec {x}}$ that solves the equation, and this ${\vec {x}}$ also obeys the original inequality. Thus I have a parametrization of the simplex using slack variables.

But the system is overdetermined, and I am wondering if there is a "natural" way to cure this. Of course, I can randomly choose one of the slack variables and eliminate it, but an arbitrary choice does not seem "natural" 95.112.244.159 (talk) 09:01, 10 April 2015 (UTC)

When you introduce slack variables what you're really doing is converting the original region into an equivalent region which is the intersection of a affine subspace and an Orthant. For example with a line segment (or 1-simplex) defined by a≤x≤b, the introduction of slack variables s=x-a and t=b-x, changes the interval into an equivalent set defined as the intersection of the first quadrant in the s,t-plane with the diagonal line s+t=b-a. For a triangle, slack variables change the region into the intersection of a plane with the first octant. For a square, and this is where it starts to get hard to visualize, slack variables change the region to the intersection of a plane with the first orthant in 4-space. For a tetrahedron , slack variables change the region into the intersection of a hyperplane with the first orthant in 4-space. But orthants are remain the same if you interchange the variables, and the same is true of the idea of an affine subspace. So if you have a description in terms of an orthant and a subspace, picking one side must be arbitrary. It didn't seem that way for the example you gave because two of the slack variables happened to coincide with original variables, so it seemed natural to pick the remaining one to eliminate. But with a more general triangle that doesn't happen. If you carry the program through with your original example you get slack variables s=x/a, t=y/b, u=1-s-t, which changes the triangle to the intersection of the plane s+t+u=1 and the first octant in s,t,u-space. If you now forget that s and t originally came from x and y, there's no way to chose one of the variables s, t, or u without being arbitrary. For a more general triangle there is no such relationship between the slack variables and the original variables, it's just an arbitrary affine transformation between 2-space and 3-space, so there is no way to pick one variable in 3-space from the others without being arbitrary. In other words, the quick answer to your question, at least as I now understand it, is no.

In terms of computation though, it's usually better not to eliminate any of the the slack variables. This is why the simplex algorithm uses them and not the original inequalities. So usually the question of which variable to eliminate doesn't come up.

Btw, the paper referred to above applies to dimension 3 and the n used in the title is the number of faces, not the dimension as used here. The problem of finding vertices of a general polytope defined in terms of half spaces is exponential for the simple reason that the output may be exponential. An example is the n-cube which has 2n faces but 2ⁿ vertices. But it you're talking about simplexes only then the number of vertices is equal to the number of faces and the computation is, by what is stated above, the same as the computation needed to find the inverse of a matrix, which is somewhere between O(n²) and O(n³). --RDBury (talk) 20:12, 10 April 2015 (UTC)

Thank you for clarifying that, yes only dimension 3. I thought it might be useful as an illustration of a conversion, but you're correct that simplexes admit simpler methods. Cheers, --Mark viking (talk) 22:18, 10 April 2015 (UTC)

Thank you, I guess this about as "natural" as it can get. Lifting things one dimension up keeps "equal rights" for all slack variables and the one additional equation does not prefer any variables either. 95.112.185.237 (talk) 10:18, 11 April 2015 (UTC)