home *** CD-ROM | disk | FTP | other *** search
/ Math Solutions 1995 October / Math_Solutions_CD-ROM_Walnut_Creek_October_1995.iso / pc / mac / discrete / doc / matrix.tex < prev    next >
Encoding:
Text File  |  1993-05-05  |  19.7 KB  |  512 lines
  1. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  2. %%
  3. %A  matrix.tex                  GAP documentation            Martin Schoenert
  4. %%
  5. %A  @(#)$Id: matrix.tex,v 3.4 1993/02/19 10:48:42 gap Exp $
  6. %%
  7. %Y  Copyright 1990-1992,  Lehrstuhl D fuer Mathematik,  RWTH Aachen,  Germany
  8. %%
  9. %%  This file describes the matrix data type, its operations  and  functions.
  10. %%
  11. %H  $Log: matrix.tex,v $
  12. %H  Revision 3.4  1993/02/19  10:48:42  gap
  13. %H  adjustments in line length and spelling
  14. %H
  15. %H  Revision 3.3  1993/02/11  17:14:10  martin
  16. %H  vectors may now contain records
  17. %H
  18. %H  Revision 3.2  1993/02/05  09:05:59  felsch
  19. %H  examples fixed
  20. %H
  21. %H  Revision 3.1  1992/03/20  16:34:52  martin
  22. %H  initial revision under RCS
  23. %H
  24. %%
  25. \Chapter{Matrices}%
  26. \index{matrix}\index{type!matrices}
  27.  
  28. Matrices are an  important tool in algebra.  A matrix nicely represents a
  29. homomorphism  between two vector spaces with respect to a choice of bases
  30. for  the  vector  spaces.   Also  matrices  represent systems  of  linear
  31. equations.
  32.  
  33. In {\GAP}  matrices are represented by list of vectors  (see  "Vectors").
  34. The vectors must all have the same length, and their elements must lie in
  35. a  common  field.   The  field  may  be  the  field  of   rationals  (see
  36. "Rationals"), a cyclotomic field (see "Cyclotomics"), a finite field (see
  37. "Finite Fields"),  or a library and/or user  defined field (or ring) such
  38. as a polynomial ring (see "Polynomials").
  39.  
  40. The first  section in this chapter describes the operations applicable to
  41. matrices (see "Operations for Matrices").   The next  sections  describes
  42. the function that tests whether an object is a matrix (see "IsMat").  The
  43. next  sections describe the functions that create  certain  matrices (see
  44. "IdentityMat", "NullMat", "TransposedMat",  and "KroneckerProduct").  The
  45. next  sections  describe functions that  compute  certain  characteristic
  46. values of matrices  (see  "DimensionsMat", "TraceMat",  "DeterminantMat",
  47. "RankMat", and  "OrderMat").   The  next  sections describe the functions
  48. that are related to the interpretation of a matrix  as a system of linear
  49. equations   (see   "TriangulizeMat",   "BaseMat",   "NullspaceMat",   and
  50. "SolutionMat").   The last  two  sections  describe  the  functions  that
  51. diagonalize    an    integer    matrix    (see    "DiagonalizeMat"    and
  52. "ElementaryDivisorsMat").
  53.  
  54. Because  matrices are  just a special  case of lists, all operations  and
  55. functions  for  lists  are  applicable  to  matrices  also  (see  chapter
  56. "Lists").   This especially includes  accessing elements of a matrix (see
  57. "List Elements"), changing elements of  a matrix (see "List Assignment"),
  58. and comparing matrices (see "Comparisons of Lists").
  59.  
  60. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  61. \Section{Operations for Matrices}
  62.  
  63. '<mat> + <scalar>' \\
  64. '<scalar> + <mat>'
  65.  
  66. This  forms evaluates  to  the  sum of  the matrix  <mat> and the  scalar
  67. <scalar>.  The elements of <mat> and <scalar> must lie in a common field.
  68. The sum is a new matrix where each entry is the sum of the  corresponding
  69. entry of <mat> and <scalar>.
  70.  
  71. '<mat1> + <mat2>'
  72.  
  73. This  form evaluates to the  sum  of the two matrices <mat1> and  <mat2>,
  74. which  must have  the  same dimensions and whose  elements must lie in  a
  75. common field.  The sum is a new matrix where each entry is the sum of the
  76. corresponding entries of <mat1> and <mat2>.
  77.  
  78. '<mat> - <scalar>' \\
  79. '<scalar> - <mat>' \\
  80. '<mat1> - <mat2>'
  81.  
  82. The definition  for the '-' operator are similar to the above definitions
  83. for the '+' operator, except that '-' subtracts of course.
  84.  
  85. '<mat> \*\ <scalar>' \\
  86. '<scalar> \*\ <mat>'
  87.  
  88. This forms evaluate  to the product of the matrix  <mat> and  the  scalar
  89. <scalar>.  The elements of <mat> and <scalar> must lie in a common field.
  90. The product  is  a  new matrix  where each entry  is the  product of  the
  91. corresponding entries of <mat> and <scalar>.
  92.  
  93. '<vec> \*\ <mat>'
  94.  
  95. This form evaluates to  the product  of  the vector <vec> and  the matrix
  96. <mat>.   The length of <vec>  and  the  number  of rows of <mat> must  be
  97. equal.  The  elements of <vec> and <mat> must lie  in a common field.  If
  98. <vec> is a vector of length <n> and <mat> is  a matrix with <n>  rows and
  99. <m> columns, the product is a new  vector of length <m>.   The element at
  100. position  <i> is  the sum  of  '<vec>[<l>] \*\  <mat>[<l>][<i>]' with <l>
  101. running from 1 to <n>.
  102.  
  103. '<mat> \*\ <vec>'
  104.  
  105. This form evaluates to the product of  the  matrix  <mat> and the  vector
  106. <vec>.  The number of columns  of <mat> and  the length  of <vec> must be
  107. equal.  The elements of <mat>  and <vec> must lie in a common  field.  If
  108. <mat> is a  matrix with <m> rows and <n> columns and <vec> is a vector of
  109. length <n>, the  product  is a new vector of length <m>.  The element  at
  110. position  <i>  is the sum  of  '<mat>[<i>][<l>]  \*\ <vec>[<l>]' with <l>
  111. running from 1 to <n>.
  112.  
  113. '<mat1> \*\ <mat2>'
  114.  
  115. This form evaluates to the product of the two matrices <mat1> and <mat2>.
  116. The number of columns of <mat1> and the number of rows of  <mat2> must be
  117. equal.  The elements of <mat1> and <mat2> must lie in a common field.  If
  118. <mat1> is a matrix with <m>  rows and <n> columns and  <mat2> is a matrix
  119. with  <n> rows and <o> columns, the result is a new  matrix with <m> rows
  120. and  <o> columns.  The element in row <i> at position <k> of the  product
  121. is the sum of '<mat1>[<i>][<l>] \*\  <mat2>[<l>][<k>]'  with  <l> running
  122. from 1 to <n>.
  123.  
  124. '<mat1> / <mat2>' \\
  125. '<scalar> / <mat>' \\
  126. '<mat> / <scalar>' \\
  127. '<vec> / <mat>'
  128.  
  129. In general  '<left>  / <right>'  is defined  as '<left> \*\ <right>\^-1'.
  130. Thus in the above forms the right operand must always be invertable.
  131.  
  132. '<mat> \^\ <int>'
  133.  
  134. This form evaluates  to  the <int>-th  power of the matrix  <mat>.  <mat>
  135. must be a square matrix, <int> must be an integer.  If <int> is negative,
  136. <mat> must be invertible.   If  <int>  is 0,  the result is the  identity
  137. matrix, even if <mat> is not invertible.
  138.  
  139. '<mat1> \^\ <mat2>'
  140.  
  141. This form evaluates to the conjugation of the matrix <mat1> by the matrix
  142. <mat2>,  i.e., to '<mat2>\^-1  \*\  <mat1>  \*\  <mat2>'.  <mat2> must be
  143. invertible and <mat1> must be such that these product can be computed.
  144.  
  145. '<vec> \^\ <mat>'
  146.  
  147. This  is  in  every  respect  equivalent  to  '<vec>  \*\  <mat>'.   This
  148. operations reflects the fact that matrices operate on the vector space by
  149. multiplication from the right.
  150.  
  151. '<scalar> + <matlist>' \\
  152. '<matlist> + <scalar>' \\
  153. '<scalar> - <matlist>' \\
  154. '<matlist> - <scalar>' \\
  155. '<scalar> \*\ <matlist>' \\
  156. '<matlist> \*\ <scalar>' \\
  157. '<matlist> / <scalar>'
  158.  
  159. A scalar <scalar>  may also  be added,  subtracted,  multiplied with,  or
  160. divide into a whole list of matrices <matlist>.  The result is a new list
  161. of matrices where each  matrix is the result  of performing the operation
  162. with the corresponding matrix in <matlist>.
  163.  
  164. '<mat> \*\ <matlist>' \\
  165. '<matlist> \*\ <mat>'
  166.  
  167. A  matrix  <mat>  may  also be multiplied  with a whole list  of matrices
  168. <matlist>.  The  result  is a new list of matrices, where each matrix  is
  169. the product of <mat> and the corresponding matrix in <matlist>.
  170.  
  171. '<matlist> / <mat>'
  172.  
  173. This form evaluates to  '<matlist> \*\ <mat>\^-1'.  <mat>  must of course
  174. be invertable.
  175.  
  176. '<vec> \*\ <matlist>'
  177.  
  178. This form evaluates to  the product  of the vector <vec> and the  list of
  179. matrices  <mat>.  The length  <l> of  <vec> and <matlist> must be  equal.
  180. All matrices in <matlist> must have the same dimensions.  The elements of
  181. <vec> and the elements of the matrices in <matlist> must lie in a  common
  182. field.   The product  is the sum of '<vec>[<i>] \*\  <matlist>[<i>]' with
  183. <i> running from 1 to <l>.
  184.  
  185. 'Comm( <mat1>, <mat2> )'
  186.  
  187. 'Comm' returns the  commutator of  the matrices <mat1> and  <mat2>, i.e.,
  188. '<mat1>\^-1  \*\ <mat2>\^-1  \*\ <mat1>  \*\  <mat2>'.  <mat1> and <mat2>
  189. must be invertable and such that these product can be computed.
  190.  
  191. There is  one exception to  the rule that  the operands or their elements
  192. must  lie in common field.  It is allowed  that  one operand is  a finite
  193. field element, a finite field vector, a finite field matrix, or a list of
  194. finite  field  matrices, and the other operand  is an integer, an integer
  195. vector, an integer matrix,  or  a list of integer matrices.  In this case
  196. the integers are interpreted  as  '<int> \*\ <GF>.one', where <GF> is the
  197. finite field (see "Operations for Finite Field Elements").
  198.  
  199. For  all  the above operations the result  is new, i.e., not identical to
  200. any other list  (see  "Identical Lists").  This is the  case  even if the
  201. result is equal  to  one of  the  operands, e.g., if  you add zero  to  a
  202. matrix.
  203.  
  204. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  205. \Section{IsMat}
  206.  
  207. 'IsMat( <obj> )'
  208.  
  209. 'IsMat' return 'true' if <obj>, which can be an object of arbitrary type,
  210. is  a matrix and 'false'  otherwise.  Will cause an error  if <obj> is an
  211. unbound variable.
  212.  
  213. |    gap> IsMat( [ [ 1, 0 ], [ 0, 1 ] ] );
  214.     true    # a matrix is a list of vectors
  215.     gap> IsMat( [ [ 1, 2, 3, 4, 5 ] ] );
  216.     true
  217.     gap> IsMat( [ [ Z(2)^0, 0*Z(2) ], [ 0*Z(2), Z(2)^0 ] ] );
  218.     true
  219.     gap> IsMat( [ [ Z(2)^0, 0 ], [ 0, Z(2)^0 ] ] );
  220.     false    # 'Z(2)\^0' and '0' do not lie in a common field
  221.     gap> IsMat( [ 1, 0 ] );
  222.     false    # a vector is not a matrix
  223.     gap> IsMat( 1 );
  224.     false    # neither is a scalar |
  225.  
  226. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  227. \Section{IdentityMat}
  228.  
  229. 'IdentityMat( <n> )' \\
  230. 'IdentityMat( <n>, <F> )'
  231.  
  232. 'IdentityMat' returns the identity matrix  with <n> rows  and <n> columns
  233. over  the  field  <F>.  If  no field is given, 'IdentityMat'  returns the
  234. identity matrix over the field of rationals.  Each call to 'IdentityMat'
  235. returns a new matrix, so it is safe to modify the result.
  236.  
  237. |    gap> IdentityMat( 3 );
  238.     [ [ 1, 0, 0 ], [ 0, 1, 0 ], [ 0, 0, 1 ] ]
  239.     gap> PrintArray( last );
  240.     [ [  1,  0,  0 ],
  241.       [  0,  1,  0 ],
  242.       [  0,  0,  1 ] ]
  243.     gap> PrintArray( IdentityMat( 3, GF(2) ) );
  244.     [ [  Z(2)^0,  0*Z(2),  0*Z(2) ],
  245.       [  0*Z(2),  Z(2)^0,  0*Z(2) ],
  246.       [  0*Z(2),  0*Z(2),  Z(2)^0 ] ] |
  247.  
  248. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  249. \Section{NullMat}
  250.  
  251. 'NullMat( <m>, <n> )' \\
  252. 'NullMat( <m>, <n>, <F> )'
  253.  
  254. 'NullMat' returns the null matrix with <m> rows and <n> columns over  the
  255. field <F>.  If no field is given,  'NullMat' returns the null matrix over
  256. the field of rationals.  Each call to 'NullMat' returns  a new matrix, so
  257. it is safe to modify the result.
  258.  
  259. |    gap> PrintArray( NullMat( 2, 3 ) );
  260.     [ [  0,  0,  0 ],
  261.       [  0,  0,  0 ] ]
  262.     gap> PrintArray( NullMat( 2, 2, GF(2) ) );
  263.     [ [  0*Z(2),  0*Z(2) ],
  264.       [  0*Z(2),  0*Z(2) ] ] |
  265.  
  266. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  267. \Section{TransposedMat}
  268.  
  269. 'TransposedMat( <mat> )'
  270.  
  271. 'TransposedMat'  returns  the  transposed  of   the  matrix  <mat>.   The
  272. transposed matrix is a new  matrix  <trn>, such that '<trn>[<i>][<k>]' is
  273. '<mat>[<k>][<i>]'.
  274.  
  275. |    gap> TransposedMat( [ [ 1, 2 ], [ 3, 4 ] ] );
  276.     [ [ 1, 3 ], [ 2, 4 ] ]
  277.     gap> TransposedMat( [ [ 1..5 ] ] );
  278.     [ [ 1 ], [ 2 ], [ 3 ], [ 4 ], [ 5 ] ] |
  279.  
  280. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  281. \Section{KroneckerProduct}
  282.  
  283. 'KroneckerProduct( <mat1>, <mat2> )'
  284.  
  285. 'KroneckerProduct'  returns  the  Kronecker product of  the  two matrices
  286. <mat1>  and <mat2>.  If <mat1> is a <m> by <n> matrix and <mat2> is a <o>
  287. by  <p> matrix,  the  Kronecker product  is a  '<m>\*<o>'  by  '<n>\*<p>'
  288. matrix,  such  that  the  entry  in  row  '<i1>\*<m>+<i2>'  at   position
  289. '<k1>\*<n>+<k2>' is '<mat1>[<i1>][<k1>] \*\ <mat2>[<i2>][<k2>]'.
  290.  
  291. |    gap> mat1 := [ [ 0, -1, 1 ], [ -2, 0, -2 ] ];;
  292.     gap> mat2 := [ [ 1, 1 ], [ 0, 1 ] ];;
  293.     gap> PrintArray( KroneckerProduct( mat1, mat2 ) );
  294.     [ [   0,   0,  -1,  -1,   1,   1 ],
  295.       [   0,   0,   0,  -1,   0,   1 ],
  296.       [  -2,  -2,   0,   0,  -2,  -2 ],
  297.       [   0,  -2,   0,   0,   0,  -2 ] ] |
  298.  
  299. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  300. \Section{DimensionsMat}
  301.  
  302. 'DimensionsMat( <mat> )'
  303.  
  304. 'DimensionsMat' returns the dimensions of the matrix <mat>  as  a list of
  305. two integers.  The first entry is the number of rows of <mat>, the second
  306. entry is the number of columns.
  307.  
  308. |    gap> DimensionsMat( [ [ 1, 2, 3 ], [ 4, 5, 6 ] ] );
  309.     [ 2, 3 ]
  310.     gap> DimensionsMat( [ [ 1 .. 5 ] ] );
  311.     [ 1, 5 ] |
  312.  
  313. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  314. \Section{TraceMat}
  315.  
  316. 'TraceMat( <mat> )'
  317.  
  318. 'TraceMat' returns  the trace  of the square matrix <mat>.   The trace is
  319. the sum of all entries on the diagonal of <mat>.
  320.  
  321. |    gap> TraceMat( [ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ] );
  322.     15
  323.     gap> TraceMat( IdentityMat( 4, GF(2) ) );
  324.     0*Z(2) |
  325.  
  326. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  327. \Section{DeterminantMat}
  328.  
  329. 'DeterminantMat( <mat> )'
  330.  
  331. 'DeterminantMat' returns the determinant of the square matrix <mat>.  The
  332. determinant is defined by\\
  333. $\sum_{p \in Symm(n)}{sign(p)\prod_{i=1}^{n}{mat[i][i^p]}}$.
  334.  
  335. |    gap> DeterminantMat( [ [ 1, 2 ], [ 3, 4 ] ] );
  336.     -2
  337.     gap> DeterminantMat( [ [ 0*Z(3), Z(3)^0 ], [ Z(3)^0, Z(3) ] ] );
  338.     Z(3) |
  339.  
  340. Note that 'DeterminantMat' does not use  the above  definition to compute
  341. the  result.   Instead  it  performs a Gaussian  elimination.   For large
  342. rational matrices this may take very long, because the entries may become
  343. very large, even if the final result is a small integer.
  344.  
  345. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  346. \Section{RankMat}
  347.  
  348. 'RankMat( <mat> )'
  349.  
  350. 'RankMat'  returns the  rank of the matrix <mat>.  The rank is defined as
  351. the  dimension  of the vector  space spanned by the rows  of  <mat>.   It
  352. follows  that  a <n> by  <n>  matrix is invertible exactly if its rank is
  353. <n>.
  354.  
  355. |    gap> RankMat( [ [ 4, 1, 2 ], [ 3, -1, 4 ], [ -1, -2, 2 ] ] );
  356.     2 |
  357.  
  358. Note that 'RankMat' performs a  Gaussian elimination.  For large rational
  359. matrices  this  may take  very long, because the  entries may become very
  360. large.
  361.  
  362. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  363. \Section{OrderMat}
  364.  
  365. 'OrderMat( <mat> )'
  366.  
  367. 'OrderMat' returns  the order of the invertible square matrix <mat>.  The
  368. order <ord> is the smallest positive integer such  that '<mat>\^<ord>' is
  369. the identity.
  370.  
  371. |    gap> OrderMat( [ [ 0*Z(2), 0*Z(2), Z(2)^0 ],
  372.     >                 [ Z(2)^0, Z(2)^0, 0*Z(2) ],
  373.     >                 [ Z(2)^0, 0*Z(2), 0*Z(2) ] ] );
  374.     4 |
  375.  
  376. 'OrderMat'  first  computes <ord1>  such that  the first  standard  basis
  377. vector  is  mapped  by  '<mat>\^<ord1>' onto  itself.   It  does this  by
  378. applying <mat> repeatedly to the  first standard basis  vector.   Then it
  379. computes <mat1> as '<mat1>\^<ord1>'.   Then it  computes <ord2> such that
  380. the second  standard  basis vector is  mapped  by  '<mat1>\^<ord2>'  onto
  381. itself.  This process is repeated until all basis vectors are mapped onto
  382. themselves.  'OrderMat' warns you that the order may be infinite, when it
  383. finds that the order must be larger than 1000.
  384.  
  385. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  386. \Section{TriangulizeMat}
  387.  
  388. 'TriangulizeMat( <mat> )'
  389.  
  390. 'TriangulizeMat'  brings the matrix  <mat> into  upper  triangular  form.
  391. Note that <mat> is changed and that nothing is returned.   A matrix is in
  392. upper triangular form when the first nonzero entry in each row is one and
  393. lies  further to the right  than the first nonzero entry  in the previous
  394. row.  Furthermore, above  the first nonzero entry in each row all entries
  395. are zero.  Note that the matrix will have trailing zero  rows if the rank
  396. of <mat> is not maximal.  The rows of the resulting matrix span the  same
  397. vectorspace than the rows of the original matrix <mat>.
  398.  
  399. |    gap> m := [ [ 0, -3, -1 ], [ -3, 0, -1 ], [ 2, -2, 0 ] ];;
  400.     gap> TriangulizeMat( m ); m;
  401.     [ [ 1, 0, 1/3 ], [ 0, 1, 1/3 ], [ 0, 0, 0 ] ] |
  402.  
  403. Note  that for  large rational  matrices  'TriangulizeMat' may take  very
  404. long,  because the  entries  may become  very large  during the  Gaussian
  405. elimination, even if the final result contains only small integers.
  406.  
  407. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  408. \Section{BaseMat}
  409.  
  410. 'BaseMat( <mat> )'
  411.  
  412. 'BaseMat'  returns a  standard  base for the vector space  spanned by the
  413. rows of the matrix <mat>.  The standard base is in upper triangular form.
  414. That means that  the  first nonzero vector in each  row  is  one and lies
  415. further to the right than  the first nonzero  entry in the previous  row.
  416. Furthermore, above  the  first  nonzero entry in each row all entries are
  417. zero.
  418.  
  419. |    gap> BaseMat( [ [ 0, -3, -1 ], [ -3, 0, -1 ], [ 2, -2, 0 ] ] );
  420.     [ [ 1, 0, 1/3 ], [ 0, 1, 1/3 ] ] |
  421.  
  422. Note that  for  large  rational  matrices 'BaseMat'  may take very  long,
  423. because  the  entries   may  become   very  large   during  the  Gaussian
  424. elimination, even if the final result contains only small integers.
  425.  
  426. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  427. \Section{NullspaceMat}
  428.  
  429. 'NullspaceMat( <mat> )'
  430.  
  431. 'NullspaceMat' returns a base for the nullspace of the matrix <mat>.  The
  432. nullspace is the set of vectors <vec> such that '<vec> \*\ <mat>'  is the
  433. zero vector.   The returned  base is the standard  base for the nullspace
  434. (see "BaseMat").
  435.  
  436. |    gap> NullspaceMat( [ [ 2, -4, 1 ], [ 0, 0, -4 ], [ 1, -2, -1 ] ] );
  437.     [ [ 1, 3/4, -2 ] ] |
  438.  
  439. Note that for large rational matrices 'NullspaceMat' may take very  long,
  440. because   the   entries   may  become  very  large  during  the  Gaussian
  441. elimination, even if the final result only contains small integers.
  442.  
  443. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  444. \Section{SolutionMat}
  445.  
  446. 'SolutionMat( <mat>, <vec> )'
  447.  
  448. 'SolutionMat'  returns  one solution  of the equation '<x>  \*\  <mat>  =
  449. <vec>' or 'false' if no such solution exists.
  450.  
  451. |    gap> SolutionMat( [ [ 2, -4, 1 ], [ 0, 0, -4 ], [ 1, -2, -1 ] ],
  452.     >                  [ 10, -20, -10 ] );
  453.     [ 5, 15/4, 0 ]
  454.     gap> SolutionMat( [ [ 2, -4, 1 ], [ 0, 0, -4 ], [ 1, -2, -1 ] ],
  455.     >                  [ 10, 20, -10 ] );
  456.     false |
  457.  
  458. Note  that for large rational  matrices 'SolutionMat' may take very long,
  459. because   the  entries  may   become  very  large   during  the  Gaussian
  460. elimination, even if the final result only contains small integers.
  461.  
  462. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  463. \Section{DiagonalizeMat}
  464.  
  465. 'DiagonalizeMat( <mat> )'
  466.  
  467. 'DiagonalizeMat'  transforms the  integer matrix <mat> by  multiplication
  468. with unimodular  (i.e., determinant +1  or -1) integer matrices  from the
  469. left  and from the right into diagonal form (i.e., only diagonal  entries
  470. are  nonzero).  Note  that  'DiagonalizeMat'  changes <mat>  and  returns
  471. nothing.  If  there  are  several  diagonal matrices  to  which  <mat> is
  472. equivalent,  it is not  specified  which one is computed, except that all
  473. zero entries  on  the diagonal are collected at the lower right  end (see
  474. "ElementaryDivisorsMat").
  475.  
  476. |    gap> m := [ [ 0, -1, 1 ], [ -2, 0, -2 ], [ 2, -2, 4 ] ];;
  477.     gap> DiagonalizeMat( m );  m;
  478.     [ [ 1, 0, 0 ], [ 0, 2, 0 ], [ 0, 0, 0 ] ] |
  479.  
  480. Note that for large integer matrices 'DiagonalizeMat' may take very long,
  481. because the entries may become very large during the computation, even if
  482. the final result only contains small integers.
  483.  
  484. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  485. \Section{ElementaryDivisorsMat}
  486.  
  487. 'ElementaryDivisorsMat( <mat> )'
  488.  
  489. 'ElementaryDivisors' returns a list of the elementary divisors, i.e., the
  490. unique <d> with '<d>[<i>]'  divides '<d>[<i>+1]'  and <mat> is equivalent
  491. to a diagonal matrix  with the elements  '<d>[<i>]' on the  diagonal (see
  492. "DiagonalizeMat").
  493.  
  494. |    gap> m := [ [ 0, -1, 1 ], [ -2, 0, -2 ], [ 2, -2, 4 ] ];;
  495.     gap> ElementaryDivisorsMat( m );
  496.     [ 1, 2, 0 ] |
  497.  
  498. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  499. %%
  500. %E  Emacs . . . . . . . . . . . . . . . . . . . . . local Emacs variables
  501. %%
  502. %%  Local Variables:
  503. %%  mode:               outline
  504. %%  outline-regexp:     "\\\\Chapter\\|\\\\Section"
  505. %%  fill-column:        73
  506. %%  eval:               (hide-body)
  507. %%  End:
  508. %%
  509.  
  510.  
  511.  
  512.