# Mappings of indices

Next topic: Tree traversal

## Basics

Perhaps the most significant difference between tensor- and symbol-oriented computer algebra systems lies in the comparison of mathematical expressions. In the symbol-oriented CASs result of atomic comparison problem (determination of whether two expressions are equal, i.e. operation that is the main building block of such complicated routines as pattern matching) is just a logical true or false, while in the case of tensorial CAS it transforms into a complicated pattern matching problem, which produces a complicated object as a result.

The most common question, which can be asked about two expressions, is whether they define the same Tensor (to within a free indices relabelling). This question arises in such frequent routines like substitutions and reduction of similar terms. Consider the following expressions: $F_{ab}G^{bc} \mapsto F_{iq}G^{qj} \,\,=\,\, \left\{ \begin{array}{c} a \to i\\ c \to j \end{array} \right\}$ These two expressions have the same tensorial structure. The above notation means that if rename $a$ to $i$ and $c$ to $j$ in the left expression one will get exactly the same tensor as defined by the right expression. So, the result of such comparison is not just true or false, but a mapping of free indices of one expression onto free indices of another expression.

One of the major quirks of the problem lies in the fact that free and dummy indices hold completely different places. Mappings of free indices are global for expression, while dummy indices have their scopes. If some free index is present in several places, then its mapping will be the same everywhere. On the other hand, explicit names of dummies are not important (consider indices $b$ and $q$ in the first example). Besides that, dummy indices brings additional structure into expressions, which should be taken into account when finding mappings. To illustrate this features, consider the following examples: $F_{{\color{blue}a}b}G^b{}_{\color{red}c}+M_{{\color{blue}a}d}N^d{}_{\color{red}c } \mapsto F_{{\color{blue}i}q}G^q{}_{\color{red}j}+M_{{\color{blue}i}q}N^q{}_{\color{red}j } \,\,=\,\, \left\{ \begin{array}{c} a \to i\\ c \to j \end{array} \right\},$ but $F_{{\color{blue}a}b}G^b{}_{\color{red}c}+M_{{\color{blue}a}d}N^d{}_{\color{red}c } \mapsto F_{{\color{blue}i}q}G^q{}_{\color{red}j}+M_{q{\color{blue}i}}N^q{}_{\color{red}j} \,\,=\,\, \varnothing.$

In the first expression $a$ and $c$ should be renamed into $i$ and $j$ respectively in both summands in order to transform l.h.s. into the r.h.s. But, there is no mapping in the second example because structure of contractions of the second summand in the r.h.s. differs from that in the l.h.s. (if no symmetries defined for tensor $M_{ab}$).

## Multiple mappings and symmetries of tensors

In general, several mappings of indices can exist for a pair of tensors. Consider the following primitive example. Suppose that tensor $R_{ab}$ is antisymmetric, than: $R_{ab}A_c+R_{bc}A_a \mapsto R_{ij}A_k+R_{jk}A_i$ gives two mappings $\mathcal M_1=+\left\{ \begin{array}{c} a \to i\\ b \to j\\ c \to k \end{array} \right\}\quad\mbox{and}\quad \mathcal M_2=-\left\{ \begin{array}{c} a \to k\\ b \to j\\ c \to i \end{array} \right\}.$ Second mapping $\mathcal M_2$ has negative sign, which means that in order to obtain the r.h.s., one needs to apply mapping to the l.h.s. and negate the result. Sign property of mappings and processing both symmetries and antisymmetries in a common way makes these entities fully consistent with each other.

It is clear that mapping of tensor onto itself gives permutational symmetries of its indices. So, in the case of the above primitive example, one can find that $R_{ab}A_c+R_{bc}A_a \mapsto R_{ab}A_c+R_{bc}A_a \,\,=\,\, +\left\{ \begin{array}{c} a \to a\\ b \to b\\ c \to c \end{array} \right\}\,\,\mbox{and}\,\, -\left\{ \begin{array}{c} a \to c\\ b \to b\\ c \to a \end{array} \right\}.$ The last mapping represents a nontrivial antisymmetry of tensor.

## Mappings in Redberry

The entire architecture of Redberry rely on the ideas described in above subsections.

### Building mappings between tensors

In Redberry one can construct mappings from tensor from onto tensor to using % operator; the object returned (we'll call it mappings container) allows to access different mappings between these tensors. Consider the following example:

setAntiSymmetric 'R_ab'
def from = 'R_ab*A_c + R_bc*A_a'.t,
to = 'R_ij*A^k + R_j^k*A_i'.t
//create mappings
def mappings = from % to
//takes just first available mapping
println mappings.first

   > +{_a->_i, _b->_j, _c->^k}

//print all mappings
mappings.each { mapping ->
assert (mapping >> from).equals(to) //apply mapping
println mapping
}

   > +{_a->_i, _b->_j, _c->^k}
> -{_a->^k, _b->_j, _c->_i}

As it seen, mappings allows to get just first single mapping (line 7) or iterate over all possible mappings (line 9). Moreover, calculation of each subsequent mapping during iteration occurs only on the corresponding step of iteration (calculation on demand). In order to apply single mapping rules to tensor one can use ordinary >> operator (as in line 10): this will automatically perform raising or lowering of indices if it is meant by mapping and resolve dummy clashes.

Internally, mappings container contains output port of mappings, which subsequently return mappings on take() or null if no more mappings exist:

def mappings = 'g_ab'.t % 'g_cd'.t
def port = mappings.port
//take first mapping
println port.take()

   > {_a->_c, _b->_d}

//take second mapping
println port.take()

   > {_a->_d, _b->_c}

//take third mapping etc.
println port.take()

   > null


Redberry can build mappings for tensors of any complexity with any number of nested sums/products, symmetries and dummy indices:

setAntiSymmetric 'A_mn', 'F_mnab'
def from = '(A_m^n - A_m^p*A_p^n)*F_nk^i_j + A_mn*A^n_j*A^i_k'.t,
to = '-(A_d^a + A_p^a*A_d^p)*F^d_kq^i - A^a_b*A^b_q*A^i_k'.t
(from % to).each { println it }

   > -{_i->_i, _j->_q, _k->_k, _m->^a}
> +{_i->^k, _j->_q, _k->^i, _m->^a}


### Constructing single mapping

In the previous section, mapping rules were constructed by mapping one tensor onto another. However, sometimes it is necessary to rename indices of tensor using some given mapping rules. For example, if one need to rename index a to index b in some tensor, one can do:

def m = '{a -> b}'.mapping
println m >> 'f_a'.t

   > f_b

Another example:
def m = '{a -> b, b -> a}'.mapping
println m >> 'f_ab'.t

   > f_ba

One can specify different states of indices in order to perform raising or lowering:
def m = '{_a -> ^c, ^b -> _d}'.mapping
println m >> 'f_a^b'.t

   > f^c_d


One can also construct mapping from given indices from and to:

def mapping = '_ab'.si % '^cd'.si
println mapping >> 't_ab + f_ba'.t

   > t^{cd}+f^{dc}


### Example applications

Mappings in Redberry provide a very versatile way for implementing effective and simple routines. Consider few examples.

Implement Transformation that performs lowering of all tensor Indices:

def toLower = { t ->
def u = t.indices.free.upper
(u % u.inverted) >> t
} as Transformation
println toLower >> 'f^ab_cd + t_mn*t^mnab_cd'.t

   > f_{abcd}+t^{mn}_{abcd}*t_{mn}


Implement Transformation that inverts Indices of Tensor:

def invert = { t ->
def from = [], to = []
t.indices.free.each { from << it; to << it.invert(); }
(from.si % to.si) >> t
} as Transformation
println invert >> 'f^ab_cd + t_mn*t^mnab_cd'.t

   > f_{ab}^{cd}+t_{mn}*t^{mn}_{ab}^{cd}