LinearAlgebra[Modular] - Maple Programming Help

Home : Support : Online Help : Mathematics : Linear Algebra : LinearAlgebra Package : Modular Subpackage : LinearAlgebra/Modular/MatBasis

LinearAlgebra[Modular]

 MatBasis
 compute Basis and Nullspace of vectors stored in the rows of a mod m Matrix

 Calling Sequence MatBasis(m, A, nrow, nullflag)

Parameters

 m - modulus A - mod m Matrix nrow - number of rows containing Vectors on input nullflag - boolean; indicates whether nullspace

Description

 • The MatBasis function computes a basis of the set of vectors in the first nrow rows of A. Optionally, a basis for the nullspace can also be computed. On successful completion, the number of rows in A containing vectors (labeled r) is returned (the dimension of the basis).
 • Computation of the basis does not require that m be a prime, but computation of the nullspace does. In some cases, it is possible to compute the nullspace with m composite. If this is not possible, the function returns an error indicating that the algorithm failed because m is composite.
 • To request a nullspace, set nullflag=true. If the nullspace is requested, the input Matrix must have at least as many rows as columns, and the basis of the nullspace is specified in the trailing $n-r+1..n$ rows of the Matrix, where $n$ is the number of columns, and $r$ is the return value (the dimension of the basis for the input vectors).
 • This command is part of the LinearAlgebra[Modular] package, so it can be used in the form MatBasis(..) only after executing the command with(LinearAlgebra[Modular]).  However, it can always be used in the form LinearAlgebra[Modular][MatBasis](..).

Examples

An example of a three dimensional basis and a two dimensional nullspace.

 > $\mathrm{with}\left(\mathrm{LinearAlgebra}[\mathrm{Modular}]\right):$
 > $p≔2741$
 ${p}{:=}{2741}$ (1)
 > $A≔\mathrm{Mod}\left(p,\mathrm{Matrix}\left(5,5,\left(i,j\right)→\mathrm{rand}\left(\right)\right),\mathrm{integer}[]\right):$
 > $\mathrm{Fill}\left(p,A,4..5\right):$
 > $A$
 $\left[\begin{array}{rrrrr}{2543}& {1568}& {127}& {356}& {581}\\ {430}& {1549}& {2376}& {1511}& {1839}\\ {164}& {1946}& {211}& {49}& {2418}\\ {0}& {0}& {0}& {0}& {0}\\ {0}& {0}& {0}& {0}& {0}\end{array}\right]$ (2)
 > $r≔\mathrm{MatBasis}\left(p,A,3,\mathrm{true}\right):$
 > $A,r$
 $\left[\begin{array}{rrrrr}{1}& {0}& {0}& {1972}& {1878}\\ {0}& {1}& {0}& {1578}& {1735}\\ {0}& {0}& {1}& {1724}& {2166}\\ {769}& {1163}& {1017}& {1}& {0}\\ {863}& {1006}& {575}& {0}& {1}\end{array}\right]{,}{3}$ (3)

In the previous example, the first $r$ rows are the basis of the input vectors, and the remaining rows are the basis of the nullspace. Check that these are orthogonal.

 > $\mathrm{Multiply}\left(p,A,1..r,A,r+1..5,'\mathrm{transpose}'\right)$
 $\left[\begin{array}{rr}{0}& {0}\\ {0}& {0}\\ {0}& {0}\end{array}\right]$ (4)

Construct an example with a known 2-D nullspace.

 > $A≔\mathrm{Mod}\left(p,\mathrm{Matrix}\left(5,5,\left(i,j\right)→\mathrm{rand}\left(\right)\right),\mathrm{float}[8]\right):$
 > $\mathbf{for}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}i\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathbf{to}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}5\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathbf{do}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{A}_{i,4}≔\mathrm{modp}\left(\mathrm{trunc}\left(p-{A}_{i,1}\right),p\right);\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{A}_{i,5}≔\mathrm{modp}\left(2\mathrm{trunc}\left(p-{A}_{i,3}\right),p\right)\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathbf{end do}:$$A$
 $\left[\begin{array}{ccccc}{2635.}& {353.}& {2657.}& {106.}& {168.}\\ {2587.}& {1857.}& {827.}& {154.}& {1087.}\\ {1720.}& {1181.}& {493.}& {1021.}& {1755.}\\ {2209.}& {884.}& {1207.}& {532.}& {327.}\\ {26.}& {2325.}& {518.}& {2715.}& {1705.}\end{array}\right]$ (5)

Obtain the basis and nullspace.

 > $r≔\mathrm{MatBasis}\left(p,A,5,\mathrm{true}\right):$
 > $A,r$
 $\left[\begin{array}{ccccc}{1.}& {0.}& {0.}& {2740.}& {0.}\\ {0.}& {1.}& {0.}& {0.}& {0.}\\ {0.}& {0.}& {1.}& {0.}& {2739.}\\ {1.}& {0.}& {0.}& {1.}& {0.}\\ {0.}& {0.}& {2.}& {0.}& {1.}\end{array}\right]{,}{3}$ (6)

Check orthogonality.

 > $\mathrm{Multiply}\left(p,A,1..r,A,r+1..5,'\mathrm{transpose}'\right)$
 $\left[\begin{array}{cc}{0.}& {0.}\\ {0.}& {0.}\\ {0.}& {0.}\end{array}\right]$ (7)