%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% %A matrix.tex GAP documentation Martin Schoenert %% %A @(#)$Id: matrix.tex,v 3.7 1994/06/23 13:30:29 vfelsch Rel $ %% %Y Copyright 1990-1992, Lehrstuhl D fuer Mathematik, RWTH Aachen, Germany %% %% This file describes the matrix data type, its operations and functions. %% %H $Log: matrix.tex,v $ %H Revision 3.7 1994/06/23 13:30:29 vfelsch %H modified an example %H %H Revision 3.6 1994/06/23 08:50:40 ahulpke %H added PrintArray %H %H Revision 3.5 1994/02/28 06:57:50 fceller %H fixed description of 'KronckerProduct' %H %H Revision 3.4 1993/02/19 10:48:42 gap %H adjustments in line length and spelling %H %H Revision 3.3 1993/02/11 17:14:10 martin %H vectors may now contain records %H %H Revision 3.2 1993/02/05 09:05:59 felsch %H examples fixed %H %H Revision 3.1 1992/03/20 16:34:52 martin %H initial revision under RCS %% \Chapter{Matrices}% \index{matrix}\index{type!matrices} Matrices are an important tool in algebra. A matrix nicely represents a homomorphism between two vector spaces with respect to a choice of bases for the vector spaces. Also matrices represent systems of linear equations. In {\GAP} matrices are represented by list of vectors (see "Vectors"). The vectors must all have the same length, and their elements must lie in a common field. The field may be the field of rationals (see "Rationals"), a cyclotomic field (see "Cyclotomics"), a finite field (see "Finite Fields"), or a library and/or user defined field (or ring) such as a polynomial ring (see "Polynomials"). The first section in this chapter describes the operations applicable to matrices (see "Operations for Matrices"). The next sections describes the function that tests whether an object is a matrix (see "IsMat"). The next sections describe the functions that create certain matrices (see "IdentityMat", "NullMat", "TransposedMat", and "KroneckerProduct"). The next sections describe functions that compute certain characteristic values of matrices (see "DimensionsMat", "TraceMat", "DeterminantMat", "RankMat", and "OrderMat"). The next sections describe the functions that are related to the interpretation of a matrix as a system of linear equations (see "TriangulizeMat", "BaseMat", "NullspaceMat", and "SolutionMat"). The last two sections describe the functions that diagonalize an integer matrix (see "DiagonalizeMat" and "ElementaryDivisorsMat"). Because matrices are just a special case of lists, all operations and functions for lists are applicable to matrices also (see chapter "Lists"). This especially includes accessing elements of a matrix (see "List Elements"), changing elements of a matrix (see "List Assignment"), and comparing matrices (see "Comparisons of Lists"). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Operations for Matrices} ' + ' \\ ' + ' This forms evaluates to the sum of the matrix and the scalar . The elements of and must lie in a common field. The sum is a new matrix where each entry is the sum of the corresponding entry of and . ' + ' This form evaluates to the sum of the two matrices and , which must have the same dimensions and whose elements must lie in a common field. The sum is a new matrix where each entry is the sum of the corresponding entries of and . ' - ' \\ ' - ' \\ ' - ' The definition for the '-' operator are similar to the above definitions for the '+' operator, except that '-' subtracts of course. ' \*\ ' \\ ' \*\ ' This forms evaluate to the product of the matrix and the scalar . The elements of and must lie in a common field. The product is a new matrix where each entry is the product of the corresponding entries of and . ' \*\ ' This form evaluates to the product of the vector and the matrix . The length of and the number of rows of must be equal. The elements of and must lie in a common field. If is a vector of length and is a matrix with rows and columns, the product is a new vector of length . The element at position is the sum of '[] \*\ [][]' with running from 1 to . ' \*\ ' This form evaluates to the product of the matrix and the vector . The number of columns of and the length of must be equal. The elements of and must lie in a common field. If is a matrix with rows and columns and is a vector of length , the product is a new vector of length . The element at position is the sum of '[][] \*\ []' with running from 1 to . ' \*\ ' This form evaluates to the product of the two matrices and . The number of columns of and the number of rows of must be equal. The elements of and must lie in a common field. If is a matrix with rows and columns and is a matrix with rows and columns, the result is a new matrix with rows and columns. The element in row at position of the product is the sum of '[][] \*\ [][]' with running from 1 to . ' / ' \\ ' / ' \\ ' / ' \\ ' / ' In general ' / ' is defined as ' \*\ \^-1'. Thus in the above forms the right operand must always be invertable. ' \^\ ' This form evaluates to the -th power of the matrix . must be a square matrix, must be an integer. If is negative, must be invertible. If is 0, the result is the identity matrix, even if is not invertible. ' \^\ ' This form evaluates to the conjugation of the matrix by the matrix , i.e., to '\^-1 \*\ \*\ '. must be invertible and must be such that these product can be computed. ' \^\ ' This is in every respect equivalent to ' \*\ '. This operations reflects the fact that matrices operate on the vector space by multiplication from the right. ' + ' \\ ' + ' \\ ' - ' \\ ' - ' \\ ' \*\ ' \\ ' \*\ ' \\ ' / ' A scalar may also be added, subtracted, multiplied with, or divide into a whole list of matrices . The result is a new list of matrices where each matrix is the result of performing the operation with the corresponding matrix in . ' \*\ ' \\ ' \*\ ' A matrix may also be multiplied with a whole list of matrices . The result is a new list of matrices, where each matrix is the product of and the corresponding matrix in . ' / ' This form evaluates to ' \*\ \^-1'. must of course be invertable. ' \*\ ' This form evaluates to the product of the vector and the list of matrices . The length of and must be equal. All matrices in must have the same dimensions. The elements of and the elements of the matrices in must lie in a common field. The product is the sum of '[] \*\ []' with running from 1 to . 'Comm( , )' 'Comm' returns the commutator of the matrices and , i.e., '\^-1 \*\ \^-1 \*\ \*\ '. and must be invertable and such that these product can be computed. There is one exception to the rule that the operands or their elements must lie in common field. It is allowed that one operand is a finite field element, a finite field vector, a finite field matrix, or a list of finite field matrices, and the other operand is an integer, an integer vector, an integer matrix, or a list of integer matrices. In this case the integers are interpreted as ' \*\ .one', where is the finite field (see "Operations for Finite Field Elements"). For all the above operations the result is new, i.e., not identical to any other list (see "Identical Lists"). This is the case even if the result is equal to one of the operands, e.g., if you add zero to a matrix. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{IsMat} 'IsMat( )' 'IsMat' return 'true' if , which can be an object of arbitrary type, is a matrix and 'false' otherwise. Will cause an error if is an unbound variable. | gap> IsMat( [ [ 1, 0 ], [ 0, 1 ] ] ); true # a matrix is a list of vectors gap> IsMat( [ [ 1, 2, 3, 4, 5 ] ] ); true gap> IsMat( [ [ Z(2)^0, 0*Z(2) ], [ 0*Z(2), Z(2)^0 ] ] ); true gap> IsMat( [ [ Z(2)^0, 0 ], [ 0, Z(2)^0 ] ] ); false # 'Z(2)\^0' and '0' do not lie in a common field gap> IsMat( [ 1, 0 ] ); false # a vector is not a matrix gap> IsMat( 1 ); false # neither is a scalar | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{IdentityMat} 'IdentityMat( )' \\ 'IdentityMat( , )' 'IdentityMat' returns the identity matrix with rows and columns over the field . If no field is given, 'IdentityMat' returns the identity matrix over the field of rationals. Each call to 'IdentityMat' returns a new matrix, so it is safe to modify the result. | gap> IdentityMat( 3 ); [ [ 1, 0, 0 ], [ 0, 1, 0 ], [ 0, 0, 1 ] ] gap> PrintArray( last ); [ [ 1, 0, 0 ], [ 0, 1, 0 ], [ 0, 0, 1 ] ] gap> PrintArray( IdentityMat( 3, GF(2) ) ); [ [ Z(2)^0, 0*Z(2), 0*Z(2) ], [ 0*Z(2), Z(2)^0, 0*Z(2) ], [ 0*Z(2), 0*Z(2), Z(2)^0 ] ] | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{NullMat} 'NullMat( , )' \\ 'NullMat( , , )' 'NullMat' returns the null matrix with rows and columns over the field . If no field is given, 'NullMat' returns the null matrix over the field of rationals. Each call to 'NullMat' returns a new matrix, so it is safe to modify the result. | gap> PrintArray( NullMat( 2, 3 ) ); [ [ 0, 0, 0 ], [ 0, 0, 0 ] ] gap> PrintArray( NullMat( 2, 2, GF(2) ) ); [ [ 0*Z(2), 0*Z(2) ], [ 0*Z(2), 0*Z(2) ] ] | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{TransposedMat} 'TransposedMat( )' 'TransposedMat' returns the transposed of the matrix . The transposed matrix is a new matrix , such that '[][]' is '[][]'. | gap> TransposedMat( [ [ 1, 2 ], [ 3, 4 ] ] ); [ [ 1, 3 ], [ 2, 4 ] ] gap> TransposedMat( [ [ 1..5 ] ] ); [ [ 1 ], [ 2 ], [ 3 ], [ 4 ], [ 5 ] ] | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{KroneckerProduct} 'KroneckerProduct( , )' 'KroneckerProduct' returns the Kronecker product of the two matrices and . If is a by matrix and is a by

matrix, the Kronecker product is a '\*' by '\*

' matrix, such that the entry in row '(-1)\*+' at position '(-1)\*

+' is '[][] \*\ [][]'. | gap> mat1 := [ [ 0, -1, 1 ], [ -2, 0, -2 ] ];; gap> mat2 := [ [ 1, 1 ], [ 0, 1 ] ];; gap> PrintArray( KroneckerProduct( mat1, mat2 ) ); [ [ 0, 0, -1, -1, 1, 1 ], [ 0, 0, 0, -1, 0, 1 ], [ -2, -2, 0, 0, -2, -2 ], [ 0, -2, 0, 0, 0, -2 ] ] | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{DimensionsMat} 'DimensionsMat( )' 'DimensionsMat' returns the dimensions of the matrix as a list of two integers. The first entry is the number of rows of , the second entry is the number of columns. | gap> DimensionsMat( [ [ 1, 2, 3 ], [ 4, 5, 6 ] ] ); [ 2, 3 ] gap> DimensionsMat( [ [ 1 .. 5 ] ] ); [ 1, 5 ] | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{TraceMat} 'TraceMat( )' 'TraceMat' returns the trace of the square matrix . The trace is the sum of all entries on the diagonal of . | gap> TraceMat( [ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ] ); 15 gap> TraceMat( IdentityMat( 4, GF(2) ) ); 0*Z(2) | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{DeterminantMat} 'DeterminantMat( )' 'DeterminantMat' returns the determinant of the square matrix . The determinant is defined by\\ $\sum_{p \in Symm(n)}{sign(p)\prod_{i=1}^{n}{mat[i][i^p]}}$. | gap> DeterminantMat( [ [ 1, 2 ], [ 3, 4 ] ] ); -2 gap> DeterminantMat( [ [ 0*Z(3), Z(3)^0 ], [ Z(3)^0, Z(3) ] ] ); Z(3) | Note that 'DeterminantMat' does not use the above definition to compute the result. Instead it performs a Gaussian elimination. For large rational matrices this may take very long, because the entries may become very large, even if the final result is a small integer. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{RankMat} 'RankMat( )' 'RankMat' returns the rank of the matrix . The rank is defined as the dimension of the vector space spanned by the rows of . It follows that a by matrix is invertible exactly if its rank is . | gap> RankMat( [ [ 4, 1, 2 ], [ 3, -1, 4 ], [ -1, -2, 2 ] ] ); 2 | Note that 'RankMat' performs a Gaussian elimination. For large rational matrices this may take very long, because the entries may become very large. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{OrderMat} 'OrderMat( )' 'OrderMat' returns the order of the invertible square matrix . The order is the smallest positive integer such that '\^' is the identity. | gap> OrderMat( [ [ 0*Z(2), 0*Z(2), Z(2)^0 ], > [ Z(2)^0, Z(2)^0, 0*Z(2) ], > [ Z(2)^0, 0*Z(2), 0*Z(2) ] ] ); 4 | 'OrderMat' first computes such that the first standard basis vector is mapped by '\^' onto itself. It does this by applying repeatedly to the first standard basis vector. Then it computes as '\^'. Then it computes such that the second standard basis vector is mapped by '\^' onto itself. This process is repeated until all basis vectors are mapped onto themselves. 'OrderMat' warns you that the order may be infinite, when it finds that the order must be larger than 1000. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{TriangulizeMat} 'TriangulizeMat( )' 'TriangulizeMat' brings the matrix into upper triangular form. Note that is changed and that nothing is returned. A matrix is in upper triangular form when the first nonzero entry in each row is one and lies further to the right than the first nonzero entry in the previous row. Furthermore, above the first nonzero entry in each row all entries are zero. Note that the matrix will have trailing zero rows if the rank of is not maximal. The rows of the resulting matrix span the same vectorspace than the rows of the original matrix . | gap> m := [ [ 0, -3, -1 ], [ -3, 0, -1 ], [ 2, -2, 0 ] ];; gap> TriangulizeMat( m ); m; [ [ 1, 0, 1/3 ], [ 0, 1, 1/3 ], [ 0, 0, 0 ] ] | Note that for large rational matrices 'TriangulizeMat' may take very long, because the entries may become very large during the Gaussian elimination, even if the final result contains only small integers. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{BaseMat} 'BaseMat( )' 'BaseMat' returns a standard base for the vector space spanned by the rows of the matrix . The standard base is in upper triangular form. That means that the first nonzero vector in each row is one and lies further to the right than the first nonzero entry in the previous row. Furthermore, above the first nonzero entry in each row all entries are zero. | gap> BaseMat( [ [ 0, -3, -1 ], [ -3, 0, -1 ], [ 2, -2, 0 ] ] ); [ [ 1, 0, 1/3 ], [ 0, 1, 1/3 ] ] | Note that for large rational matrices 'BaseMat' may take very long, because the entries may become very large during the Gaussian elimination, even if the final result contains only small integers. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{NullspaceMat} 'NullspaceMat( )' 'NullspaceMat' returns a base for the nullspace of the matrix . The nullspace is the set of vectors such that ' \*\ ' is the zero vector. The returned base is the standard base for the nullspace (see "BaseMat"). | gap> NullspaceMat( [ [ 2, -4, 1 ], [ 0, 0, -4 ], [ 1, -2, -1 ] ] ); [ [ 1, 3/4, -2 ] ] | Note that for large rational matrices 'NullspaceMat' may take very long, because the entries may become very large during the Gaussian elimination, even if the final result only contains small integers. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{SolutionMat} 'SolutionMat( , )' 'SolutionMat' returns one solution of the equation ' \*\ = ' or 'false' if no such solution exists. | gap> SolutionMat( [ [ 2, -4, 1 ], [ 0, 0, -4 ], [ 1, -2, -1 ] ], > [ 10, -20, -10 ] ); [ 5, 15/4, 0 ] gap> SolutionMat( [ [ 2, -4, 1 ], [ 0, 0, -4 ], [ 1, -2, -1 ] ], > [ 10, 20, -10 ] ); false | Note that for large rational matrices 'SolutionMat' may take very long, because the entries may become very large during the Gaussian elimination, even if the final result only contains small integers. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{DiagonalizeMat} 'DiagonalizeMat( )' 'DiagonalizeMat' transforms the integer matrix by multiplication with unimodular (i.e., determinant +1 or -1) integer matrices from the left and from the right into diagonal form (i.e., only diagonal entries are nonzero). Note that 'DiagonalizeMat' changes and returns nothing. If there are several diagonal matrices to which is equivalent, it is not specified which one is computed, except that all zero entries on the diagonal are collected at the lower right end (see "ElementaryDivisorsMat"). | gap> m := [ [ 0, -1, 1 ], [ -2, 0, -2 ], [ 2, -2, 4 ] ];; gap> DiagonalizeMat( m ); m; [ [ 1, 0, 0 ], [ 0, 2, 0 ], [ 0, 0, 0 ] ] | Note that for large integer matrices 'DiagonalizeMat' may take very long, because the entries may become very large during the computation, even if the final result only contains small integers. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{ElementaryDivisorsMat} 'ElementaryDivisorsMat( )' 'ElementaryDivisors' returns a list of the elementary divisors, i.e., the unique with '[]' divides '[+1]' and is equivalent to a diagonal matrix with the elements '[]' on the diagonal (see "DiagonalizeMat"). | gap> m := [ [ 0, -1, 1 ], [ -2, 0, -2 ], [ 2, -2, 4 ] ];; gap> ElementaryDivisorsMat( m ); [ 1, 2, 0 ] | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{PrintArray} 'PrintArray( )' 'PrintArray' displays the matrix in a pretty way. | gap> m := [[1,2,3,4],[5,6,7,8],[9,10,11,12]]; [ [ 1, 2, 3, 4 ], [ 5, 6, 7, 8 ], [ 9, 10, 11, 12 ] ] gap> PrintArray( m ); [ [ 1, 2, 3, 4 ], [ 5, 6, 7, 8 ], [ 9, 10, 11, 12 ] ]|