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:

$\mathrm{\delta }\left(a+b\right)=\mathrm{\delta }\left(a\right)+\mathrm{\delta }\left(b\right)$ for any a and b in k

$\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.

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

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:

$\mathrm{\theta }\left(u+v\right)=\mathrm{\theta }\left(u\right)+\mathrm{\theta }\left(v\right)$ for any u and v in V

$\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:

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,

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

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:

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:

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.

If $\mathrm{\sigma }=1$, then$\mathrm{\sigma }*=\mathrm{\sigma }$ $=1$ and$\mathrm{\delta }*=-\mathrm{\delta }$.

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{\sigma }}^{\left\{\mathrm{-1}\right\}}$ and$\mathrm{\delta }*=\mathrm{\alpha }\left(\mathrm{\sigma }*-1\right)$ $=\mathrm{\alpha }\left({\mathrm{\sigma }}^{\left\{\mathrm{-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:

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:

Set

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.