Is there a formula for the expansion coefficients of powers of an inner product? I would like to expand the following expression
$$\left(\sum_{i,j=1}^N \,x_i A_{ij} x_j\right)^n$$
where $\mathbf A$ is a symmetric $N\times N$ matrix, $\mathbf {x}$ is an $N$-component vector, and $n$ is a non-negative integer power.  The expansion of this expression yields a homogeneous polynomial of order $2n$ in the $x_k$.
What is the coefficient of the term $x_1^{p_1} x_2^{p_2} \cdots x_N^{p_N}$ for $p_1 + p_2 + \cdots + p_N = 2n$ in the expansion of this expression?
Has the formula been worked out before?
 A: The expression can be succintly written as ${\left({\mathbf{x}}^TA\mathbf{x} \right)}^n$, where $\mathbf{x}=(x_1,x_2,\ldots,x_N)$.
The inner product $x^TAx$ is some polynomial $p_A(\mathbf{x})$ that is a sum of monomials of degree exactly $2$.
Hence, each nonzero monomial in ${\left({\mathbf{x}}^TA\mathbf{x}\right)}^n ={\big[p_A(\mathbf{x})\big]}^n$ is of the form $x_1^{p_1}x_2^{p_2}\dots x_n^{p_N}$ with $p_i\geq 0$ and $\sum_ip_i=2n$.
Let $\rho$ be one such $N$-tuple $\rho=(p_1,p_2,\ldots,p_N)$, and let $\lVert\rho\rVert = \sum_ip_i$. We will use combinatorics to calculate the coefficient of ${\mathbf{x}}^{\rho} = x_1^{p_1}x_2^{p_2}\dots x_n^{p_N}$ in ${\left({\mathbf{x}}^TA\mathbf{x}\right)}^n$. We will consider each different way in which we can choose a term from each copy of $p_A$ in the (ordered) product ${\big[p_A(\mathbf{x})\big]}^n$ so that the end result is a ${\mathbf{x}}^{\rho}$ monomial.
Let $\mho$ be an alphabet $\mho=\{l_1,l_2,\dots,l_N\}$.
We associate to each (ordered) choice of monomial $x_iA_{ij}x_j$ in $p_A(\mathbf{x})$ the string $l_il_j$ in $\mho$.
This induces a correspondence between choices in the ordered product ${\big[p_A(\mathbf{x})\big]}^n$ and strings of length $\lVert\rho\rVert$ in $\mho$.

Example with ${\big[p_A(\mathbf{x})\big]}^3$.
  Below, the $\longleftrightarrow$ arrow indicates the correspondence between choices and strings, while the $\Rightarrow$ arrow indicates the associated coefficient of the end monomial.
$$\left[\underbrace{(x_1A_{13}x_3)}_{\text{$1^{\text{st}}$ choice}}\underbrace{(x_4A_{41}x_1)}_{\text{$2^{\text{nd}}$ choice}}\underbrace{(x_2A_{22}x_2)}_{{\text{$3^{\text{rd}}$ choice}}} \longleftrightarrow l_1l_3l_4l_1l_2l_2\right] \Rightarrow A_{13}A_{41}A_{22}$$

Notice that two different strings may give rise to the same coefficient.
For instance, $l_2l_2l_4l_1l_1l_3$ is also associated to the coefficient $A_{22}A_{41}A_{13}=A_{13}A_{41}A_{22}$, but this is because the product of the numbers $A_{ij}$ does not depend on the order of the terms.
This is not a contradiction with our correspondence, because different strings correspond to different choices (even if they are associated to the same coefficient).
Let $A(s)$ be the coefficient associated to a string $s$.
We note that $A(s)$ is in the coefficient of ${\mathbf{x}}^{\rho}$ if and only if $s$ contains $p_i$ $l_i$'s for each $i=1,2\ldots,N$. Hence, with 
\begin{equation}
S(\rho)=\left\{s\,\middle|\,
\begin{array}{l}
\text{$s$ is a string of length $\lVert \rho \rVert$ on $\mho$ and}\\
\text{for each $i=1,\dots,N$ the letter $i$ appears $p_i$ times on $s$}
\end{array}\right\},\end{equation}
then the coefficient $K(\rho)$ of ${\mathbf{x}}^{\rho}$ is given by
\begin{equation}\tag{1}\label{ksr}
K(\rho) = \sum_{s \in S(\rho)}A(s)
\end{equation}

We pause briefly to note a rather obvious lemma, that will nonetheless be useful to us.

$\textbf{Lemma}$.
  Let $\rho$ be such that each $p_i=0$, except $p_k=2n$ for some positive integer $n$.
  Then
$$K(\rho)={\left(A_{kk}\right)}^n$$

Proof.
In ${\left(\sum_{i,j=1}^N \,x_i A_{ij} x_j\right)}^n$, the only choice that yields $x_k^{2n}$ is taking $i=j=k$ in each term of the $n$ products. $\square$

In the statement of the theorem below, we highlight the following piece of notation. The hat above $c_j$ in $c_1+\ldots+\hat{c_j}+\ldots+c_N$ means $c_j$ does not feature in the sum, and $e_i$ is the vector
$$e_i=\underbrace{(0,0,\ldots,0,1,0,\ldots,0,0)}_{\text{$1$ at position $i$}}$$
With that out of the way:

$\textbf{Theorem}$ $\text{$\big(K(\rho)$ expansion$\big)$.}$
  Let $\rho=(p_1,\ldots,p_N)$, where each $p_i$ is a nonnegative integer and $\sum_ip_i=2n$.
  For each $j \in \{1,2,\ldots, N\}$ we have that
$$K(\rho)=n!\cdot\sum_{a=0}^{\left\lfloor p_j/2\right\rfloor}\frac{{\left(A_{jj}\right)}^a}{a!} \cdot F(\rho,j,a),$$
where $F(\rho,j,a)$ equals
$$\sum_{ \substack{
c_1+\ldots+\hat{c_j}+\ldots+c_N=p_j-2a\\
0\leq c_i \leq p_i
}}
\left(
\prod_{ \substack{1\leq k\leq N\\
k\neq j
}}
\frac{ {\left( A_{jk} \right)}^{c_k} } {c_k!}
\right)
\cdot
\frac{1}{ \big(n-(p_j-a)\big)! }
\cdot
K \left(
\sum\limits_{ \substack{
1\leq k\leq N\\
k\neq j
}}
(p_k-c_k)e_k
\right)$$

Notice that the expansion calculates $K(p_1,\ldots,p_N)$ in terms of coefficients $K(\overset{\sim}{p_1},\ldots,\overset{\sim}{p_N})$, where each $\overset{\sim}{p_i}\leq p_i$ and, most importantly, $\overset{\sim}{p_j}=0$.
Together with the lemma, this means $K(p_1,\ldots,p_N)$ can be calculated in at most $(N-1)$ applications of the theorem.
Proof.
We consider $A$ to be a 'free' symmetric matrix, meaning we assume no relations between the $A_{ij}$ beyond $A_{ij}=A_{ji}$.
That said, the theorem can be adapted to general 'free' matrices.
The idea behind the expansion is to rewrite $\eqref{ksr}$ in a sum of the type
\begin{equation}\tag{2}\label{krp}
K(\rho)=\sum_{\alpha}\big|\{s \in S(\rho)\,|\,A(s)=\alpha\}\big|\cdot \alpha
\end{equation}
where $|X|$ is the cardinality of set $X$.
Now, $\big|\{s \in S(\rho)\,|\,A(s)=\alpha\}\big|$ is given by a multinomial coefficient.
If $\alpha=\prod_{1\leq i<k\leq N}{\left(A_{ik}\right)}^{n_{ik}}$, and remember $\sum n_{ik}=n$ as per hypotheses, then
$$\big|\{s \in S(\rho)\,|\,A(s)=\alpha\}\big|=\frac{n!}{\prod_{1\leq i<k\leq N}n_{ik}!}$$
Next, we consider how terms $A_{ji}$ (where $j$ is the fixed index choice of the thoerem) show up in the values $\alpha$.
Afterewards, the substrings that remain have no $l_j$, so the problem is reduced to an easier one, with a smaller alphabet.
Each $A_{jj}$ corresponds to two $l_j$'s in a string $s$, while each $A_{ji}$ with $j\neq i$ corresponds to a single $l_j$.
Hence, if $a$ is the number of $A_{jj}$'s in $A(s)$ and $b$ is the number of $A_{ji}$'s with $j\neq i$, we have that $2a+b=p_j$ and that the total number of terms in $A(s)$ which feature an index $j$ is
$$a+b=p_j-a.$$
The number of terms in $A(s)$ that don't feature an index $j$ is thus $n-(p_j-a)$. Notice that $0\leq a \leq \left\lfloor p_j/2\right\rfloor$.
Now, a choice of $a$ 'well-defines' the terms $A_{jj}$'s, but, even though it defines $b$, there's still room for choice with the $A_{ji}$'s (namely, the indices $i$).
To know the terms $A_{ji}$, it suffices to choose a submultiset $M$ from
$$N=\bigcup\limits_{\substack{1\leq k\leq N\\k\neq j}}\left\{l_k^{p_k}\right\}$$
with $|M|=b=p_j-2a$, where above we're using the multiset exponential notation for multiplicities.
$M$ represents the indices $i$ (with their multiplicities).
Hence, each such submultiset has the form $M=\bigcup\limits_{\substack{1\leq k\leq N\\k\neq j}}\left\{l_k^{c_k}\right\}$ and corresponds to a solution of
\begin{equation}\tag{3}\label{msys}
\left\{
\begin{array}{ll}
c_1+\ldots+\hat{c_j}+\ldots+c_N=p_j-2a&\\
0\leq c_i \leq p_i & (\forall i\in\{1,\ldots,N\}\setminus\{j\})
\end{array}\right.
\end{equation}
Besides not having any $l_j$'s, the substring that remains will have $c_i$ fewer $l_i$'s for each $i\in\{1,\ldots,N\}\setminus\{j\}$.
This answer is getting long enough as is, but I'll try to summarize the points made and hope it makes for a satisfactory proof:


*

*We begin with the expression in $\eqref{krp}$

*We factorize terms in $\alpha$ that feature an index $j$

*There are $a$ terms with a double index $j$, and $p_j-2a$ terms with a single index $j$

*$0\leq a \leq \left\lfloor p_j/2\right\rfloor$

*Choices for the other index on terms with a single index $j$ correspond to solutions of $\eqref{msys}$

*Factorials come from multinomial coefficients that count cardinalities in $\eqref{krp}$ 

*The substring that remains will have no $l_j$'s and $(p_i-c_i)$ $l_i$'s for each $i\in\{1,\ldots,N\}\setminus\{j\}$


If you have any questions about this proof I'll be happy to answer, but I hope this is clear enough. $\square$

$\textbf{Corollary}$ $\text{$\big($Minimal $K(\rho)$ expansion$\big)$.}$
  Let $\rho$ be as in the Theorem.
  Let $P^+=\{p_i\,|\,p_i>0\}$, $I^+=\{i\,|\,p_i>0\}$ and $j \in I^+$ be such that $p_j =\min P^+$.
  Then
$$K(\rho)=n!\cdot\sum_{a=0}^{\left\lfloor p_j/2\right\rfloor}\frac{{\left(A_{jj}\right)}^a}{a!} \cdot F(\rho,j,a),$$
where $F(\rho,j,a)$ equals
$$\sum_{ \substack{
\sum\limits_{i\in I^+\setminus\{j\}}c_i\, =\,p_j-2a\\
c_i\geq 0
}}
\left(
\prod_{ k\in I^+\setminus\{j\}}
\frac{ {\left( A_{jk} \right)}^{c_k} } {c_k!}
\right)
\cdot
\frac{1}{ \big(n-(p_j-a)\big)! }
\cdot
K \left(
\sum\limits_{k\in I^+\setminus\{j\}}
(p_k-c_k)e_k
\right)$$

Notice the subscript in the summation of $F(\rho,j,a)$.
In this form, the number of terms in the summation of $F(\rho,j,a)$ can be found easily via stars and bars.
The number is
$$\binom{(p_j-2a)+\left(\left|I^+\right|-1\right)-1}{p_j-2a}= \binom{p_j+\left|I^+\right|-2a-2}{p_j-2a}$$
Proof. For $i \notin I^+$, $p_i=0$. Hence, $0\leq c_i\leq p_i$ implies $c_i=0$, and it's easy to check that there's no loss in removing them from the summation. On the other hand, $\sum_{i\in I^+\setminus{\{j\}}}c_i=p_j-2a$ and $c_i\geq 0$ imply $c_i \leq p_j-2a\leq p_j\leq p_i$, so the sum is as in the theorem. $\square$
A: Here is an answer using the symmetry of the inner product and based upon the multinomial theorem.
From the multinomial theorem
\begin{align*}
\left(\sum_{i=1}^Nx_i\right)^n=\sum_{k_1+k_2+\cdots+k_N=n}\binom{n}{k_1,k_2,\ldots,k_N}
\prod_{t=1}^{N}x_t^{k_t}\tag{1}
\end{align*}

we obtain
  \begin{align*}
\left(\sum_{i,j=1}^Nx_iA_{i,j}x_j\right)^n&=\left(\sum_{i=1}^NA_{i,i}x_i^2+2\sum_{1\leq i<j\leq N} A_{i,j}x_ix_j\right)^n\tag{2}\\
&=\sum_{k=0}^n\binom{n}{k}\left(\sum_{i=1}^NA_{i,i}x_i^2\right)^k
\left(\sum_{1\leq i<j\leq N}A_{i,j}x_ix_j\right)^{n-k}2^{n-k}\tag{3}
\end{align*}
  with
  \begin{align*}
\left(\sum_{i=1}^NA_{i,i}x_i^2\right)^k&=\sum_{k_1+k_2+\cdots+k_N=k}
\binom{k}{k_1,k_2,\ldots,k_N}\prod_{t=1}^NA_{t,t}^{k_t} x_t^{2k_t}\\
\left(\sum_{1\leq i<j\leq N}A_{i,j}x_ix_j\right)^{n-k}&=
\sum_{l_{1,2}+l_{1,3}+\cdots+l_{N-1,N}=n-k}\binom{n-k}{l_{1,2},l_{1,3},\ldots,l_{N-1,N}}
\prod_{1\leq u<v\leq N}\left(A_{u,v}x_ux_v\right)^{l_{u,v}}
\end{align*}

Comment:


*

*In (2) we use the symmetry $A_{i,j}=A_{j,i},1\leq i<j\leq N$ and separate  sums accordingly.

*In (3) we apply the binomial theorem and prepare this way the application of the multinomial theorem for two parts.
