Transcript Linear ODE’s in Non-Commutative Associative Algebras

Linear ODE’s in NonCommutative Associative
Algebras
Gordon Erlebacher
Florida State University
Garret Sobczyk
UDLA
1/27/2004
UDLAP, Department of
Mathematics
Linear Scalar ODE
Constant coefficient a
dx
 ax,
dt
x  0  x
0
x  eat x0
a
Coefficient a(t)
dx
 a  t  x,
dt
x 0  x
0
t
a ( s ) ds

0
xe
x
0
Linear Matrix ODE
dX
 AX , X  0   X
0
dt
A  Gl  n,
dX
 XA, X  0   X
0
dt

A  Gl  n,
X  e At X 0
X  X 0e At
The exponential matrix function is defined by

An n
e  t
n 0 n !
At
Note:
AX  XA

Linear Matrix ODE(t)
dX
 At  X , X  0  X
0
dt
A  Gl  n,
t
X  e 0
A s ds
dX
 XA, X  0   X
0
dt

A  Gl  n,
t
A s ds

0
X  X 0e
X0
The exponential matrix function is defined by
n
 A  s  ds 
 0
 n
At
e 
t
n!
n 0
t

If and only if

A  s  A(t )  A( s) A  t   s, t
Matrix ODE
More generally, if the commutator
 A  s  , A  t   0
, use Picard iteration:
dX
 At  X
dt
X (t )  X 0   A  s  X ( s )ds
t
0
s

 X 0   A  s  X 0   A  s ' X ( s ')ds '


0
0
t
 X 0   A  s  X 0 ds   A  s   A  s ' X 0 ds ' ds
t
t
s
0
0
0
  A  s   A  s '  A  s "X 0 ds '' ds ' ds  H .O.T .
t
s
s'
0
0
0
H.O.T. : Higher Order Terms
More general Linear Matrix ODEs
dX
 A  t  X  XB (t )
dt
dX
 A(t ) XB(t )
dt
n
dX
  Ai  t  XBi  t 
dt i 0
Simple Matrix Equation
dX
 AXB
dt
d  x11
dt  x21
 1 0 
 4 2 
A
, B


0

3

1


2

x12   41 x11  21 x21 42 x21  22 x22 


x22   31 x11  11 x21 32 x21  12 x22 
Note that it is not possible to solve the equation in this form.
Furthermore, the structure of A and B have been destroyed.
Matrix Equation (cont.)
The solution is to define
Vec  X    x11
x12
x21
x22 
T
d
Vec  X   CVec( X )
dt
 41 0
 0 4
2
C 
 31 0

 0 32
 BT  A
21
0
1
0
0 
22 

0 

2 
Disadvantage: the natural structure of X is destroyed. Often, X has
physical significance, e.g., through its invariants. These
invariances are lost when using Vec(X).
and solve
Further Considerations
• In many problems, a scalar matrix
represents a choice of coordinate system
• It is often desirable to solve problems in a
coordinate-free manner!
• A coordinate free solution is expressed
using invariants of the individual elements
of the equation.
Matrix Invariants
Consider the matrix A. Its invariants are constant when A is subjected to
a similarity transformation:
A  SAS 1
Invariants of A (aij) include its eigenvalues, its determinant, and

 
i
i j
i
j
  
i j k
...
i
j
k
Quaternion invariants
Not clear what these are, since the concept of
eigenvalues is not defined in the same manner
as for matrices.
Example: Quaternion equation
It is well-known that a quaternion can be encoded as either a 2x2
complex matrix, a 4x4 real matrix. Other representations are also
possible. They are widely used in computer graphics to express
3
rotations in
q  q0  xi  yj  zk
Where the basis functions have the properties:
i 2  j 2  k 2  ijk  1
Based on these, it is easy to show that if
q1 , q2  H
where H is the space of quaternions, then
q  q1q2  H , q1 , q2  0
Quaternion ODE
dq
 aqb,
dt
a, q, b  H
Further Generalization
The space H of quaternions and the space G(n,C) of invertible matrices
form an associative, non-commutative Algebra.
Given an arbitrary associative, non-commutative algebra Alg, we wish to
solve analytically
dx n
  ai  t  xbi  t   f  t 
dt i0
where
ai  t  , bi  t  , f  t  , x  t Alg
An analytical solution of this general problem is not possible without
further restrictions. We assume:
bi , b j   0, i, j
Spectral Basis
Given an algebra Alg, any element a in the algebra has the spectral
decomposition
n
a   pi  i 0   i1qi ,
pi , qi  Alg,  ij 
i 0
The basis functions
pi , qi
have remarkable properties:
pi p j   ij
pi q j  q j ij , no implicit summation
qi q j  0, i  j
qiri  0, and qiri 1  0
Spectral Basis (cont.)
pi
qi
are idempotents;
are nilpotents of index
ri
i 0 are the eigenvalues of the element a in Alg
Consequence of this decomposition:
n 1 ri 1
f (a)   f 
i 0 j 0
where
n
 i 0  pi qij
n
d
f  x
1
 n
f  i 0  
n! dx n x
i0
Minimal Polynomial
Given an element a in Alg, and the spectral basis
S   S0
Sn 

 i ,r 1 
Si   i 0
i
The minimal polynomial is defined as
n
  a     a  ai 
mi
i 1
n
m   mi
i 1
Note:
pi  pi  a  , qi  qi  a  ,
polynomials of degree < m in the
element a
Assumptions
Consider the equation
dx n
  ai  t  xbi  t   f  t 
dt i1
x  0   x0
with initial condition
Also consider a general basis

S= Si  , Si  pi , qi ,
with idempotents
pi

, qiri 1 , i  1,
and nilpotents
qi
,r
Assumptions (cont.)
We assume that all
bi
can be expanded in the elements of S:
n
bi  t    bij  t 
j 1
rj
bij  t     ijk  t  pij qijk
k 1
By the properties of the spectral basis,
bi  t  , b j  s    0, when i  j , t , s
Linear Superposition
We would like to express the solution to
dx n
  ai  t  xbi  t   f  t 
dt i1
We would like to express the solution as a linear superposition of
simpler solutions. Right-multiply the equation by
p( n )  p1 j1 p2 j2
dxp n 
dt
Note that
bi , ji  t 
pnjn
n
  ai  t  xbi  t  p n   f  t  p n 
i1
n
  ai  t  xp n bi, j  t   f  n   t 
i
i1
has lives in the space spanned by

Si , ji  pi , ji
r 1
qi ,jij
i

Linear Superposition (cont.)
Given the solution to the reduced equation, the full solution is simply
n1
x
i1 1
nn
 xp
in 1
i1
pi2
pin
where we have used the idempotent property:
n1
1 
i1 1
nn
p
in 1
i1
pi2
pin
New Problem
Solve
dx n
  ai  t  xbi  t   f n   t 
dt i1
where the b’s form a commuting set and live in the space
spanned by a simple basis

Si  1 qi
Given the solution, right-multiply by
permutations.
qiri

p n  and sum over all index
We concentrate on the homogeneous equation. The forcing
term is handled via the standard technique of the method of
variation of constants (see paper).
First Step:
Multiply to the right by
dx
 a (t ) xb  t 
dt
S  1 q
T
q

r 1 T
dxS T
 a(t ) xb  t  S T  a  t  xBS T
dt
where
Ir
N
  0 1
0 
0
B
0 0

0 0
is the identity matrix of order
is a nilpotent matrix,
 r 1 
 r 2 
0
r
Nr  0


0 
 0 t  Ir  N
First Step (cont.)
Note: B is matrix of scalars, so commutes with elements of Alg. Therefore,
dxS T
 a(t ) xBS T  a  t  BxS T
dt
which is a matrix equation for the (1xr) matrix variable y  xS
Note that Bx=xB since matrices of complex numbers always commute with
elements of Alg.
T
Solve this equation making use of the fundamental solution of the scalar
equation
dx
   t  x,
dt
x  0  1
We denote the solution symbolically by
  t 
Fundamental Solution
The solution to
is
dx
   t  x,
dt
x  0   x0
x  t    t   t  x0
Similarly, the solution to the time-dependent linear matrix equation
dX
 At  X , X  0  X 0
dt
is
X  t    At   t  X 0
Note that this is a symbolic representation of the solution. One must
still determine how to compute it in practice.
Back to our problem …
We are trying to solve
dy
 a t  B t  y
dt
 a  t  0  t  I r y  a  t  N  t  y
It is easy to solve this equation symbolically using the fundamental
solution:
T
 0aI r 1aI N  aI 0
0 r
0 r
y t   

y  xS
The subscript to the fundamental solution are elements of Gl(r,Alg),
the algebra of rxr matrices whose elements lie in Alg.
The solution x(t) is found by left-multiplying y(t) by the row matrix
Er  1 0
0
x  t   Er 0aIr   1
0 aI r N 0 aI r
x0 S T
New Notation
Let
  a 0 I r ,
The ODE becomes
K  aN ,
   1K  
dy
   K  y
dt
The solution becomes:
xS T  Em   t    t  x0 S T
The solution to the inhomogeneous problem can be shown to be:
x  t   Em    t    t  x0 S T 
t

Em    t    t   1  s   1  s  f  s  ds  S T


0
General Equation:
dx n
  ai (t ) xbi  t 
dt i1
Rewrite the equation in the matrix form:
dx
 A  t  xBT  t 
dt
where
A  t    a1
an 
B  t    b1
bn 
Notation
To each
bi
associate a matrix
Bi  i 0  t  I ri  Ni  t 
where
 0  i1  t 

0
0

Ni  t  
0
0

0
0

Is a nilpotent of multiplicity
ri
 i ,r 1  t  

 i ,ri 2  t  


0 
i
0
Notation (cont.)
Define the tensor product of spectral bases:
S  S1 
 Sn
S T  S1T 
 SnT
and the overbar symbol (same definition for all subscripted matrices):
Clearly,
Bi  I r1 
 Bi 
B  B1 
 Bn
Bi  i 0 I ri  Ni
 I rn
Solution
Multiply to the right by
ST
d T
xS  AxBT S T  AB T xS T
dt
which is an equation linear in
y  xS T
Note that
 x, B  0
but
 A, B  0
The above equation is symbolically equivalent to the earlier differential equation
with a single term on the right-hand side. Therefore, the solution is simply
Solution (cont.)
n
AB T   ai  t  Bi  t 
i 1
K
where
n
   i
i1
n
K   Ki
i 1
The equation to solve reduces to the previous one (symbolically)
dy
   K  y
dt
Solution (cont.)
xS  y  EM   t    t  x0 S
T
where
M  m1m2
T
mn
The non-homogeneous solution also has a structure similar to that of the
simpler ODE (with one term on the right-hand side):
x  t   EM    t    t  x0 S T 
t

EM    t    t   1  s  1  s  f  s  ds  S T


0
Explicit Computations
(advantages of the decomposition)
By definition,    t  is the solution to
d
   t  ,
dt
  0  I M
which can be solved by Picart iteration:
   I M     s     s  ds
t
0
n
t
i 1
0
 I M    i  s     s  ds
Explicit Computation (cont.)
One more iteration will reveal the general structure of the solution:
n


   t   I M    ds1i1  s1  1    ds2i1  s2     s2  
0
i11
 i2 1

n
t
n
t
n
n
 I M    ds1i1  s1     ds1  ds2 i1  s1   i2  s2     s2 
i11

  
j
0
i1 1 i2 1
t
s1
0
0
t 
j 1
where
k 

n
 t     0 ds1 0
i 1
i 1
1
   I M
0
n
k
t
sk 1
dsk  ij  s j 
k
j 1
However …
n
n
i 1
i 1
i   0i aia I mi I M  0i aia  I M   t 
where
  t   Alg
It follows that
i   1 Ki  
where
Ki  I m1 
 ai Ni 
 I mn
is a tensor project of nilpotent matrices:
  a t  N t   0
mi
j 1
j
i
j
The series for   therefore has a finite number of terms!!!
Exact solutions may be computed.
Example: Quaternion equation
Consider the equation:
dx
 a  t  xb  t   f  t 
dt
where a,b,x,f lie in the space H of quaternions. We consider 3 cases:
I 
 II 
 III 
 no nilpotent, single subspace 
b  t   b0  t 
 no nilpotent, two subspaces 
b  t   b1  t  p1  b2  t  p2
Nilpotent of index 1, single subspace
b  t   b0  t   b1  t  q
bi  t  
Case I: b  t   b0  t 
t
t

x  t   b0a  t  x0   b0a f  s  ds 


0
Case II: b  t   b1  t  p1  b2 t  p2
Solution to homogeneous equation:
xH  t   b1a  t  x0 p1  b2a  t  x0 p2
Solution to non-homogeneous equation:
2
t

xNH  t    bi a x0   bi a1  s  f  s  ds  pi


0
i 1
Case III: b  t   b0  t   b1 t  q
Solution to homogeneous equation:

xH  t   b0a  t  x0   ds  s  x0 q
t
0

Solution to non-homogeneous equation:
xNH  t   xH  t   b0 a  ds bi a1  s  f  s 
t
0
 b0 a  t   ds1
t
0
1
bi a
 s1  f  s1  0
where
  t   b1a  t  ab a  t  b1  t   H
0
0
s1
ds2  s2  q
Possible extensions
•
•
•
•
Remove the constraint that bi , b j   0
Solve higher order linear ODEs in Alg
Solve systems of linear equations in Alg
Asymptotic analysis of equations defined
in Alg
• Develop efficient numerical algorithms to
compute the spectral basis of an arbitrary
element of Alg
FULL PAPER
http://www.csit.fsu.edu/~erlebach/publications/sobczyk_erlebacher_2004.pdf