LinearAlgebra - Maple Help

Home : Support : Online Help : Mathematics : Linear Algebra : LinearAlgebra Package : Solvers : LinearAlgebra/PopovForm

LinearAlgebra

 PopovForm
 compute the Popov normal form of a Matrix

 Calling Sequence PopovForm(A, x, shifts, out, options, outopts)

Parameters

 A - Matrix of univariate polynomials in x x - variable name of the polynomial domain shifts - (optional) equation of the form shifts = obj where obj is a list of one or two lists out - (optional) equation of the form output = obj where obj is one of 'P', 'U', 'rank', 'P_pivots', 'U_pivots', or a list containing one or more of these names; select result objects to compute options - (optional); constructor options for the result object(s) outopts - (optional) equation(s) of the form outputoptions[o] = list where o is one of 'P' or 'U'; constructor options for the specified result object

Description

 • The PopovForm(A, x) function computes the column Popov normal form P (also called the polynomial echelon form) of an m x n rectangular Matrix of univariate polynomials in x over the field of rational numbers Q, or rational expressions over Q. You can request the form P, the unimodular multiplier U which gives P, the rank and various pivots in P and U via a specification of the output option.

Definition of Column Popov Form

 • There are a number of variations of column Popov forms, typically unique up to permutation of the columns. The definitions used for both the full and non-full column rank case are as follows.
 If $m=n$ and P is nonsingular, P has the following degree constraints.

$\mathrm{deg}\left({P}_{j,i}\right)<\mathrm{deg}\left({P}_{i,i}\right),\mathrm{for all j > i}$

$\mathrm{deg}\left({P}_{j,i}\right)\le \mathrm{deg}\left({P}_{i,i}\right),\mathrm{for all j < i}$

 If $n and P has full column rank, there is a trailing list of n pivot rows P_pivots such that P[P_pivots,*] is in Popov normal form.
 If $n\le m$ and P has column rank $r, P has the first $n-r$ columns 0 and there is a trailing list of r rows P_pivots such that P[P_pivots,*] is in Popov normal form. In this case, U is a minimal unimodular multiplier and as such there is a list U_pivots of rows such that U[U_pivots,*] is also in Popov normal form.
 The Popov normal form P is obtained by doing elementary column operations on A. This includes interchanging columns, multiplying through a column by a unit, and subtracting a polynomial multiple of one column from another. The method used is a fraction-free algorithm by Beckermann, Labahn, and Villard.  The returned Matrix objects have the property that $P=A\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}.\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}U$.
 • The output option (out) determines the content of the returned expression sequence.
 Depending on what is included in the output option, an expression sequence containing one or more of the factors P (the Popov normal form), U (the unimodular transformation Matrix), rank (the rank of the matrix), P_pivots, or U_pivots (the pivot rows of P and U, respectively) can be returned.
 If output is a list, the objects are returned in the same order as specified in the list.
 • The shifts option is an optional input which allows the user to shift the degree constraints on both the Popov form and the minimal multiplier (in the non-full column rank case).
 • The constructor options provide additional information (readonly, shape, storage, order, datatype, and attributes) to the Matrix constructor that builds the result(s). These options may also be provided in the form outputoptions[o]=[...], where [...] represents a Maple list.  If a constructor option is provided in both the calling sequence directly and in an outputoptions[o] option, the latter takes precedence (regardless of the order).

Examples

 > $\mathrm{with}\left(\mathrm{LinearAlgebra}\right):$
 > $A≔⟨⟨{z}^{3}-{z}^{2},{z}^{3}-2{z}^{2}+2z-2⟩|⟨{z}^{3}-2{z}^{2}-1,{z}^{3}-3{z}^{2}+3z-4⟩⟩$
 ${A}{:=}\left[\begin{array}{cc}{{z}}^{{3}}{-}{{z}}^{{2}}& {{z}}^{{3}}{-}{2}{}{{z}}^{{2}}{-}{1}\\ {{z}}^{{3}}{-}{2}{}{{z}}^{{2}}{+}{2}{}{z}{-}{2}& {{z}}^{{3}}{-}{3}{}{{z}}^{{2}}{+}{3}{}{z}{-}{4}\end{array}\right]$ (1)
 > $P≔\mathrm{PopovForm}\left(A,z,\mathrm{datatype}=\mathrm{algebraic}\right)$
 ${P}{:=}\left[\begin{array}{cc}{z}& {-}{1}\\ {1}& {-}{1}{+}{z}\end{array}\right]$ (2)
 > $P,U≔\mathrm{PopovForm}\left(A,z,\mathrm{output}=\left['P','U'\right]\right)$
 ${P}{,}{U}{:=}\left[\begin{array}{cc}{z}& {-}{1}\\ {1}& {-}{1}{+}{z}\end{array}\right]{,}\left[\begin{array}{cc}{-}\frac{{1}}{{2}}{}{{z}}^{{2}}{+}\frac{{3}}{{2}}{}{z}{-}\frac{{1}}{{2}}& \frac{{1}}{{2}}{}{{z}}^{{2}}{-}\frac{{1}}{{2}}{}{z}{-}\frac{{3}}{{2}}\\ \frac{{1}}{{2}}{}{{z}}^{{2}}{-}{z}& {-}\frac{{1}}{{2}}{}{{z}}^{{2}}{+}{1}\end{array}\right]$ (3)
 > $\mathrm{map}\left(\mathrm{expand},P-A\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}.\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}U\right)$
 $\left[\begin{array}{rr}{0}& {0}\\ {0}& {0}\end{array}\right]$ (4)
 > $\mathrm{Determinant}\left(U\right)$
 ${-}\frac{{1}}{{2}}$ (5)

A low rank matrix.

 > $A≔⟨⟨3z-6,-3z+3,2z+3,z⟩|⟨-3z,3z,-2,-1⟩|⟨6,-3,-2z-1,-z+1⟩⟩$
 ${A}{:=}\left[\begin{array}{ccc}{3}{}{z}{-}{6}& {-}{3}{}{z}& {6}\\ {-}{3}{}{z}{+}{3}& {3}{}{z}& {-}{3}\\ {2}{}{z}{+}{3}& {-}{2}& {-}{2}{}{z}{-}{1}\\ {z}& {-}{1}& {-}{z}{+}{1}\end{array}\right]$ (6)
 > $P,U,r≔\mathrm{PopovForm}\left(A,z,\mathrm{output}=\left['P','U','\mathrm{rank}'\right]\right)$
 ${P}{,}{U}{,}{r}{:=}\left[\begin{array}{ccc}{0}& {-}{z}& {-}{6}\\ {0}& {z}& {3}\\ {0}& {-}\frac{{2}}{{3}}& {1}{+}{2}{}{z}\\ {0}& {-}\frac{{1}}{{3}}& {-}{1}{+}{z}\end{array}\right]{,}\left[\begin{array}{ccc}{1}& {0}& {1}\\ {1}& \frac{{1}}{{3}}& {1}\\ {1}& {0}& {0}\end{array}\right]{,}{2}$ (7)
 > $P,U,r,\mathrm{II},K≔\mathrm{PopovForm}\left(A,z,\mathrm{output}=\left['P','U','\mathrm{rank}','\mathrm{P_pivots}','\mathrm{U_pivots}'\right]\right)$
 ${P}{,}{U}{,}{r}{,}{\mathrm{II}}{,}{K}{:=}\left[\begin{array}{ccc}{0}& {-}{z}& {-}{6}\\ {0}& {z}& {3}\\ {0}& {-}\frac{{2}}{{3}}& {1}{+}{2}{}{z}\\ {0}& {-}\frac{{1}}{{3}}& {-}{1}{+}{z}\end{array}\right]{,}\left[\begin{array}{ccc}{1}& {0}& {1}\\ {1}& \frac{{1}}{{3}}& {1}\\ {1}& {0}& {0}\end{array}\right]{,}{2}{,}\left[{2}{,}{4}\right]{,}\left[{3}\right]$ (8)

A [2,2,0,0]-shifted Popov form.

 > $P,U,r,\mathrm{II},K≔\mathrm{PopovForm}\left(A,z,\mathrm{shifts}=\left[\left[2,2,0,0\right]\right],\mathrm{output}=\left['P','U','\mathrm{rank}','\mathrm{P_pivots}','\mathrm{U_pivots}'\right]\right)$
 ${P}{,}{U}{,}{r}{,}{\mathrm{II}}{,}{K}{:=}\left[\begin{array}{ccc}{0}& {-}{{z}}^{{2}}{+}{z}{-}{2}& {2}{}{{z}}^{{2}}{+}{z}{+}{4}\\ {0}& {{z}}^{{2}}{-}{z}{+}{1}& {-}{2}{}{{z}}^{{2}}{-}{z}{-}{2}\\ {0}& {1}& {0}\\ {0}& {0}& {1}\end{array}\right]{,}\left[\begin{array}{ccc}{1}& \frac{{1}}{{3}}& {-}\frac{{2}}{{3}}\\ {1}& \frac{{1}}{{3}}{}{z}& {-}{1}{-}\frac{{2}}{{3}}{}{z}\\ {1}& {0}& {0}\end{array}\right]{,}{2}{,}\left[{3}{,}{4}\right]{,}\left[{3}\right]$ (9)

A Popov form with [0,-3,0,0]-shift for unimodular multiplier.

 > $A≔⟨⟨-{z}^{3}+4{z}^{2}+z+1,-{z}^{2}+7z+4⟩|⟨z-1,z+2⟩|⟨2{z}^{2}+2z-2,{z}^{2}+6z+6⟩|⟨-{z}^{2},-2z⟩⟩$
 ${A}{:=}\left[\begin{array}{cccc}{-}{{z}}^{{3}}{+}{4}{}{{z}}^{{2}}{+}{z}{+}{1}& {-}{1}{+}{z}& {2}{}{{z}}^{{2}}{+}{2}{}{z}{-}{2}& {-}{{z}}^{{2}}\\ {-}{{z}}^{{2}}{+}{7}{}{z}{+}{4}& {z}{+}{2}& {{z}}^{{2}}{+}{6}{}{z}{+}{6}& {-}{2}{}{z}\end{array}\right]$ (10)
 > $P,U,r,\mathrm{II},K≔\mathrm{PopovForm}\left(A,z,\mathrm{shifts}=\left[\left[0,0\right],\left[0,-3,0,0\right]\right],\mathrm{output}=\left['P','U','\mathrm{rank}','\mathrm{P_pivots}','\mathrm{U_pivots}'\right]\right)$
 ${P}{,}{U}{,}{r}{,}{\mathrm{II}}{,}{K}{:=}\left[\begin{array}{cccc}{0}& {0}& {z}& {-}{1}\\ {0}& {0}& {2}& {z}\end{array}\right]{,}\left[\begin{array}{cccc}{-}\frac{{2}}{{21}}{}{z}{+}\frac{{1}}{{7}}& {-}{{z}}^{{2}}{-}{2}{}{z}& \frac{{2}}{{7}}{+}\frac{{1}}{{7}}{}{z}& {-}\frac{{1}}{{21}}{}{z}{-}\frac{{3}}{{7}}\\ {1}& {0}& {0}& {0}\\ {-}\frac{{3}}{{7}}{+}\frac{{2}}{{21}}{}{z}& {{z}}^{{2}}{-}{z}& {-}\frac{{1}}{{7}}{}{z}{+}\frac{{1}}{{7}}& \frac{{2}}{{7}}{+}\frac{{1}}{{21}}{}{z}\\ \frac{{2}}{{21}}{}{{z}}^{{2}}{-}\frac{{1}}{{3}}{}{z}{-}\frac{{4}}{{21}}& {{z}}^{{3}}{-}{9}{}{z}{-}{7}& {-}\frac{{1}}{{7}}{}{{z}}^{{2}}{+}\frac{{9}}{{7}}& \frac{{1}}{{21}}{}{{z}}^{{2}}{+}\frac{{1}}{{3}}{}{z}{-}\frac{{23}}{{21}}\end{array}\right]{,}{2}{,}\left[{1}{,}{2}\right]{,}\left[{2}{,}{4}\right]$ (11)
 > $\mathrm{map}\left(\mathrm{expand},P-A\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}.\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}U\right)$
 $\left[\begin{array}{rrrr}{0}& {0}& {0}& {0}\\ {0}& {0}& {0}& {0}\end{array}\right]$ (12)
 > $\mathrm{Determinant}\left(U\right)$
 ${1}$ (13)

References

 Beckermann, B., and Labahn, G. "Fraction-free Computation of Matrix Rational Interpolants and Matrix GCDs." SIAM Journal on Matrix Analysis and Applications, Vol. 22 No. 1. (2000): 114-144.
 Beckermann, B.; Labahn, G.; and Villard, G. "Shifted Normal Forms of General Polynomial Matrices." University of Waterloo, Technical Report. Department of Computer Science, 2001.
 Beckermann, B.; Labahn, G.; and Villard, G. "Shifted Normal Forms of Polynomial Matrices."  ISSAC'99, pp. 189-196. 1999.