Introduction to matrices 
Algorithms  Matrices  
Written by Jan Schulz  
Sunday, 13 July 2008 20:07  
MatricesThis 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 matricesCommon 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 (GLOBECGermany), 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 metadata. Although metadata 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 terminologyThe term matrix dates back to the middle of the 19^{th} 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 nonitalic letters to symbolise matrices. To refer to an element of a matrix the same lowercase letter is used. The element a_{i,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 a_{i,j} and refers to the element of the i^{th} row in the j^{th} column. The indices i and j are defined for nonnegative integers. A matrix A with m rows and n columns is called the m×n (read: mbyn) 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 a_{i,j} = a_{j,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 a_{i}_{,j }= 0, for i > j, the matrix is called the upper or right triangular matrix. Respectively a matrix with a_{i}_{,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 indexingThe matrix element a_{i}_{,j }is accessed by its integer indices i and j. But the range in which these indices are defined depends on the used nbased indexing. As the smallest nonnegative value of an integer variable is zero, most programming languages, like e.g. Object Pascal or C, use a 0based indexing. Thus, the upper left element of a matrix is the element a_{0,0} and the indices i and j are defined for 0 £ i £ m1 and 0 £ j £ n1. In contrast the traditional mathematical notation uses a 1based indexing. This means the first element (upper left) of a matrix A is a_{1,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 1based indexing. Some languages allow arbitrary nbased 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 z_{5,4} in 1based indexing and z_{4,3} in 0based 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 0based 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 0based 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 0based, Sedgewick (1992) prefers the 1based indexing. On these pages the concept of the 0based indexing is followed.
VectorsVectors 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 matricesAs 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 runtime. 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 a_{0,0} of the matrix A by aMatrix.Cells [0,0]. The titles of the respective rows and columns can be accessed by aMatrix.RowTitle [0] and aMatrix.ColTitle [0]. 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.
ReferencesDijkstra 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. 2^{nd} edition. Sedgewick R. (1992) Algorithmen. AddisonWesley. German translation of the 2^{nd} edition. Sylvester J. J. (1850) Additions to the Articles 'On a New Class of Theorems' and 'On Pascal's Theorem’. Philosophical Magazine, 363370. Reprint: J. J. Sylvester's Mathematical Papers (1904). Cambridge University Press, England, 1:145151. Weisstein E.W. Matrix. MathWorld  A Wolfram Web Resource. http://mathworld.wolfram.com/Matrix.html


Last Updated on Friday, 18 March 2011 18:02 