2.3.3 Compound Index Notation

An indexed expression can itself contain an indexed notation, which generates nested indexed notations, as in the following expression:

    (        )
⊙     ⊗
i∈I   j∈J

where and are two arbitrary index operators. If the two operators are different then we need to evaluate the inner expression first and the outer afterwards. A notable example is a system of m linear equations with n variables that is commonly noted as follows:

       a  x  = b   with   i ∈ {1 ...m }
        i,j  j   i

Using the list operator . , these formula can be noted as a nested indexed notation, that is, a notation where the index expression contains itself an indexed notation, with the outer index operator . and the inner index operator as . The nested notation then is noted as follows:

          (                  )
∧.            ∑
          (        ai,jxj = bi)
  i∈{1...m}   j∈{1...n}

This notation is a very short writing of the following system of equations:

a1,1x1 + a1,2x2 + + a1,n-1xn-1 + a1,nxn = b1
a2,1x1 + a2,2x2 + + a2,n-1xn-1 + a2,nxn = b2
am,1x1 + am,2x2 + + am,n-1xn-1 + am,nxn = bm

On the other hand, if both index operators in (5) are identical, then the two index operators can be merged in the following way:

    (        )
⊙     ⊙            ⊙
          Fi,j   =        Fi,j
 i∈I   j∈J         i∈I, j∈J

It means that we merge the operator and unify also the indexing terms to be written as “i I, j J”. It signifies that we build every tuple of the Cartesian Product of the two sets: (i,j) I × J. As an example, suppose I = {1, 2} and J = {a,b,c} then the index set is I × J = {(1,a), (1,b), (1,c), ((2,a), (2,b), (2,c)} – it consists of 6 tuples. There are two active indexes i and j, or a tuple (i,j) of active indexes. Hence we also may write this expression in the following way:


where the index set is I × J and the active index is replaced by the notation (i,j) which is called an active index tuple. In this case, the names within the active index tuples are called active indices. The active indices are now place-holders for the single components of the tuple.

The index set I × J is also a set, the set of all tuples in the Cartesian Product. Hence if we do not need to access the single components within the product, we can replace (i,j) by a single active index, say k, and I × J can be replaced by a set name, say K. Now we see that the previous formula really reduces to our general indexed notation, which is as follows:

  ⊙           ⊙
        Fi,j =     Ek
(i,j)∈I×J       k∈K

Since indexed notation with multiple indexing terms really is reducible to indexed notation with one indexing term, we only need to extend the definition of index sets:

Definition: A compound index set is any countable (finite or infinite) collection of elements, where all elements are either indivisible items called atoms or tuples containing all the same number of components.

Some care has to be taken, if the index-sets are tuple lists.

Sometimes access to the tuple itself and to its components is needed. In such cases, one could use a combined syntax as in:

          (E ,F   )
            k   i,j

where (Ek,Fi,j) is the indexed expression.

Tuples list as index-sets are very common. Let the set I be a number of locations of clients in a region. Then J I × I is a tuple list and a tuple can be interpreted as direct connection (route) from a location i to a location j, and let Pi,j be true if there is a route from i to j, then the set of all connections is :

J = { (i,j)|Pi,j , i,j ∈ I}

Suppose now, that fi,j is the number of vehicles that are driving from i to j in a hour. Then we can calculate the number of vehicles (xi) arriving at each location i per hour, it is:

xi =       fi,j  forall j ∈ I

How can this be expressed with the tuple list J without using Pi,j? One variant is:

xi =        fi,j   forall i ∈ (i,j) ∈ J

This notation is a little bit clumsy. In this context, (i,j) J is often abbreviated as J[i,j] and the expression becomes:

xi =       fi,j   forall i ∈ J[i,j]

The previous considerations can be generalized to tuples of more than two components: If I1,,Ip are p > 0 non-empty – not necessary different – index sets containing only atoms, then any subset of the Cartesian product I1 ×⋅⋅⋅× Ip is also an index set, called compound index set. Its elements are ordered tuples denoted by (i1,,ip) with i1 I1,,ip Ip. Each item ik with k ∈{1p} in a tuple (i1,,ip) is called a component within the tuple. The integer p determines the arity (dimension) of the tuple. All elements in a compound index set have the same arity, and the order of the components is significant. If the underlying index sets I1,,Ip are all ordered, then the order of the corresponding compound index set is determined by the lexicographic ordering: the right most component is varied first.

The active index tuple (i1,,ip) contains the active indices of each component for the underlying index sets. If an active index is needed for the tuple itself, it can be preceded by a new unique name as in k = (i1,,ip), called named active index tuple. k is now an active index for the tuple itself. This notation can be extended to any subset of components of the active index tuple. For example, if an active index is used for a sub-tuple consisting of the second, fourth and p-th component besides an index for the tuple itself, one could write this as: “k1 = (i2,i4,ip),k = (i1,,ip)”.

We may call this a list of named active index tuples. It is important to note that every name for a sub-tuple (the names before the equal signs) as well as all active indices in the last (complete) active index tuple must be different from each other; however, all names in the other sub-tuples must occur in the last tuple, because they only define a selection from the last tuple. (Of course, the same selection may turn up more than once, defining several active indices for the same sub-tuple.)

The previous considerations can now be generalized to a list of p indexing terms as follows (where K I1 ×⋅⋅⋅× Ip):

   ⊙                      ⊙                      ⊙            ⊙
          Ei1,...,ip ,                 Ei1,...,ip ,            Ek ,      Ek
i1∈I1,...,ip∈Ip           (i1,...,ip)∈I1×⋅⋅⋅×Ip           k∈I1×⋅⋅⋅×Ip       k∈K

All tuples in the indexing terms have arity p. All four indexing expressions represent a p-dimensional table of expressions. Simple index sets (which contain only atoms) can be interpreted as compound index sets with arity 1. In this case, the parentheses around the ”tuple“ are not needed.

The use of indexed notation together with compound index sets, that is, sets which are subsets of some Cartesian Product, might be considered as a purely theoretical exercise. However, this is not the case. This notation is extremely useful in practice, and it is worth while to understand the mechanism and the notation very well. Therefore, let us give an example.