11
$\begingroup$

Let $V$ be a $\mathbb{R}$-vector space. Let $\Phi:V^n\to\mathbb{R}$ a multilinear symmetric operator.

Is it true and how do we show that for any $v_1,\ldots,v_n\in V$, we have:

$$\Phi[v_1,\ldots,v_n]=\frac{1}{n!} \sum_{k=1}^n \sum_{1\leq j_1<\cdots<j_k\leq n} (-1)^{n-k}\phi (v_{j_1}+\cdots+v_{j_k}),$$ where $\phi(v)=\Phi(v,\ldots,v)$.

My question come from that, I have seen this formula when I was reading about mixed volume, and also when I was reading about mixed Monge-Ampère measure. The setting was not exactly the one of a vector space $V$ but I think the formula is true here and I am interested by having this property shown out of the specific context of Monge-Ampère measures or volumes. I have done some work in the other direction, i.e. starting from an operator $\phi:V\to\mathbb{R}$ satisfying some condition and obtaining a multilinear operator $\Phi$ ; bellow are the results I have seen in this direction.

I already know that if $\phi':V\to\mathbb{R}$ is such that for any $v_1,\ldots,v_n\in V$, $\phi'(\lambda_1 v_1+\ldots+\lambda_n v_n)$ is a homogeneous polynomial of degree $n$ in the variables $\lambda_i$, then there exists a unique multilinear symmetric operator $\Phi':V^n\to\mathbb{R}$ such that $\Phi'(v,\ldots,v)=\phi'(v)$ for any $v\in V$. Moreover $\Phi'(v_1,\ldots,v_n)$ is the coefficient of the symmetric monomial $\lambda_1\cdots\lambda_n$ in $\phi'(\lambda_1 v_1+\ldots+\lambda_n v_n)$ (see Symmetric multilinear form from an homogenous form.).

I also know that if $\phi'(\lambda v)=\lambda^n \phi'(v)$ and we define $$\Phi''(v_1,\ldots,v_n)=\frac{1}{n!} \sum_{k=1}^n \sum_{1\leq j_1<\cdots<j_k\leq n} (-1)^{n-k}\phi' (v_{j_1}+\cdots+v_{j_k}),$$ then $\Phi''(v,\ldots,v)=\frac{1}{n!} \sum_{k=1}^n (-1)^{n-k} \binom{n}{k} k^n \phi'(v)=\phi'(v)$ (see Show this equality (The factorial as an alternate sum with binomial coefficients).). It is clear that $\Phi''$ is symmetric, but I don't know if $\Phi''$ is multilinear.

Formula for $n=2$: $$\Phi[v_1,v_2]=\frac12 [\phi(v_1+v_2)-\phi(v_1)-\phi(v_2)].$$

Formula for $n=3$: $$\Phi[v_1,v_2,v_3]=\frac16 [\phi(v_1+v_2+v_3)-\phi(v_1+v_2)-\phi(v_1+v_3)-\phi(v_2+v_3)+\phi(v_1)+\phi(v_2)+\phi(v_3)].$$

$\endgroup$
1
$\begingroup$

(This is just the summary of the answers by Ewan and Anthony, but a lot simpler.)

Let $S_n$ denote the symmetric group. Also, let us write $X=\{1,\dots,n\}$. We compute $$\begin{eqnarray}\sum_{k=1}^{n}\sum_{1\leq j_{1}<\cdots<j_{k}\leq n}(-1)^{k}\phi(v_{j_{1}}+\cdots+v_{j_{k}})&=&\sum_{A\subset X}(-1)^{|A|}\phi(\sum_{a\in A}v_{a})\\&=&\sum_{A\subset X}(-1)^{|A|}\sum_{f:X\to A}\Phi(v_{f(1)},\dots,v_{f(n)})\\&=&\sum_{f:X\to X}\Phi(v_{f(1)},\dots,v_{f(n)})\sum_{f(X)\subset A\subset X}(-1)^{|A|}\\&=&\sum_{f\in S_{n}}\Phi(v_{f(1)},\dots,v_{f(n)})(-1)^{n}\\&=&(-1)^{n}n!\Phi(v_{1},\dots,v_{n}),\end{eqnarray}$$ where the fourth equality follows from the binomial formula.

$\endgroup$
5
$\begingroup$

This is true, here's a proof.

I'm going to use the polynomial notation $\Phi\left(v_{1},\ldots,v_{n}\right)=v_{1}\cdots v_{n}$ - note that the multilinearity and symmetry of $\Phi$ means that manipulating these like polynomials (i.e. commuting elements, distributing ``multiplication'') is completely legitimate. Let the RHS of your proposed equation be $\frac{1}{n!}F\left(n\right)$.

Using the multinomial expansion, we have $$ F\left(n\right)=\sum_{k=1}^{n}\left(-1\right)^{n-k}f\left(n,k\right) $$ where $$ f\left(n,k\right)=\sum_{1\le j_{1}<\cdots<j_{k}\le n}\ \sum_{l_{1}+\cdots+l_{k}=n}{n \choose l_{1},\ldots,l_{k}}v_{j_{1}}^{l_{1}}\cdots v_{j_{k}}^{l_{k}}. $$ Let's try to compute the coefficient of $v_{j_{1}}^{l_{1}}\cdots v_{j_{k}}^{l_{k}}$ in $F\left(n\right)$. The most obvious contribution is from $f\left(n,k\right)$, which gives $\left(-1\right)^{n-k}{n \choose l_{1},\ldots,l_{k}}.$ But there are more contributions: for every $K>k$ we have terms where $K-k$ of the $l$s are zero. The contribution from $f\left(n,K\right)$ is $$ \left(-1\right)^{n-K}\sum\left\{ {n \choose l_{1},\ldots,l_{k},0,0,\ldots}:j_{k+1},\ldots,j_{K}\textrm{ distinct from }j_{1},\ldots,j_{k}\right\} . $$ All we need to do to compute this is count the number of choices of $K-k$ of the $n-k$ remaining indices, so we get $$ \left(-1\right)^{n-K}{n \choose l_{1},\ldots,l_{k}}{n-k \choose K-k}. $$ The coefficient of $v_{j_{1}}^{l_{1}}\cdots v_{j_{k}}^{l_{k}}$ in $F\left(n\right)$ is thus $$ \sum_{K=k}^{n}\left(-1\right)^{n-K}{n \choose l_{1},\ldots,l_{k}}{n-k \choose K-k}=\sum_{K=k}^{n}\left(-1\right)^{n-K}\frac{n!}{l_{1}!\cdots l_{k}!}{n-k \choose K-k}. $$ We want to show that this is $n!$ when $k=n,l_{j}=1$ and zero otherwise. The first case is easy - there is only a single term in the sum and all of $n,k,K$ are just $n$, so it falls out immediately. Let's try the zero case. Factoring out the $K$-independent terms gives $$ \left(-1\right)^{n}\frac{n!}{l_{1}!\cdots l_{k}!}\sum_{K=k}^{n}\left(-1\right)^{K}{n-k \choose K-k}. $$ Making a change of variables $j=K-k$ turns the sum to $$ \left(-1\right)^{k}\sum_{j=0}^{n-k}\left(-1\right)^{j}{n-k \choose j}. $$ This is the alternating sum of the binomial coefficients, which vanishes as required.

$\endgroup$
  • $\begingroup$ Our two proofs are basically the same (and were posted at about the same time). Your proof is less formal and easier to read ; on the other hand I find my sketch useful. $\endgroup$ – Ewan Delanoy Sep 3 '13 at 14:10
  • $\begingroup$ @EwanDelanoy: Yeah, I laughed when you submitted so soon after me. The proofs are indeed pretty much identical once you translate the notation. $\endgroup$ – Anthony Carapetis Sep 3 '13 at 14:20
  • $\begingroup$ Your proof and the one of @EwanDelanoy are both really nice. Thanks! It gonna be hard to attribute the bounty to one of you more then the other. I believe that I cannot share it between both of you. $\endgroup$ – Gilles Bonnet Sep 3 '13 at 15:26
4
$\begingroup$

This in not an answer, but an incomplete attempt of induction proof.

First, we will consider the following notation: $$\Phi_v[v_1,\ldots,v_{n-1}]=\Phi[v_1,\ldots,v_{n-1},v],$$ so $\Phi_v:V^{n-1}\to\mathbb{R}$ is the multinear symmetric operator we obtain when we fix a variable in $\Phi$. We then of course note $\phi_w(v)=\Phi_w[v,\ldots,v]=\Phi[v,\ldots,v,w]$.

In this 'answer', I show that the formula is proved if $$\phi(v_1+\cdots+v_n) =\sum_{k=1}^{n-1} \sum_{1\leq j_1<\cdots<j_k\leq n} (-1)^{n-1-k}\phi_{v_1+\cdots+v_n}(v_{j_1}+\cdots+v_{j_k}),$$ which is probably not more easy then the polarization formula itself, but that where lead me my attempt of induction.

We also write $$\Phi_v[v_1,\ldots,\hat{v_i},\ldots,v_n]=\Phi_v[v_1,\ldots,v_{i-1},v_{i+1},\ldots,v_n].$$

Let assume the formula is true for multilinear symmetric operator $V^{n-1}\to\mathbb{R}$. Since $\Phi[v_1,\ldots,v_n]=\Phi_{v_i}[v_1,\ldots,\hat{v_i},\ldots,v_n]$ by symmetry, we have: $$\Phi[v_1,\ldots,v_n]=\frac1n \sum_{i=1}^n \Phi_{v_i}[v_1,\ldots,\hat{v_i},\ldots,v_n].$$ By the induction we have $$\Phi_{v_i}[v_1,\ldots,\hat{v_i},\ldots,v_n] =\frac{1}{(n-1)!} \sum_{k=1}^{n-1} \sum_{1\leq j_1<\cdots<j_k\leq n\ ;\ j_l\neq i} (-1)^{n-1-k}\phi_{v_i} (v_{j_1}+\cdots+v_{j_k}).$$ So $$\Phi[v_1,\ldots,v_n] =\frac1{n!}\sum_{k=1}^{n-1} \sum_{1\leq j_1<\cdots<j_k\leq n} (-1)^{n-1-k} \sum_{\{i\mid i\neq j_l \forall l\leq k\}}\phi_{v_i} (v_{j_1}+\cdots+v_{j_k}).$$ But \begin{align} \sum_{\{i\mid i\neq j_l \forall l\leq k\}}\phi_{v_i} (v_{j_1}+\cdots+v_{j_k}) &={\phi_{v_1+\cdots+v_n}(v_{j_1}+\cdots+v_{j_k})-\phi_{v_{j_1}+\cdots+v_{j_k}}(v_{j_1}+\cdots+v_{j_k})}\\ &={\phi_{v_1+\cdots+v_n}(v_{j_1}+\cdots+v_{j_k})-\phi(v_{j_1}+\cdots+v_{j_k})}. \end{align} So \begin{align} &\Phi[v_1,\ldots,v_n]\\ &=\frac1{n!}\sum_{k=1}^{n-1} \sum_{1\leq j_1<\cdots<j_k\leq n} (-1)^{n-1-k} (\phi_{v_1+\cdots+v_n}(v_{j_1}+\cdots+v_{j_k})-\phi(v_{j_1}+\cdots+v_{j_k}))\\ &=\frac1{n!}\sum_{k=1}^{n-1} \sum_{1\leq j_1<\cdots<j_k\leq n} (-1)^{n-k} \phi(v_{j_1}+\cdots+v_{j_k})\\ &\qquad +\frac1{n!}\sum_{k=1}^{n-1} \sum_{1\leq j_1<\cdots<j_k\leq n} (-1)^{n-1-k}\phi_{v_1+\cdots+v_n}(v_{j_1}+\cdots+v_{j_k}).\\ \end{align} In this last expression the first part is almost the R.H.S. of the polarisation formula ; the sum goes until $n-1$ instead of $n$. But when $k=n$, $\sum_{1\leq j_1<\cdots<j_k\leq n} (-1)^{n-k} \phi(v_{j_1}+\cdots+v_{j_k}) =\phi(v_1+\cdots+v_n)$. Hence we will have prove the polarization formula if $$\phi(v_1+\cdots+v_n) =\sum_{k=1}^{n-1} \sum_{1\leq j_1<\cdots<j_k\leq n} (-1)^{n-1-k}\phi_{v_1+\cdots+v_n}(v_{j_1}+\cdots+v_{j_k}).$$

Unfortunately I don't see how to show that, it is maybe as difficult as the polarization formula.

$\endgroup$
4
+100
$\begingroup$

SKETCH OF THE PROOF : Your big sums are always sums of (sums of sums of) terms of the form $\Phi(v_{k_1},v_{k_2},\ldots ,v_{k_n})$ for some uples of indices $(k_1,k_2, \ldots ,k_n)$. Thanks to the symmetry of $\Phi$, we can always rearrange and put the uple in increasing order. You are then left with a simpler sum with less terms, where exactly one term is multilinear (the term $\Phi(v_1,v_2, \ldots ,v_n)$) and all the others are not. So this is a Rambo-like situation of one against a hundred. But fortunately for us, the combinatorial property (let us call it $P$) that for any finite set $X$, the sum $\sum_{B \subseteq X}(-1)^{|B|}$ is zero except when $X$ is empty, allows us to show that all the non-multilinear terms have zero coefficient in the sum.

THE DETAILS : Given a uple $(k_1,\ldots ,k_n)$, denote by $\rho(k_1,k_2,\ldots,k_n)$ the rearranged uple according to increasing order. (Thus, $\rho(1,3,2)=(1,2,3)$).

It is more convenient here to view uples as functions, so we shall speak of $u$ and $\rho u$ where $u$ and $\rho u$ are maps $\lbrace 1,2, \ldots, n\rbrace \to \lbrace 1,2, \ldots, n\rbrace$ and $\rho u$ is increasing. Also, we put $\psi(f)=\Phi(v_{f(1)},\ldots,v_{f(n)})$.

For an arbitrary increasing uple $i$, denote by $w(i)$ the number of uples $j$ satisfying $\rho(j)=i$. For any $A \subseteq \lbrace 1,2, \ldots ,n \rbrace$, denote by $I(A)$ the set of all increasing maps $\lbrace 1,2, \ldots ,n \rbrace \to A$. Also, let $I=I(\lbrace 1,2, \ldots, n \rbrace)$ and $V(f)=\lbrace A \subseteq \lbrace 1,2, \ldots ,n \rbrace | f\in I(A) \rbrace$ . Note that if $K(f)=\lbrace 1,2, \ldots ,n \rbrace \setminus Im(f)$, then there is a natural bijection between ${\cal P}(K(f))$ and $V(f)$, given by $B \mapsto Im(f) \cup B$.

Let $$ \lambda (A)=\phi\bigg(\sum_{a\in A}v_a\bigg) \tag{2} $$

Then, expanding $\lambda(A)$ completely shows that

$$ \lambda (A)=\sum_{f\in I(A)} w(f) \psi(f) \tag{3} $$

Then, the RHS (call it $\Phi''$) of the desired equality can be rewritten as

$$ \begin{eqnarray} \Phi'' &=& \sum_{A\subseteq \lbrace 1,2, \ldots ,n \rbrace}(-1)^{n-|A|}\lambda(A)\\ &=& \sum_{A\subseteq \lbrace 1,2, \ldots ,n \rbrace}(-1)^{n-|A|}\sum_{f\in I(A)} w(f) \psi(f) \\ &=& \sum_{f\in I}w(f)\psi(f)\sum_{A\in V(f)}(-1)^{n-|A|} \\ &=& \sum_{f\in I}w(f)\psi(f)\sum_{B\subseteq K(f)}(-1)^{n-|Im(f)|+|B|} \\ &=& w({\mathsf{id}})\psi(\mathsf{id}) \ \text{by property } P. \\ &=& n! \Phi(v_1,v_2, \ldots ,v_n) \end{eqnarray} $$

which concludes the proof.

$\endgroup$
  • $\begingroup$ I think you mean $\psi(f)=\Phi(v_{f(1)},\ldots,v_{f(n)})$, and not $\psi(f)=\phi(v_{f(1)},\ldots,v_{f(n)})$. $\endgroup$ – Gilles Bonnet Sep 3 '13 at 14:52
  • $\begingroup$ @GillesBonnet Corrected, thanks. $\endgroup$ – Ewan Delanoy Sep 3 '13 at 14:55
  • $\begingroup$ Do you have a reference for the combinatorial property P? $\endgroup$ – Gilles Bonnet Sep 4 '13 at 11:12
  • 2
    $\begingroup$ @GillesBonnet This property $P$ is called “alternating sum of binomial coefficients” in Anthony Carapetis' answer. In other words, it is the binomial Newton expansion of $(1-1)^n$. $\endgroup$ – Ewan Delanoy Sep 4 '13 at 11:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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