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 non-square 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 non-zero (that is, they are singular). For algorithms such as those used in LinearFunctionalSystems[PolynomialSolution] and LinearFunctionalSystems[UniversalDenominator], this matrix should be non-singular.

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 non-singular).

This technique is named EG-eliminations, because EG-eliminations 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 EG-eliminations (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 non-singular leading or trailing matrix that reveals the rank. If the name res is given then 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](..).

$\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}\mathrm{-1}& \mathrm{-1}& n+1& 0\\ \mathrm{-1}& \mathrm{-1}& 0& n+1\end{array}\right]\,table\left(\left[\right]\right)\,\left[\begin{array}{c}0\\ 0\end{array}\right]\,\varnothing \,\varnothing \right]$

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

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

$M≔\mathrm{Matrix}\left(4\,6\,\left\{\left(1\,4\right)=n-2\,\left(1\,5\right)=-1\,\left(2\,5\right)=n-2\,\left(3\,2\right)=-n-1\,\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& \mathrm{-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]$

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

$2$

$\mathrm{res}$

$\left[\left[\begin{array}{cccccc}\mathrm{-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]\,table\left(\left[1=\left\{\left[0\,\mathrm{-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}{c}1\\ 0\end{array}\right]\,\left\{3\,4\right\}\,\varnothing \right]$

Abramov, S. A. "EG-Eliminations." Journal of Difference Equations and Applications, (1999): 393-433.

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