Index notation

In mathematics and computer programming, index notation is used to specify the elements of an array of numbers. The formalism of how indices are used varies according to the subject. 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.

In mathematics

It is frequently helpful in mathematics to refer to the elements of an array using subscripts. The subscripts can be integers or variables. The array takes the form of tensors in general, since these can be treated as multi-dimensional arrays. Special (and more familiar) cases are vectors (1d arrays) and matrices (2d arrays).

The following is only an introduction to the concept: index notation is used in more detail in mathematics (particularly in the representation and manipulation of tensor operations). See the main article for further details.

One-dimensional arrays (vectors)

A vector treated as an array of numbers by writing as a row vector or column vector (whichever is used depends on convenience or context):

Index notation allows indication of the elements of the array by simply writing a_i, where the index i is known to run from 1 to n, because of n-dimensions.Cite error: A <ref> tag is missing the closing </ref> (see the help page).

Multidimensional arrays

Things become more interesting when we consider arrays with more than one index, for example, a two-dimensional table. We have three possibilities:

make the two-dimensional array one-dimensional by computing a single index from the two
consider a one-dimensional array where each element is another one-dimensional array, i.e. an array of arrays
use additional storage to hold the array of addresses of each row of the original array, and store the rows of the original array as separate one-dimensional arrays

In C, all three methods can be used. When the first method is used, the programmer decides how the elements of the array are laid out in the computer's memory, and provides the formulas to compute the location of each element. The second method is used when the number of elements in each row is the same and known at the time the program is written. The programmer declares the array to have, say, three columns by writing e.g. elementtype tablename[][3];. One then refers to a particular element of the array by writing tablename[first index][second index]. The compiler computes the total number of memory cells occupied by each row, uses the first index to find the address of the desired row, and then uses the second index to find the address of the desired element in the row. When the third method is used, the programmer declares the table to be an array of pointers, like in elementtype *tablename[];. When the programmer subsequently specifies a particular element tablename[first index][second index], the compiler generates instructions to look up the address of the row specified by the first index, and use this address as the base when computing the address of the element specified by the second index.

void mult3x3f(float result[][3], const float A[][3], const float B[][3])
{
  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 languages

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.

References

Programming with C++, J. Hubbard, Schaum's Outlines, McGraw Hill (USA), 1996, ISBN 0-07-114328-9
Tensor Calculus, D.C. Kay, Schaum's Outlines, McGraw Hill (USA), 1988, ISBN 0-07-033484-6
Mathematical methods for physics and engineering, K.F. Riley, M.P. Hobson, S.J. Bence, Cambridge University Press, 2010, ISBN 978-0-521-86153-3