Overview of Pseudo-linear Algebra - Maple Programming Help

Online Help

All Products    Maple    MapleSim

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

Basic Arithmetic

Adjoint Equations


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:


δa+b=δa+δb for any a and b in k


δab=σaδb+δab 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.


If sigma <> 1, then there is an element alpha in k such that:

δ=ασ1` = `δα


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



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:



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:


θu+v=θu+θv for any u and v in V


θau=σaθu+δau 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:



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



there is an element c in K such that theta = theta[c].


Note: To prove the converse, by the pseudo-linearity of theta,

θa=θa1` = `σaθ1+δa


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&equals;BQ1&plus;R1&comma;Q1&comma;R1&in;k[x; sigma, delta]&comma;degR1<degB


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&equals;BQ2&plus;R2&comma;Q2&comma;R2&in;k[x; sigma, delta]&comma;degR2<degB


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.

Adjoint Equations


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.


If σ=1, thenσ`* `=σ &equals;1 andδ`* `=δ.


If σ1, then δ=ασ1 for someαk. Setσ`* `=σ−1 andδ`* `=ασ`* `1 ``=ασ−11.


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* &equals;xnan&plus;...&plus;xa1&plus;a0&comma;L* &in;k[x; sigma*, delta*]


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:

θ=` = `cσθc+δ



θ`* `=`* `cσ+δ`* `


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



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.

See Also