Overview of Pseudo-linear Algebra - Maple Programming Help

Home : Support : Online Help : Mathematics : Algebra : Skew Polynomials : OreTools : OreTools/OreAlgebra

Overview of Pseudo-linear Algebra

 This help page provides a brief overview of pseudo-linear algebra. For a detailed discussion on the topic, refer to the literature in the References section.

Basic Objects

 • Let k be a field and sigma : k -> k be an automorphism of k.
 • Definition 1. (Pseudo-derivations) A pseudo-derivation with respect to sigma is any map delta: k -> k satisfying:
 1 $\mathrm{\delta }\left(a+b\right)=\mathrm{\delta }\left(a\right)+\mathrm{\delta }\left(b\right)$ for any a and b in k
 2 $\mathrm{\delta }\left(\mathrm{ab}\right)=\mathrm{\sigma }\left(a\right)\mathrm{\delta }\left(b\right)+\mathrm{\delta }\left(a\right)b$ for any a and b in k
 Example: For any alpha in k, delta[alpha] is defined as alpha(sigma - 1). The map alpha[delta] given by delta[alpha]a = alpha(sigma(a) - a) is called an inner derivation.
 • Lemma 1. Let k be a field, sigma be an automorphism of k, and delta be a pseudo-derivation of k.
 3 If sigma <> 1, then there is an element alpha in k such that:

$\mathrm{\delta }=\mathrm{\alpha }\left(\mathrm{\sigma }-1\right)\mathrm{ = }{\mathrm{\delta }}_{\mathrm{\alpha }}$

 4 If delta <> 0, then there is an element beta in k such that:

$\mathrm{\sigma }=\mathrm{\beta }\mathrm{\delta }+1$

 • Definition 2. (Univariate skew-polynomials) The left skew polynomial ring given by sigma and delta is the ring (k[x], +, .) of polynomials in x over k with the usual polynomial addition, and the multiplication given by:

$xa=\mathrm{\sigma }\left(a\right)x+\mathrm{\delta }\left(a\right)$

 for any a in k.
 To distinguish it from the usual commutative polynomial ring k[x], the left skew polynomial ring is denoted by k[x; sigma, delta]. Its elements are called skew polynomials or Ore polynomials. It can be shown that k[x; sigma, delta] possesses the right and left Euclidean division algorithms.
 • Definition 3. (Pseudo-linear maps) Let V be a vector space over k. A map theta: V -> V is called k-pseudo-linear (with respect to sigma and delta) if:
 5 $\mathrm{\theta }\left(u+v\right)=\mathrm{\theta }\left(u\right)+\mathrm{\theta }\left(v\right)$ for any u and v in V
 6 $\mathrm{\theta }\left(au\right)=\mathrm{\sigma }\left(a\right)\mathrm{\theta }\left(u\right)+\mathrm{\delta }\left(a\right)u$ for any a in k and u and v in V
 • Lemma 2. Let K be a compatible field extension of k. Then, for any c in K, the map theta[c]: K -> K given by:

${\mathrm{\theta }}_{c}\left(a\right)=c\mathrm{\sigma }\left(a\right)+\mathrm{\delta }\left(a\right)$

 is K-pseudo-linear. Conversely, for any K-pseudo-linear map,

$\mathrm{theta}:K\to K,$

 there is an element c in K such that theta = theta[c].
 Note: To prove the converse, by the pseudo-linearity of theta,

$\mathrm{\theta }\left(a\right)=\mathrm{\theta }\left(\mathrm{a1}\right)\mathrm{ = }\mathrm{\sigma }\left(a\right)\mathrm{\theta }\left(1\right)+\mathrm{\delta }\left(a\right)$

 Hence, theta = theta[c], where c = theta(1).
 Note: To define a ring (k[x], +, .) and the pseudo-linear map theta, you must specify sigma, delta, and theta(1).

Basic Arithmetic

 • Let k[x; sigma, delta] be a skew-polynomial ring, and A and B be in the set k[x; sigma, delta] minus {0}. By applying the right Euclidean division algorithm, you obtain the relation:

$A=B\mathrm{Q1}+\mathrm{R1},\mathrm{Q1},\mathrm{R1}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}∈\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathrm{k\left[x; sigma, delta\right]},\mathrm{deg}\left(\mathrm{R1}\right)<\mathrm{deg}\left(B\right)$

 R1 and Q1 are called the right-remainder and the right-quotient of A by B, respectively.
 Similarly, by applying the left Euclidean division algorithm, you obtain the relation:

$A=B\mathrm{Q2}+\mathrm{R2},\mathrm{Q2},\mathrm{R2}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}∈\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathrm{k\left[x; sigma, delta\right]},\mathrm{deg}\left(\mathrm{R2}\right)<\mathrm{deg}\left(B\right)$

 R2 and Q2 are called the left-remainder and the left-quotient of A by B, respectively.
 • For a given A and B in k[x; sigma, delta], you can find the greatest common right divisor (GCRD) and the least common left multiple (LCLM) by using the extended right Euclidean algorithm.

 • Definition 4. Let k[x; sigma, delta] be a skew-polynomial ring. The adjoint of k[x; sigma, delta] is defined by the ring k[x; sigma*, delta*] where sigma* and delta* are defined as follows.
 1 If $\mathrm{\sigma }=1$, then$\mathrm{\sigma }\mathrm{* }=\mathrm{\sigma }$ $=1$ and$\mathrm{\delta }\mathrm{* }=-\mathrm{\delta }$.
 2 If $\mathrm{\sigma }\ne 1$, then $\mathrm{\delta }=\mathrm{\alpha }\left(\mathrm{\sigma }-1\right)$ for some$\mathrm{\alpha }\in k$. Set$\mathrm{\sigma }\mathrm{* }={\mathrm{\sigma }}^{\left\{-1\right\}}$ and$\mathrm{\delta }\mathrm{* }=\mathrm{\alpha }\left(\mathrm{\sigma }\mathrm{* }-1\right)$ $\mathrm{}=\mathrm{\alpha }\left({\mathrm{\sigma }}^{\left\{-1\right\}}-1\right)$.
 Let L=a[n] x^n + ... + a[1] x + a[0] be in k[x; sigma, delta]. The adjoint operator L* is then defined by:

$L*={x}^{n}{a}_{n}+\mathrm{...}+x{a}_{1}+{a}_{0},L*\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}∈\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathrm{k\left[x; sigma*, delta*\right]}$

 Note: The product x^i a[i] must be computed in the ring k[x; sigma*, delta*]. It is easy to show that (sigma*)* = sigma, (delta*)* = delta. You can also verify that that the adjoint is a linear bijective map and that (M o N){*} = N* o M*.
 • Lemma 4. Let theta be a pseudo-linear map with respect to sigma and delta. Then:

$\mathrm{\theta }=\mathrm{ = }c\mathrm{\sigma }{\mathrm{\theta }}_{c}+\mathrm{\delta }$

 Set

$\mathrm{\theta }\mathrm{* }=\mathrm{* }c\mathrm{\sigma }+\mathrm{\delta }\mathrm{* }$

 Then theta* is a pseudo-linear map with respect to sigma* and delta*.

References

 Abramov, S.A. Ore Rings and Linear Equations. Unpublished.
 Bronstein, M. and Petkovsek, M. "An introduction to pseudo-linear algebra." Theoretical Computer Science Vol. 157, (1996): 3-33.
 Ore, O. "Theory of non-commutative polynomials." Annals of Mathematics. Vol. 34, (1933): 480-508.