A Faà di Bruno’s formula with tensors

Recently, working on k-order perturbation in dynare, I had to compute high-order derivatives of composite vector-valued functions. In their 2004 mimeo « Solving Stochastic Dynamic Equilibrium Models: A k-Order Perturbation Approach », Michel Juillard and Ondra Kamenik mention a Faà di Bruno’s formula with tensors using the Einstein summation convention. There is neither a demonstration nor a source pointing to it despite the usefulness of such a formula. I have unsuccessfuly looked for an equivalent expression in the mathematical literature. Let’s take a peek at it.

I adopt the elegant terminology of Tsoy-Wo Ma in its 2009’s article « Higher Chain Formula Proved by Combinatorics. » published in The Electronic Journal of Combinatorics.

Consider a function \(h : x \in X \subset \mathbb{R}^{\nu} \overset{f}{\rightarrow} y \in Y \subset \mathbb{R}^{\mu} \overset{g}{\rightarrow} z \in \mathbb{R}\) where \(X\) and \(Y\) are open sets.

I denote \(\mathbb{P}_n\) the set of partitions of \(\{1,…,n\}\) and \(P_\mu\) the set of functions from a partition of \(\{1,…,n\}\) into \(\{1,…,\mu\}\).

Tsoy-Wo Ma demonstrates the following Lemma:

\(\frac{\partial^n z}{\partial t_1 … \partial t_n} = \sum_{P \in \mathbb{P}_n} \sum_{\lambda \in P_\mu} \left\{ \left(\prod_{B \in P} \frac{\partial}{\partial y_{\lambda(B)}} \right) z \right\} \left\{ \prod_{B \in P} \left[ \left( \prod_{b \in B} \frac{\partial}{\partial t_b}\right) y_{\lambda(B)} \right] \right\}\)

where \(t_i\) denotes one of the variables \(x_1, …, x_{\nu}\).

I denote \(\mathbb{P}_n^k\) the partitions of \(\{1, …, n \}\) with \(k\) classes \(k \in \{ 1,…,n\}\), which is a partition of \(\mathbb{P}_n\). Thus, the formula above becomes

\(\frac{\partial^n z}{\partial t_1 … \partial t_n} = \sum_{k=1}^n \sum_{P \in \mathbb{P}_n^k} \sum_{\lambda \in P_\mu} \left\{ \left(\prod_{j = 1}^{k} \frac{\partial}{\partial y_{\lambda(P_j)}} \right) z \right\} \left\{ \prod_{j = 1}^{k} \left[ \left( \prod_{b \in P_j} \frac{\partial}{\partial t_b}\right) y_{\lambda(P_j)} \right] \right\}\)

where \(P_j\) is the \(j\)-th block of partition \(P\), \(j \in \{1,…,k\}\).

Introducing the Einstein notation yields

\(\left[ h_{x^n} \right]_{t_1 … t_n} = \sum_{k=1}^n \sum_{P \in \mathbb{P}_n^k} \sum_{\lambda \in P_\mu} \left[ g_{y^k} \right]_{ \lambda (P_1) … \lambda (P_k) } \prod_{j = 1}^{k} \left[ f_{x^{\mid P_j \mid}}^{\lambda (P_j)} \right]_{t \left( P_j \right)}\)

where \(\mid P_j \mid\) is the cardinal of the block \(P_j\) and \(t \left( P_j \right)\) is the collection of \(t\) indexes the \(P_j\) block contains.

Given \(P \in \mathbb{P}_n^k\), note that summing over all \(\lambda \in P_\mu\) is the same as summing over all tuples \(\left( \beta_1, …, \beta_k \right) \in \left\{1, …, \mu \right\}^k\). Using the conventions of the Einstein notation, the following simplification arises

\(\begin{aligned}\sum_{\lambda \in P_\mu} \left[ g_{y^k} \right]_{ \lambda (P_1) … \lambda (P_k) } \prod_{j = 1}^{k} \left[ f_{x^{\mid P_j \mid}}^{\lambda (P_j)} \right]_{t \left( P_j \right)} &= \sum_{\beta_1, …, \beta_k} \left[ g_{y^k} \right]_{ \beta_1 … \beta_k } \prod_{j = 1}^{k} \left[ f_{x^{\mid P_j \mid}}^{\beta_j} \right]_{t \left( P_j \right)}\\
&= \left[ g_{y^k} \right]_{ \beta_1 … \beta_k } \left[ f_{x^{\mid P_1 \mid}} \right]_{t \left( P_1 \right)}^{\beta_1} … \left[ f_{x^{\mid P_k \mid}} \right]_{t \left( P_k \right)}^{\beta_k}\end{aligned}\)

As a result, the Faà di Bruno’s formula in tensor notation with the Einstein summation convention appears.
\(\left[ h_{x^n} \right]_{t_1 … t_n} = \sum_{k=1}^n \sum_{P \in \mathbb{P}_n^k} \left[ g_{y^k} \right]_{ \beta_1 … \beta_k } \left[ f_{x^{\mid P_1 \mid}} \right]_{t \left( P_1 \right)}^{\beta_1} … \left[ f_{x^{\mid P_k \mid}} \right]_{t \left( P_k \right)}^{\beta_k}\)

Leave a Comment

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *