Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Recently I stumbled upon the following theorem — I'd like to read a comprehensible (i.e. understandable for an engineer) proof for it:

Given a polynomial $F(t)$ of degree $n$, there exists a unique equivalent symmetric, multiaffine polynomial $f(u_1, u_2, \ldots, u_n)$ — $u_i$ all of degree $1$ — satisfying $f(t,t,\dots,t) = F(t)$. This $f(u_1,u_2,\ldots,u_n)$ is called the polar form of $F(t)$.

So for example,

$F(t) = 5t^3 + 6t^2 + 9t - 2$

Is equivalent to

$\begin{align}f(u,v,w) & = c_1 uvw + c_2 uv + c_3 uw + c_4 vw + c_5u + c_6v +c_7w + c_8 \\ & = 5uvw + 2uv + 2uw + 2vw + 3u + 3v + 3w -2 \end{align}$

Which is clearly symmetric (i.e. $f(u,v,w) = f(w,u,v) = f(v,w,u) = \ldots$). This multiaffine (in fact, triaffine) function is equal to $F(t)$ when $u,v,w$ all have value $t$, resulting in $f(t,t,\ldots,t)$.

What I understand, is that the "multiaffine" property says that when you keep every $u_i$ of $f(u_1,u_2,\ldots,u_n)$ constant, except for one $u_j$, then this $f$ is an affine function in this variable $u_j$. So then it would be just a line which is traversed with a constant speed, right?

For some reason, $f(t,t,\ldots,t)$ — which is equal to $F(t)$ as said before — is called the diagonal (form) of $f$. I can imagine a diagonal in a 3D (or 2D) coordinate system where $u=v=w$, this would in a certain sense be a diagonal of the coordinate system. Is this the reason why it's called "diagonal (form)"?

So my question, where can I find a good proof for the above theorem?

Edit: Furthermore, I'd like to refresh my knowledge of affine spaces, functions, combinations... (e.g. why is it that for an affine combination of points resulting in a new point, the coefficients have to add up to 1 — and when combining them into a vector, they have to add up to 0). Any recommendations for readable books/articles are most welcome!

Edit2: Although Gerry has provided a nice solution, I'd like to know why there is such a difference between his proof and Ramshaw's (the link to that proof is in the comments). For some reason, he uses multiple variables for the function $F$, and the multinomial coefficient. Why is that? Oh, and if anybody has some thoughts about accessible literature on affine things, please let me know.

share|improve this question
    
Comment: I only found one proof for the theorem, given by Lyle Ramshaw. But as he already mentions himself, the article might be a little too mathematically involved for engineers. Indeed, the provided proof is too concise for me to understand. –  Ailurus May 31 '12 at 23:33
add comment

3 Answers 3

up vote 3 down vote accepted

I think you have the right idea as to why the term, "diagonal".

As for the theorem, suppose $$F(t)=a_0t^n+a_1t^{n-1}+\cdots+a_{n-1}t+a_n$$ with $a_0\ne0$. Now pick any term there, say, $a_{n-k}t^k$, and think of all the ways of choosing $k$ of the variables $u_1,u_2,\dots,u_n$, and forming their product; let's say there are $C$ ways to do this (more about $C$, later). Well, if you give each product the coefficient $a_{n-k}/C$, then the sum of these terms will be a symmetric sum of $C$ terms, each with coefficient $a_{n-k}/C$. Now when you let $u_j=t$ for all $j$, you get a sum of $C$ terms, each of which is $(a_{n-k}/C)t^k$, so in total you get $a_{n-k}t^k$, which is what you want.

In your example, $n=3$, let's look at the term $6t^2$. Now $C=3$ because there are 3 ways to choose 2 of the variables $u,v,w$ to form their product, namely, $uv$, $uw$, and $vw$, and $a_1$, the coefficient of $t^2$, is 6, and $6/3=2$, and that's why we want $2uv+2uw+2vw$ in the symmetric polynomial.

In general, what I've called $C$ is the binomial coefficient $n\choose k$ which has the simple formula, $${n\choose k}={n!\over k!(n-k)!}$$ where I take it you are au courant with factorials.

share|improve this answer
    
Thanks for your answer! It's quite clear, but when I compare it to Ramshaw's proof, it almost seems too easy. Because, for some reason, he involves multinomial coefficients (and multiple variables for the function $F$, while our $F(t)$ only uses $t$ as variable). His paper is called Blossoming: A Connect-the-Dots Approach to Splines, the proof is on page 10. Could you perhaps have a look at it? –  Ailurus Jun 1 '12 at 7:27
    
You haven't given me any idea where to find this paper. –  Gerry Myerson Jun 1 '12 at 7:31
    
Sorry, I should've included a link: www.cgl.uwaterloo.ca/~smann/Papers/SRC-019.pdf –  Ailurus Jun 2 '12 at 11:33
    
I'll have a look, but it might be a few days. –  Gerry Myerson Jun 2 '12 at 13:01
add comment

A shorter explanation ...

In your given polynomial, replace every term $t^r$ by the expression

$$S_r(t_1, \ldots, t_n)/{n \choose r}$$

where $S_r(t_1, \ldots, t_n)$ is the elementary symmetric polynomial of degree $r$ in the variables $t_1, \ldots, t_n$. So ...

$$ t \rightarrow (t_1 + \cdots + t_n)/n$$ $$ t^2 \rightarrow (t_1t_2 + t_1t_2 + \cdots + t_{n-1}t_n)/{n\choose 2} $$ $$ t^n \rightarrow t_1t_2 \ldots t_n$$

and so on. By construction, the resulting expression is symmetric and has the correct "diagonal". It's really very simple and elementary. Ramshaw's explanation is overly formal and notation-heavy (by my tastes, anyway).

The first uses of "blossoming" were by de Casteljau in the 1960's. His papers make heavy use of symmetric functions, but they are very difficult to read. Ramshaw's paper rediscovered the idea and gave it the name "blossoming". To a mathematician, a "blossom" is just a "polar form" (and, in fact, this is what de Casteljau called them). There are many newer accounts of blossoming that are much easier to read than Ramshaw's.

share|improve this answer
    
Thanks! The only thing that is still a little confusing are the multi-affine, or $n$-affine, maps. Any good references for that? Or for the newer accounts on blossoming? –  Ailurus Jun 3 '12 at 13:08
    
cgafaq.info/wiki/Blossoming (despite the broken stuff). Farin's book is very good. Just google "blossom bezier". –  bubba Jun 4 '12 at 2:37
    
The maps have to be multi-affine so that they correspond to the convex combination steps in the de Casteljau construction of a Bezier curve. Just think of the variables in the blossom as a clever and convenient way of labeling the points that are produced during the de Casteljau algorithm. –  bubba Jun 4 '12 at 2:40
add comment

You may wish to check out Curves and Surfaces in Geometric Modeling by Jean Gallier. (See Chapter 4 especially.) The exposition there may be right at the level you're after, and since the book has gone out of print, the author has made a manuscript freely available at http://www.cis.upenn.edu/~jean/gbooks/geom1.html.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.