Is there a formula for the expansion coefficients of powers of an inner product?

Question

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?

Answer 1

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$

Answer 2

Hint:

In the $3\times3$ case, the sum is

$$A_{11}x_1^2+A_{12}x_1x_2+A_{13}x_1x_3+A_{22}x_2^2+A_{23}x_2x_3+A_{33}x_3^2$$

where by convenience we have absorbed the factor $2$ in the coefficients $A_{ij},i\ne j$.

Then by the multinomial theorem, the $p^{th}$ power is

$$\sum_{k_{11}+k_{12}+k_{13}+k_{22}+k_{23}+k_{33}=p}\binom p{k_{11},k_{12},k_{13},k_{22},k_{23},k_{33}} A_{11}^{k_{11}}A_{12}^{k_{12}}A_{13}^{k_{13}}A_{22}^{k_{22}}A_{23}^{k_{23}}A_{33}^{k_{33}}\\ x_1^{2k_{11}}(x_1x_2)^{k_{12}}(x_1x_3)^{k_{13}}x_2^{2k_{22}}(x_2x_3)^{k_{23}}x_3^{2k_{33}}$$ or $$\sum_{k_{11}+k_{12}+k_{13}+k_{22}+k_{23}+k_{33}=p}\binom p{k_{11},k_{12},k_{13},k_{22},k_{23},k_{33}} A_{11}^{k_{11}}A_{12}^{k_{12}}A_{13}^{k_{13}}A_{22}^{k_{22}}A_{23}^{k_{23}}A_{33}^{k_{33}}\\ x_1^{2k_{11}+k_{12}+k_{13}} x_2^{k_{12}+2k_{22}+k_{23}}x_3^{k_{13}+k_{23}+2k_{33}}.$$

Then for given $p_1+p_2+p_3=2p$, the coefficient of $x_1^{p_1}x_2^{p_2}x_3^{p_3}$ is

$$\sum_{2k_{11}+k_{12}+k_{13}=p_1,\\k_{12}+2k_{22}+k_{23}=p_2,\\k_{13}+k_{23}+2k_{33}=p_3}\binom p{k_{11},k_{12},k_{13},k_{22},k_{23},k_{33}} A_{11}^{k_{11}}A_{12}^{k_{12}}A_{13}^{k_{13}}A_{22}^{k_{22}}A_{23}^{k_{23}}A_{33}^{k_{33}}.$$

The summation can be explicited as a summation on $k_{11}$, then $k_{12}$, from which $k_{13}$ is implied, then on $k_{22}$, from which the remaining indexes are implied.

$$\sum_{k_{11}=0}^{p_1/2}\sum_{k_{12}=0}^{p_1-2k_{11}}\sum_{k_{22}=0}^{p_2-k_{12}}\\ \binom p{k_{11},k_{12},p_1-2k_{11}-k_{12},k_{22},p_2-k_{12}-2k_{22},(p_3-k_{13}-k_{23})/2}\\ A_{11}^{k_{11}}A_{12}^{k_{12}}A_{13}^{p_1-2k_{11}-k_{12}}A_{22}^{k_{22}}A_{23}^{p_2-k_{12}-2k_{22}}A_{33}^{(p_3-k_{13}-k_{23})/2}.$$

For dimension $N$, you will get $T_N$ nested sums ($N^{th}$ triangular number) with the products of the $T_N$ matrix elements to some powers and the corresponding multinomial coefficient.

Answer 3

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.