|Introduction to matrices|
|Algorithms - Matrices|
|Written by Jan Schulz|
|Sunday, 13 July 2008 20:07|
This section is an introduction to matrices and their use in computational tasks. A couple of algorithms are given to handle matrices and to solve numerical problems that can be displayed by matrices.
Tables and matrices
Common ways to display data that can be organised in cells are cross tabulations. A cell in a cross tabulation gives an entity, which is characteristic for the intercept of the meaning of its row and column. Thus, the relevance of each cell is intrinsic to the position in the table. The respective meaning is often given by captions at the left and upper rim of the table.
Rows mainly represent a set of parameters measured for a unique event, like a sample or measurement campaign. The scheme is sometimes reverted, so that events are organised column wise. From the computational purposes the first method should be preferred. As the number of parameters is normally determined at the design time of experiments or campaigns it eases the process of data handling.
Excerpt of a zooplankton data set from the German Global Ocean Ecosystem Dynamics project (GLOBEC-Germany), doi://10.1594/PANGAEA.701183.
The above table is an excerpt of depth distributions of some marine zooplankton species. The uppermost row bears information on the respective column content, while the leftmost column assigns an index to every row. This index is often discarded, as it is intrinsic to the sequence in which rows are listed.
The columns used for the description of data are referred to as meta-data. Although meta-data give information on important properties of a data set it is the count data one is mainly interested to analyse. To investigate these count data with e.g. numerical methods requires a so called matrix form. A matrix is a form of tabulated data that can be calculated with. The matrix Z for the above zooplankton data looks like:
It can be seen that the rows and columns of the matrix just contain values one can perform calculations with. This distinguishes matrices from ordinary tables, where also unspecified information can be tabulated.
Matrix notation and terminology
The term matrix dates back to the middle of the 19th century and was first used by the mathematician Sylvester (1850) for the mould of arranged numbers. His contemporary colleague Dodgsen (1867; better known under his pen name Lewis Carroll and as the author of ‘Alice in Wonderland’) introduced the more precisely defined term ‘block’. Anyhow, the use of the word matrix prevailed (see also Weisstein).
Today the term matrix is used for a rectangular table of elements. The type of the elements is an abstract quantity that can be calculated with. The elements are surrounded by parenthesis or square brackets.
In equations it is common to use bold uppercase and non-italic letters to symbolise matrices. To refer to an element of a matrix the same lowercase letter is used. The element ai,j of a matrix A is addressed by its indices i and j. By convention the first index refers to the row, the second to the column. The notation A [i, j] is equivalent to ai,j and refers to the element of the ith row in the jth column. The indices i and j are defined for non-negative integers. A matrix A with m rows and n columns is called the m×n (read: m-by-n) matrix with m and n being the dimensions of the matrix. Sometimes the dimensioning is written below the letter.
The diagonal of a matrix are the elements where i = j. Thus the diagonal are the elements that run from the upper left stepping down and right each time until the rim of the matrix is reached. When all elements of a matrix ai,j = aj,i (mirrored along the main diagonal) the matrix is symmetric.
When m = n it is said that the matrix is square, respectively has the same number of rows as it has columns. In square matrices the diagonal runs from the upper left down to the lower right element. Square matrices with elements being one on the diagonal and zeroes on all other positions are called identity or unit matrices.
When only elements above the diagonal of a square matrix have entries and the elements ai,j = 0, for i > j, the matrix is called the upper or right triangular matrix. Respectively a matrix with ai,j = 0, for i < j, is called the lower or left triangular matrix. When the diagonal elements of a triangular matrix are completely zero the matrix is called a strict upper or lower triangular matrix.
A word on indexing
The matrix element ai,j is accessed by its integer indices i and j. But the range in which these indices are defined depends on the used n-based indexing. As the smallest non-negative value of an integer variable is zero, most programming languages, like e.g. Object Pascal or C, use a 0-based indexing. Thus, the upper left element of a matrix is the element a0,0 and the indices i and j are defined for 0 £ i £ m-1 and 0 £ j £ n-1.
In contrast the traditional mathematical notation uses a 1-based indexing. This means the first element (upper left) of a matrix A is a1,1 and i and j are defined for 1 £ i £ m and 1 £ j £ n. Various programming languages, like e.g. Fortran or MatLab, make use of a default 1-based indexing. Some languages allow arbitrary n-based indexing, so that a programmer can choose lower and upper bounds freely and even define negative bounds, like e.g. in Visual Basic.
In the above zooplankton example the element z5,4 in 1-based indexing and z4,3 in 0-based indexing both refer to the element that has the value 1203.20. Both notations are valid indices and the element they refer to depends on the initial definition. Thus, one should have an eye on the used definition when reading algorithms.
There is a debate about the advantage of the different methods. Supporters on either side have good arguments for their preference. Anyhow, the use of the 0-based indexing allows several code performance optimisations, like the use of the processors automatically set zero flag for termination control of loops. Thus, comparisons can be saved and the flag is directly evaluated by a jump on zero command on the level of the machine language. Processing large arrays this can bring significant increase in processing speed. Today most modern compilers should perform this code improvement automatically, if possible. Furthermore, variables can be used for direct access when upper and lower bounds equal an element’s index. Beside this there are a couple of further reasons, why a 0-based indexing should be used in programming (see e.g. Dijkstra 1982). The use is even not congruent among several standard works of informatic. While Press et al. (2003) use 0-based, Sedgewick (1992) prefers the 1-based indexing. On these pages the concept of the 0-based indexing is followed.
Vectors can be interpreted as matrices of which the dimension of rows or the dimension of columns is 1. An excerpt of one row or one column from a larger matrix is also a respective vector. According to the dimension which is 1 vectors can be distinguished. A m×1 matrix R is called a row vector:
A 1×n matrix C is a column vector:
Although the dispensable index is often omitted when written, it can be helpful to note both for algorithms where vectors are handled as special cases of matrices.
Definition of a record variable for matrices
As the dimension of a matrix depends on the application a dynamic ‘array of array’ structure is best used for computational implementations. The term dynamic states that dimensions are not defined at design time and can be adjusted during run time. This allows considering matrices of arbitrary size, as long as memory space is available. But it also requires algorithms adapted to handle arrays whose size is just known at run-time.
Here a data type t2dVariantarrayDouble for matrices is introduced, which is widely used with the algorithms on these pages. Within the record the elements of the properly matrix are stored in the variable Cells, which is defined as Array of Array of Double. The first dimension defines a one dimensional array of references. These references point at memory positions where the dynamic arrays of the row elements, respectively the content of the columns, are located. Thus, the number of rows can not vary, but rows may have different numbers of elements. This may be due e.g. to insufficient code or manual modifications.
Although the properly matrix must not contain information other than can be calculated with, it is often desirable to keep names for rows and columns. For this reason it has proven useful to include further arrays. For the titles of the rows and columns two dynamic arrays are defined as Array of String. Additionally a string variable is defined, where one can assign a name for a matrix. Titles for rows and columns, as well as the name of the matrix, are just for informational purposes. Thus, the information is separated from Cells containing the data. The four variables are grouped to a record that can be passed among functions. The complete declaration is:
Type t2dVariantArrayDouble = Record
A matrix variable is declared by:
Var aMatrix : t2dVariantArrayDouble;
It must be kept in mind that a newly declared variable has zero elements for Cells, RowTitles and ColTitles and MatrixName is of zero length. Trying to access elements of the dynamic arrays prior to initialisation results in a runtime ‘out of range’ error. After initialisation it is possible to access the upper left element a0,0 of the matrix A by aMatrix.Cells [0,0]. The titles of the respective rows and columns can be accessed by aMatrix.RowTitle  and aMatrix.ColTitle . The name of the matrix is accessed by aMatrix.MatrixName.
Although t2dVariantArrayDouble is used for several algorithms on these pages most algorithms can also implemented with a dynamic variable defined as Array of Array. In this case the respective code lines regarding titles for rows and columns and the name of the matrix need to be deleted in the sources. By this data are reduced to a proper matrix, but loose the possibility to entrain the additional information. Additionally it might be interesting for a couple of applications to define records of the t2dVariantArray type with Cells defined as integer, date, string or anything else that can be calculated with.
Dijkstra E.W. (1982) http://www.cs.utexas.edu/users/EWD/transcriptions/EWD08xx/EWD831.html
Dodgson, C. L. (1867) An elementary treatise on determinants, with their application to simultaneous linear equations and algebraical geometry. Macmillan, London.
Press W.H., Teukolsky S.A., Vetterling W.T., Flannery B.P. (2003) Numerical Recipes in C++, The Art of Scientific Computing. Cambridge University Press. 2nd edition.
Sedgewick R. (1992) Algorithmen. Addison-Wesley. German translation of the 2nd edition.
Sylvester J. J. (1850) Additions to the Articles 'On a New Class of Theorems' and 'On Pascal's Theorem’. Philosophical Magazine, 363-370. Reprint: J. J. Sylvester's Mathematical Papers (1904). Cambridge University Press, England, 1:145-151.
Weisstein E.W. Matrix. MathWorld - A Wolfram Web Resource. http://mathworld.wolfram.com/Matrix.html
|Last Updated on Friday, 18 March 2011 18:02|