Overview of Pseudo-linear Algebra - Maple Help
For the best experience, we recommend viewing online help using Google Chrome or Microsoft Edge.
Our website is currently undergoing maintenance, which may result in occasional errors while browsing. We apologize for any inconvenience this may cause and are working swiftly to restore full functionality. Thank you for your patience.

Online Help

All Products    Maple    MapleSim


Home : Support : Online Help : Mathematics : Algebra : Skew Polynomials : OreTools : Overview of Pseudo-linear Algebra

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

References

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. 

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

2. 

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

3. 

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

δ=ασ1 = δα

4. 

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

σ=βδ+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=σax+δa

  

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. 

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

6. 

θ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:

θca=cσa+δa

  

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

theta:KK,

  

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=Q1B+R1,Q1,R1k[x; sigma, delta],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=BQ2+R2,Q2,R2k[x; sigma, delta],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.

1. 

If σ=1, thenσ* =σ =1 andδ* =δ.

2. 

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* =xnan+...+xa1+a0,L* 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σ+δ

  

Set

θ* =cσ* +δ*

  

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.

See Also

OreTools