LinearFunctionalSystems[MatrixTriangularization]  return the equivalent matrix recurrence system with nonsingular leading or trailing matrix
LinearFunctionalSystems[Rank]  reveal the rank of a recurrence system

Calling Sequence


MatrixTriangularization(mat, m, x, lt)
Rank(mat, m, x, lt, res)


Parameters


mat



explicit matrix of the system

m



number of matrix blocks

x



independent variable

lt



name specifying which matrix should be triangularized; one of 'lead' or 'trail'

res



(optional) name to return the result of invocation of MatrixTriangularization needed to reveal the rank





Description


•

The MatrixTriangularization function returns the equivalent matrix recurrence system with nonsingular leading or trailing matrix. The Rank function reveals the rank of a recurrence system by constructing the equivalent matrix recurrence system with nonsingular leading or trailing matrix.

•

The matrix recurrence system is represented by its explicit matrix (the matrix k by l*m, where k is the number of recurrences in the system, l is the number of the undetermined sequences in the system, and m is the number of blocks in the matrix (each block corresponds to the coefficient of the shift operator of some order in the system, so m corresponds to the order of the system in respect to the shift operator). So the leading and trailing matrices are of size k by l), as well as all other blocks in the explicit matrix. The determinants (or all minors of the maximal order for nonsquare blocks) of the leading and/or trailing matrix could vanish for all values of x, however, the leading and trailing matrices of the system are nonzero (that is, they are singular). For algorithms such as those used in LinearFunctionalSystems[PolynomialSolution] and LinearFunctionalSystems[UniversalDenominator], this matrix should be nonsingular.

•

The MatrixTriangularization function solves the problem by using the method by S.A. Abramov & M.Bronstein. It is based on the set of transformations of the given recurrent system to the equivalent one where possibly some additional constraints for the finite number of coefficients could appear (that is, to the system which has the same solutions as the given one does, but with the leading (or trailing) matrix being nonsingular).


This technique is named EGeliminations, because EGeliminations have similarities to the Euclid algorithm and the Gauss method (E = Euclidean, G = Gaussian). They either allow one to recognize the dependency of the recurrences, or else lead to a system of the desired form. It is possible that the transformation additionally results in a finite set of relations for the initial values of each of the solutions of the new system. The package implements an improved version of EGeliminations (EG') by S.A.Abramov and M.Bronstein.


The elementary steps of this transformation are Gaussian eliminations, and horizontal shifts of the rows of the explicit matrix and vertical shifts of its columns.

•

An output of MatrixTriangularization is a list of the following entries needed in order to interpret the result:


matrix  the transformed explicit matrix itself.


constraints  the additional constraints represented as a table. For each entry of the table (if any), the index specifies the fixed x and the value specifies the list of the rows of the explicit matrix corresponding to this x.


vshifts  the vertical shifts represented as a vector of size n. Each element of the vector specifies the number of times the corresponding column of the square block was vertically shifted.


rows  a set of indices of dependent rows (if any).


columns  a set of indices of columns with total zeroes in all blocks (if any).

•

The Rank function determines the rank of a recurrence system by computing the equivalent one with a nonsingular leading or trailing matrix that reveals the rank. If the name res is given then the the result of the corresponding invocation of MatrixTriangularization is assigned to this name.

•

These functions are part of the LinearFunctionalSystems package, and so they can be used in the form MatrixTriangularization(..) only after executing the command with(LinearFunctionalSystems). However, they can always be accessed through the long form of the command by using the form LinearFunctionalSystems[MatrixTriangularization](..) and LinearFunctionalSystems[Rank](..).



Examples


>

$\mathrm{with}\left(\mathrm{LinearFunctionalSystems}\right)\:$

>

$M:=\mathrm{Matrix}\left(2\,4\,\left[1\,1\,n\+1\,0\,1\,1\,0\,n\+1\right]\right)\:$

>

$\mathrm{MatrixTriangularization}\left(M\,2\,n\,\'\mathrm{trail}\'\right)$

$\left[\left[\begin{array}{cccc}{}{1}& {}{1}& {n}{\+}{1}& {0}\\ {}{1}& {}{1}& {0}& {n}{\+}{1}\end{array}\right]{\,}{\mathrm{table}}\left(\left[{}\right]\right){\,}\left[\begin{array}{r}{0}\\ {0}\end{array}\right]{\,}\left\{{}\right\}{\,}\left\{{}\right\}\right]$
 (1) 
>

$\mathrm{MatrixTriangularization}\left(M\,2\,n\,\'\mathrm{lead}\'\right)$

$\left[\left[\begin{array}{cccc}{}{1}& {}{1}& {n}{\+}{1}& {0}\\ {}{n}{}{2}& {n}{\+}{2}& {0}& {0}\end{array}\right]{\,}{\mathrm{table}}\left(\left[{}\right]\right){\,}\left[\begin{array}{r}{0}\\ {0}\end{array}\right]{\,}\left\{{}\right\}{\,}\left\{{}\right\}\right]$
 (2) 
>

$M:=\mathrm{Matrix}\left(4\,6\,\left\{\left(1\,4\right)\=n2\,\left(1\,5\right)\=1\,\left(2\,5\right)\=n2\,\left(3\,2\right)\=n1\,\left(3\,4\right)\=1\,\left(3\,6\right)\=3\,\left(4\,3\right)\=n\+1\right\}\right)$

${M}{:=}\left[\begin{array}{cccccc}{0}& {0}& {0}& {n}{}{2}& {}{1}& {0}\\ {0}& {0}& {0}& {0}& {n}{}{2}& {0}\\ {0}& {}{n}{}{1}& {0}& {1}& {0}& {3}\\ {0}& {0}& {n}{\+}{1}& {0}& {0}& {0}\end{array}\right]$
 (3) 
>

$\mathrm{LinearFunctionalSystems}\[\mathrm{Rank}\]\left(M\,3\,n\,\'\mathrm{lead}\'\,\'\mathrm{res}\'\right)$

$\left[\left[\begin{array}{cccccc}{}{1}& {n}{}{1}& {0}& {0}& {0}& {0}\\ {n}{}{1}& {0}& {0}& {0}& {0}& {0}\\ {0}& {0}& {0}& {0}& {0}& {0}\\ {0}& {0}& {0}& {0}& {0}& {0}\end{array}\right]{\,}{\mathrm{table}}\left(\left[{1}{\=}\left\{\left[{0}{\,}{}{2}{\,}{0}{\,}{1}{\,}{0}{\,}{3}\right]{\,}\left[{0}{\,}{1}{\,}{0}{\,}{3}{\,}{0}{\,}{0}\right]{\,}\left[{0}{\,}{12}{\,}{0}{\,}{0}{\,}{0}{\,}{0}\right]{\,}\left[{2}{\,}{0}{\,}{0}{\,}{0}{\,}{0}{\,}{0}\right]\right\}\right]\right){\,}\left[\begin{array}{r}{1}\\ {0}\end{array}\right]{\,}\left\{{3}{\,}{4}\right\}{\,}\left\{{}\right\}\right]$
 (5) 


References



Abramov, S. A. "EGEliminations." Journal of Difference Equations and Applications, (1999): 393433.


Abramov, S. A., and Bronstein, M. "On Solutions of Linear Functional Systems." In Proceedings of ISSAC '01, pp. 16. Edited by Bernard Mourrain. New York: ACM Press, 2001.


