Index notation

Index notation is used in mathematics to refer to the elements of matrices or the components of a vector. The formalism of how indices are used varies according to the discipline. In particular, there are different methods for referring to the elements of a list, a vector, or a matrix, depending on whether one is writing a formal mathematical paper for publication, or when one is writing a computer program.

It is quite common in some mathematical proofs to refer to the elements of an array using subscripts, and in some cases superscripts. The use of superscripts is frequently encountered in the theory of general relativity. The following line states in effect that the each of the elements of a vector c are equal to the sum of the elements of vectors a and b

<math>\mathbf{c}_j = \mathbf{a}_j + \mathbf{b}_j<math>

so

<math>\mathbf{c}_0 = \mathbf{a}_0 + \mathbf{b}_0<math>

<math>\mathbf{c}_1 = \mathbf{a}_1 + \mathbf{b}_1<math>

and so on.

See also: Summation convention

In several programming languages, index notation is a way of addressing elements of an array. This method is used since it is closest to how it is implemented in assembly language whereby the first element of the address is used as a base and a multiple (the index) of the element size is used to address inside the array.

For example, a block of memory at location 0x3000 is the base address, and if we are storing 4 byte integers, then elements in this block of memory are at memory locations 0x3000, 0x3004, 0x3008, 0x300c, ..., 0x3000 + 4n. In general, the memory location of the ith element with base address b and element size s is b+is.

C implementation details

In the C programming language, we can write the above as

base + i*sizeof(type)

where type is the type of elements in the array, and base is a pointer to the base of the array. C however, lets you omit the sizeof specifier (it will calculate this for you).

However, to get what is stored at that memory location, we need to dereference with the * operator thus:

*(base + i)

Yet this is not simple enough generally to repeat always in code, so C defines a shortcut:

base[i]

which is equivalent to the expression above. C converts an expression to the "square bracket" form to the above "round bracket" form. (Coincidentally, since addition is commutative, this allows for obscure expressions such as 3[array] which is equivalent to array[3] since both are converted to a correct expression, *(array + 3) = *(3 + array).)

So, for example, if we have an array in C as

a[3] = {3, 4, 5}

then a[0] is 3, a[1] is 4, a[2] is 5. This also works for dynamically allocated arrays, since the block of memory is simply in another location.

Multidimensional arrays

Things become more interesting when we consider arrays with more than one index, for example, a two-dimensional table. We can either do two things:

• make the two-dimensional array one-dimensional
• consider a one-dimensional array of each element in a one-dimensional array

The first is seldom used since it requires a conversion of a two-dimensional index into a one-dimensional index.

In C, the second approach is used. To represent a two-dimensional array, we consider a one-dimensional array of memory addresses to the start of other one-dimensional arrays. The first index then is used for the first array, to get a memory address of the second array, where we use the second index for the element.

For example, if we have an array called table, then, we have two base addresses - the base address of the array, which in C, is just called table (the variable name itself), and the base address of table[i]. To index an element table[i][j], note that this can be thought of as (table[i])[j]. In the brackets, we get the base address of table[i] to which we index to j. The pointer form then is

*(*(base + i) + j).

Example

This function multiplies two floating point valued matrices together (assuming that they all are 3 by 3 in size and that there is memory allocated for the result<tt> matrix).

void 
matrix_multiply(float **result, float **A, float **B)
{
  int i, j, k;
  for(i=0;i<3;i++)
  for (j=0;j<3;j++) {
       result[i][j]=0;
       for (k=0;k<3;k++)
          result[i][j] += A[i][k]+B[k][j];
  }
}

In other programming languages such as Pascal, indices may start at 1, so indexing in a block of memory can be changed to fit a start-at-1 addressing scheme by a simple linear transformation - in this scheme, the memory location of the ith element with base address b and element size s is b+(i-1)s.