arXiv:1112.4769v2 [math.RA] 17 Aug 2012

A new closed formula for the Hermite
interpolating polynomial with applications on the
spectral decomposition of a matrix
Aristides I. Kechriniotis
Christos Tsonos

∗

Konstantinos K. Delibasis

‡

Nicholas Petropoulos

†

§

December 19, 2011

Abstract
We present a new closed form for the interpolating polynomial of the
general univariate Hermite interpolation that requires only calculation of
polynomial derivatives, instead of derivatives of rational functions. This
result is used to obtain a new simultaneous polynomial division by a common divisor over a perfect field. The above findings are utilized to obtain
a closed formula for the semi–simple part of the Jordan decomposition
of a matrix. Finally, a number of new identities involving polynomial
derivatives are obtained, based on the proposed simultaneous polynomial
division. The proposed explicit formula for the semi–simple part has been
implemented using the Matlab programming environment.

1

Introduction

The Hermite interpolation of total degree is described in the following Theorem
[1]:
Theorem 1.1. Given n distinct elements λ0 , λ1 , . . . , λn−1 in a perfect field k,
positive integers mi , i = 0, . . . , n − 1, and aij ∈ k for 0 ≤ i ≤ n − 1, 0 ≤ j ≤
mi − 1, then there exists one and only one polynomial r ∈ k[x] of degree less
Pn−1
than i=0
mi , such that
r(j) (λi ) = aij , 0 ≤ j ≤ mi − 1, 0 ≤ i ≤ n − 1.

(1.1)

∗ Department of Informatics, Technological Educational Institute of Lamia, 35100 Lamia,
Greece
† University of Central Greece, Dept. of Biomedical Informatics, Greece
‡ Department of Electronics, Technological Educational Institute of Lamia, 35100 Lamia,
Greece
§ Department of Electronics, Technological Educational Institute of Lamia, 35100 Lamia,
Greece

1

This polynomial r is explicitly given by,
r(x)

=


(k)
1 1 (x − λi )mi
aij
j! k!
Ω(x)
x=xi

−j−1
n−1
i −1 miX
X mX
i=0 j=0

k=0

Ω(x)
,
×
(x − λi )mi −j−k
where
Ω(x) =

n−1
Y

(x − λi )mi ,

i=0

and r(k) (a) is the k−th derivative of r at a.
The applications of hermite interpolation to numerical analysis is well known.
In this paper we show the use of a computationally more efficient formula for
the Hermite interpolation to a number of algebraic applications.
A number of forms of the interpolating polynomial r(x) have been reported
in the literature, however they all require calculation of derivatives of rational
polynomial functions (e.g. [1]), or recursive calculation of the coefficients aij of
Theorem 1.1 (e.g. [8]). We firstly propose a new closed form of the interpolating polynomial r of the univariate Hermite interpolation that requires only
calculation of polynomial derivatives instead of derivatives of rational functions,
as required in Theorem 1.1, thus achieving a substantial computational acceleration compared to the Theorem 1.1, without imposing any restrictions in the
generality of the interpolation. We then exploit this result to show a Theorem
for the calculation of the remainders of the simultaneous division of a number
of polynomials by a separable polynomial divisor, as derivatives of a unique
polynomial. Namely, let us note that the remainder r ∈ k[x] of the Euclidean
division of any polynomial P ∈ k[x] of degree n by a separable polynomial
Q ∈ k[x] of degree m, where n ≥ m, can be calculated in closed form using the
Langrange interpolation formula as following:
m
Y
(x − λj )
,
P (λi )
r(x) =
(λ
i − λj )
j=1
i=1
m
X

j6=i

where λ1 , . . . , λm are the roots of Q in the algebraic closure k of k. In this
work we extent this simplified idea of polynomial remainder calculation by Langrange interpolation, to achieve simultaneous polynomial division by a common
separable divisor, using the closed form of the interpolating polynomial of the
univariate Hermite interpolation r that we propose.
Furthermore, the above results will be used to obtain a new closed formula
for the semi–simple part of the Jordan decomposition of an algebraic element
in an arbitrary algebra. If k is a perfect field and A an algebra over k with unit
1, then the well–known result on the Jordan decomposition, (e.g. [2, 4, 7]) is
presented in the following theorem.
2

Theorem 1.2. For each algebraic A ∈ A there exist unique SA , NA ∈ k[A]
such that A = SA + NA , SA is semi–simple and NA is nilpotent.
It should be noted that in the case of k being algebraically closed and A is
a subalgebra of the matrix-algebra kn×n , then SA is semi–simple if and only if
SA is diagonalizable.
Theorem 1.2 has various interesting applications, such as efficient computation of high powers of A, therefore, efficient algorithms for the calculation of
SA in terms of A are of great importance. A proof of the existence of SA that
is presented in the book of Hoffman and Kunze [4], is based on the Newton’s
method and yields direct methods for computations. An algorithm, which is
essentially based on these ideas, is given by Levelt [6]. The algorithm of Bourgoyne and Cushman [3] is faster, because higher derivatives are used. In [9] D.
Schmidt has used the Newton’s method to construct the semi–simple part of
the Jordan decomposition of an algebraic element in an arbitrary algebra, showing quadratic convergence of the algorithm. Another approach uses the partial
fractions decomposition of the reciprocal of the minimal polynomial [5, 10, 11].
These works however, do not provide a closed form formula for SA as a polynomial of A. An explicit construction of the spectral decomposition of a matrix
using Hermite interpolation appears in [11]. However, this approach requires
the use of Taylor coefficients of the reciprocal of the matrix minimal polynomial.
In this work, we exploit our proposed simultaneous polynomial division by a
common separable divisor, to obtain a new closed formula for the semi–simple
part SA of the Jordan decomposition of an algebraic element A in an arbitrary
algebra. The proposed closed formula requires only evaluation of the derivatives
of the basic Hermite–like interpolation polynomials that are associated by the
eigenvalues of A, up to the maximum algebraic multiplicity of the roots of
the minimal polynomial of A, as well as matrix multiplication operations. The
derived closed formula for the semi–simple part of the Jordan decomposition has
been implemented in the Matlab programming environment. The sourse code
is provided and results are shown from it’s executions on examples of matrices
taken from the literature.
Furthermore, a number of new identities involving polynomial derivatives are
also shown, based on the the simultaneous polynomial division by a common
separable divisor.
The rest of the paper is organized as follows. In section 2 we present a
new closed form for Hermite interpolation. In section 3 we show a Theorem
for the calculation of the remainders of the simultaneous division of a number
of polynomials by a separable polynomial divisor, as derivatives of a unique
polynomial. In section 4 we present an explicit Formula for SA , the relative
source code in MATLAB environment, as well as some numerical examples from
the literature. Finally, in section 5 the main result of section 3 is generalized
and applied to the derivation of some interesting polynomial formulas.

3

2

A new closed form for Hermite interpolation

Let λ0 , λ1 , . . . , λn−1 be distinct elements in a perfect field k and m0 , m1 , . . . , mn−1
be positive integers. Let us denote by Lk the polynomials given by
Lk (x) =

n−1
Y
i=0
i6=k

(x − λi )mi
∈ k[x].
(λk − λi )mi

(2.1)

Furthernore, we denote by Λk , 0 ≤ k ≤ n − 1 the mk × mk lower triangular
matrices [lij ] ∈ kmk ×mk , 0 ≤ i, j ≤ mk − 1, given by
 i
(i−j)
(λk )
if
0 ≤ j ≤ i ≤ mk − 1
j (Lk )
lij :=
,
0
if
0 ≤ i < j ≤ mk − 1
where (Lk )(i−j) (λk ) is the derivative of order (i − j) of
λk . Thus Λk has the following representation


0
.
0 Lk (λk )

 0
1
1
(1)

(L
)
(λ
)
L
(λ
)
.
k
k
k k
0
1


.
.
.


.
.


.
.


mk −1
mk −1
(mk −1)
(mk −2)
(L
)
(λ
)
(L
)
(λk ) .
k
k
k
0
1

the polynomial Lk (x) at
. .
. .
.
.
. .


0

0


.
.

.


.

mk −1
L
(λ
)
k k
mk −1
(2.2)

For our purpose the following technical Lemmas are required:
Lemma 2.1. The matrices Λk , 0 ≤ k ≤ n − 1 are invertible with Λ−1
=
k
Pmk −1
i
)
,
where
I
×
m
unit
matrix.
(I
−
Λ
is
the
m
m
k
m
k
k
k
k
i=0

Proof. Clearly, for 0 ≤ k ≤ n − 1 holds Lk (λk ) = 1. Therefore, all matrices Λk ,
0 ≤ k ≤ n − 1 are invertible and unit diagonalP
lower triangular. Therefore, it
mk −1
(Imk − Λk )i = Imk .
follows (Imk − Λk )mk = 0 and consequently Λk i=0
Using the Leibnitz’s rule for derivatives, we easily get the following Lemma:

Lemma 2.2. For 0 ≤ i, s ≤ mk − 1 and 0 ≤ j, t ≤ n − 1, the following holds:

0
if
t 6= j

s
(x − λt )
0
if
t
=
j
and i < s . (2.3)
Lt (x))(i) |x=λj =
(
 i
s!
(i−s)
(L
)
(λ
)
if
t
=
j
and s ≤ i
j
j
s
Our proposed form of Hermite interpolation can now be presented in the
following Theorem.

Theorem 2.3. Given n distinct elements λ0 , λ1 , . . . , λn−1 in a perfect field k,
positive integers mi , i = 0, . . . , n − 1 , and aij ∈ k for 0 ≤ j ≤ n − 1, 0 ≤ i ≤

4

mj − 1, then there exists one and only one polynomial r ∈ k[x] of degree less
Pn−1
than i=0
mi , such that
r(i) (λj ) = aij , 0 ≤ j ≤ n − 1, 0 ≤ i ≤ mj − 1.

(2.4)

This polynomial r is explicitly given by,
r

=

n−1
X

Xj Λ−1
j Aj

(2.5)

j=0

=

j −1
n−1
X mX

Xj (Imj − Λj )k Aj ,

j=0 k=0

where the matrices Xj , Aj are given by
h
j)
Xj = Lj (x) (x−λ
Lj (x) . . .
1!
and
Aj =



a0j

aij

. .

(x−λj )mj −1
(mj −1)! Lj (x)

. amj −1j

T

i

,

.

Proof. It can be observed that (2.5) can be equivalently written in the following
form:
j −1
n−1
X mX
(x − λj )i
cij
r(x) =
Lj (x) ∈ k[x],
i!
j=0 i=0
where












c0j
c1j
.
.
.
cmj −1j









 = Λ−1 
j 






a0j
a1j
.
.
.
amj −1j






 , 0 ≤ j ≤ n − 1.




(2.6)

Now, by calculating the derivative of order i of the polynomial r at λj and using
(2.3) in Lemma 2.2 we obtain
(i)

r (λj ) =

i
X

k=0

 
i
(Lj )(i−k) (λj ),
ckj
k

(2.7)

for all 0 ≤ j ≤ n − 1, 0 ≤ i ≤ m − 1. Taking into consideration the definition
of Λj in (2.2), the system of equations (2.7) can be rewritten in the following
matrix form




r(λj )
c0j

 c1j 

r′ (λj )








.
.

 = Λj 
, 0 ≤ j ≤ n−1
(2.8)




.
.








.
.
cmj −1j
r(mj −1) (λj )
5

By substitutting (2.6) in (2.8), we get

 
r(λj )
a0j
′

  a1j
r
(λ
)
j

 

 
.
.

=

 
.
.

 

 
.
.
amj −1j
r(mj −1) (λj )






.




Hence, we derive that r(i) (λj ) = aij , 0 ≤ j ≤ n − 1, 0 ≤ i ≤ mj − 1. The second
equality of (2.5) is obtained by Lemma 2.1.
Moreover, it can be easily confirmed that any polynomial (x − λj )i Lj (x),
Pn−1
0 ≤ j ≤ n − 1, 0 ≤ i ≤ mj − 1 has degree less than i=0
mi , and since r is a
k- linear combination
of
these
polynomials,
we
conclude
that
the degree of r is
Pn−1
less than i=0 mi .

3

Simultaneous division of polynomials by separable polynomial

At this point we are ready to present the following generalization of Euclidean
polynomial division by a separable divisor, based on Theorem 2.3.
Theorem 3.1. Let g ∈ k[x] be a separable polynomial and λ0 , . . . , λn−1 be
the roots of g in the algebraic closure k of k . Then for any polynomials
f0 , f1 , . . . , fm−1 ∈ k[x], there exists unique r ∈ k[x] of degree less than mn
and unique polynomials q0 , q1 , ..., qm−1 ∈ k[x] such that
fi = r(i) + gqi , 0 ≤ i ≤ m − 1.
This result is optimal, in the sense that if m ≥ 1 and g is inseparable, then this
result is not true. The polynomial r is given by
r(x) =

n−1
X

Xj Λ−1
j Aj ∈ k [x] ,

j=0

where
Xj
Aj

=
=

h



Lj (x)

(x−λj )
Lj (x)
1!

. . .

(x−λj )m−1
(m−1)! Lj (x)

f0 (λj ) f1 (λj ) . . . fm−1 (λj )

T

i

,

and Lj , Λj are respectively as in (2.1), (2.2) by m0 = m1 = ... = mn−1 = m.
Proof. Let k be the dimension of the field k(λ0 , . . . , λn−1 ) as vector space over
k, that is
k = [k(λ0 , . . . , λn−1 ), k]
(3.1)
6

then there exist τ 1 , ...,τ k−1 in k(λ0 , . . . , λn−1 ) such that {1, τ 1 , ..., τ k−1 } is a
basis of k(λ0 , . . . , λn−1 ) as a vector space over k.
Now, using Theorem 2.3 by m0 = m1 = ... = mn−1 = m, we have that there
is unique polynomial rb ∈ k(λ0 , . . . , λn−1 )[x] given by (2.5) for m0 = m1 = ... =
mn−1 = m having degree less than mn such that
(b
r )(i) (λj ) = fi (λj )

(3.2)

for all 0 ≤ i ≤ m − 1, 0 ≤ j ≤ n − 1. Therefore there exist polynomials
qbi ∈ k(λ0 , . . . , λn−1 )[x], 0 ≤ i ≤ m − 1 such that
rb(i) = fi + gb
qi .

(3.3)

Moreover, by (3.1) we have that the dimension of k(λ0 , . . . , λn−1 )[x] as free module over k[x] is k and {1, τ 1 , ..., τ k−1 } is a basis of k(λ0 , . . . , λn−1 )[x] over k[x].
Therefore the polynomials rb, qbi ∈ k(λ0 , . . . , λn−1 )[x] can be uniquely written in
the following form:
n−1
X
rb = r +
τ s rs ,
(3.4)
s=1

and

qbi = qi +

n−1
X

τ s qsi , 0 ≤ i ≤ m − 1,

(3.5)

s=1

where r, rs , qi , qsi ∈ k[x] with deg r, deg ri < mn.
Setting (3.4) and (3.5) in (3.3) and using that {1, τ 1 , ..., τ k−1 } is linearly
independent over k[x], we get
r(i) = fi + gqi

(3.6)

for all 0 ≤ i ≤ m − 1.
Now from (3.6) we clearly get that r satisfies the identities (3.2) and since
the polynomial of degree less than mn satisfying the identities (3.2) is unique,
we conclude that r = rb.
Finally, suppose that Theorem 3.1 is true for one polynomial g ∈ k[x] having
a root λ ∈ k of multiplicity > 1. Then there exist a polynomial g0 in k[x] such
that
g(x) = (x − λ)2 g0 (x).
Applying Theorem 3.1 for g and f0 = f1 = 1 we obtain
r(x) = 1 + (x − λ)2 g0 (x)q0 (x),

(3.7)

(1)

(3.8)

r

2

(x) = 1 + (x − λ) g0 (x)q1 (x)

for some r, q0 , q1 ∈ k[x].
Differentiating (3.7), and setting x = λ in the resulting identity, as well as,
in (3.8) we respectively get
r(1) (λ) = 0 and r(1) (λ) = 1 .
That is not true.
7

Corrolary 3.2. Let g be as in Theorem 3.1. Then for any f ∈ k[x], c ∈ k−{0},
m ∈ N with m ≥ 2 there exists unique r ∈ k[x] of degree less than mn such that
r = f mod g and r′ = crg m−1 .
Proof. According to Theorem 3.1 there exists unique r ∈ k[x] of degree less than
mn, such that
mod g, . . . , cm−1 f = r(m−1)

f = r, cf = r′

mod g.

(3.9)

Now multiplying the i−th relation of (3.9) by c and afterwards substracting
from the result the i + 1−th relation we get
(r′ − cr)(i) = 0 mod g,
for all 0 ≤ i ≤ m − 2 and since g is separable we direct get the conclusion.

4

An explicit formula for SA

We will use Theorem 3.1 to give a closed formula for the semi–simple part of
the Jordan decomposition of an algebraic number of an algebra A over a perfect
field k.
Lemma 4.1. Let g ∈ k[x] be a separable polynomial and λ0 , . . . , λn−1 are the
roots of g in k. Let f ∈ k[x, y] be a polynomial of two variables and m be a
positive integer. Then there exists unique r ∈ k[x] of degree less than mn such
that
f (x, y) = r(x + y) mod I,
where I ⊂ k[x, y] is the ideal generated from the polynomials g(x), y m . Further
the polynomial r is given by
r(x) =

n−1
X

Xj Λ−1
j Aj ∈ k[x],

(4.1)

j=0

where the matrices Xj , Aj are given by
h
(x−λj )
Xj =
Lj (x) . . .
Lj (x)
1!
h
∂
Aj =
f (λj , 0) ∂y
f (λj , 0) . . .

(x−λj )m−1
(m−1)! Lj (x)
∂ m−1
∂y m−1 f (λj , 0)

i

iT

,
,

and Lj , Λj are as in (2.1), (2.2) by m0 = m1 = ... = mn−1 = m.
Proof. The polynomial f can be rewritten in the following form
f (x, y) =

m−1
X
i=0

1 ∂i
f (x, 0)y i + y m h(x, y),
i! ∂y i

for some h ∈ k[x, y].
8

(4.2)

Furthermore, according to Theorem 3.1 there exists unique polynomial r ∈
k[x] of degree less than mn, given by (4.1), such that:
∂i
f (x, 0) = r(i) (x)
∂y i

mod g(x), 0 ≤ i ≤ m − 1,

(4.3)

r(i) (x) i
y
i!

(4.4)

Combining (4.2) with (4.3) we get
f (x, y) =

m−1
X
i=0

mod I.

Furthermore, by using the Taylor formula we have:
m−1
X
i=0

r(i) (x) i
y = r(x + y) mod y m .
i!

(4.5)

Substituting (4.5) in (4.4), completes the required proof.
Let p ∈ k[x] be the minimal polynomial of an algebraic element A of an
algebra A over k with unit 1. Let λi , i = 0, 1, . . . , n − 1 be the distinct roots
ki , i = 1, 2, . . . , n − 1 be their respective multiplicities. We
of p in k, and let
Qn−1
denote pb(x) := i=0 (x − λi ) and m(p) := max {k0 , . . . , kn−1 }.
Theorem 4.2. The semi–simple part SA of the Jordan decomposition of A is
given by SA = r(A), where r(x) is the polynomial
r(x) =

n−1
X

Xj Λj−1 Aj ∈ k[x],

(4.6)

j=0

where
Xj

=

Aj

=

h


Lj (x)
λj

(x−λj )
Lj (x)
1!

0 . . .

0

T

. . .

(x−λj )m−1
(m−1)! Lj (x)

i

,

,

and Lj , Λj are as in (2.1), (2.2) by m0 = m1 = ... = mn−1 = m(p).
Proof. Since SA is the semi–simple part of A and NA is the nilpotent part of
A, the minimal polynomials of SA and NA are respectively pb(x) and xm(p) . So
m(p)
we have pb(SA ) = 0 and NA
= 0. Now if we apply Lemma 4.1 by choosing
f (x, y) = x, g(x) = pb(x) and m = m(p), and taking into account that f (x, 0) =
∂i
x, and ∂y
1 ≤ i ≤ m − 1 we have that for the polynomial r
i f (x, 0) = 0 for
given by (4.6) holds:
x = r(x + y) mod I ,
(4.7)
where I is the ideal generated from the polynomials pb(x) and y m(p) . Finally
setting x = SA and y = NA in (4.7) we get SA = r(SA + NA ) = r(A).
9

4.1

An implementation of the explicit formula for SA in
the MATLAB programming environment and some arithmetic examples

In this subsection we present a computational implementation in the MATLAB
programming environment for the calculation of the semi-simple part SA of the
jordan decomposition of A. The MATLAB source code of function semisimple
is provided, with appropriate exlanatory comments and pointers to the relevant
Equations. Instead of using the interpolating polynomial given in Theorem 4.2,
we implemented the equivalent formulation for the interpolating polynomial of
Eq. (2.6), by setting
T
[c0j , c1j , . . . , cm(p)−1j ]T = Λ−1
j [λj , 0, . . . , 0] .

The function’s input arguments are the matrix A whose semisimple part is
required, as well as the number of decimal digits that will be taken into consideration for calculating the multiplicity of the eigenvalues of A. Integer m(p)
in Theorem 4.2 which is equal to the maximum multiplicity of the roots of
the minimal polynomial of A, is calculated as the maximum number of non
zero elements of the rows and columns of the Jordan decomposition of A. The
main function (semisimple) uses two more functions that are also provided,
one for the calculation of the Lagrange polynomial coefficients and one for the
calculation of the coefficients nth power of a given polynomial.
function R=semisimple(A,tol)
% by A. Kechriniotis, K. Delibasis, 2009
% A: matrix whose semisimple part is required
% tol: number of digits to use for finding multiple eigenvalues of A
p=poly(A);
a=roots(p);
% determine multiplicity of roots according to tolerance tol
tol=10^tol;
r1=round(a*tol)/tol;
[r_uniq,i_uniq]=unique(r1);
for i=1:length(r_uniq)
multi_uniq(i)=sum(r1==r_uniq(i));
end
a=r_uniq;
n=length(a);
% determine m as the max root multiplicity of the minimal polynomial
J=jordan(A);
m=max(max(sum(J~=0)), max(sum(J~=0,2)));

10

% create a table with n rows to hold Langrange polynomial coefficients
as in (2.1)
for k=1:n
myLangr_coefs(k,:)=myLangr(a,k,n);
end
% Calculate cnm array in (2.6)
for j0=1:n
generate Lamda mxm matrix, as in (2.2)
for i=1:m
for j=1:m
if j>i
Lamda(i,j)=0;
else
l1=myLangr_coefs(j0,:);
l1=polypower(l1,m);
f1=nchoosek(i-1,j-1);
if i>1
calc (i-1) order derivative of l1
lk=l1;
for k=1:i-j
lk=polyder(lk);
end
Lamda(i,j)=f1*polyval(lk,a(j0));
else
no derivative of l1
Lamda(i,j)=f1*polyval(l1,a(j0));
end
end
end
end
I=diag(ones(size(A,1),1));
col1=[a(j0),zeros(1,m-1)]’;
c(:,j0)=(Lamda^-1)*col1;
col1;
end
R=zeros(size(A));
for i=1:m
for j=1:n
Ln=myLangr_coefs(j,:);
LnM=polypower(Ln,m);
R=R+c(i,j)*polyvalm(LnM,A)*((A-a(j)*I)^(i-1))/factorial(i-1);
end
end

11

function Ln=myLangr(a,n,N)
% a: is the vector of roots
% N: length of a
% n: integer between 1 and N inclusive
% Ln is an array of coefficients of the Lagrange polynomial
Ldenom=1;
Lnom=1;
for i=1:N
if i~=n
Ldenom=Ldenom*(a(n)-a(i));
Lnom=conv(Lnom,[1,-a(i)]);
end
end
Ln=Lnom/Ldenom;

function p1=polypower(p,n);
%p: an array of coefficients of the Lagrange polynomial
% n: integer power
% p1: array of coefficients of polynomial p raised to the nth power
p1=p;
if n>1
for i=1:n-1
p1=conv(p1,p);
end
end
In order to verify the accuracy of the above implementation, we present the
following arithmetic examples of the application of the above source code for
the calculation
part SA , taken from [5].
 of the semisimple

3 4 3
Let A =  2 7 4 . It is easy to verify that A has 2 unique eigenvalues:
−4 8 3
a0 = 1, a1 = 11 with multiplicity 2 and 1 respectively.
The

 matrices Λ0 , Λ1 ac
1
0
1 0
cording to Eq. (2.2) are calculated as Λ0 =
and Λ1 =
,
−0.2 1
0.2 1
whereas
 the matrix
 cij obtains the following values according, to Eq. (2.6):
1
11
c=
. The semisimple part is calculated according to Eq. (2.6):
0.2 −2.2


1 5.6 2.8
SA =  0 8.6 3.8 . It is easy to demonstrate that SA is semisimple (e.g. by
0 4.8 3.4
calculating the Jordan decomposition of SA which is a diagonal 3 × 3 matrix),
as well as that (A − SA ) is nilpotent, since (A − SA )2 is the 3 × 3 zero matrix.
The result obtained for SA by the proposed method is identical to the result
12

produced in [5].
The second arithmetic example is also taken from [5]. Let

0
−1
0
0
0
0
0
0
0
0
 −1
0
0
0
0
0
0
0
0
0

 0
0
1
−1
0
0
0
0
0
0

 0.25 0
−1
1
0
0
0
0
0
0

 0
0
0
0
2
−1
0
0
0
0
A=
 0
0 0.25 0
−1
2
0
0
0
0

 0
0
0
0
0
0
3
−1
0
0

 0
0
0
0
0.25
0
−1
3
0
0

 0
0
0
0
0
0
0
0
4 −1
0
0
0
0
0
0 0.25 0 −1 4










.








It is easy to show that the roots of the characteristic polynomial of A are the
following: a0 = 5, a1 = 4, a2 = −1, a3 = 3 (multiplicity equal to 2), a4 = 2
(multiplicity equal to 2), a5 = 1 (multiplicity equal to 2), a6 = 0. The matrices
Λi i = 0, 
. . . , 6 according
to Eq.

 (2.2) are calculated

as:

1
0
1
0
1
0
Λ0 =
, Λ1 =
, Λ2 =
,
−4.9 1
−2.5667 1
−1.667 1








1 0
1
0
1
0
1 0
Λ3 =
, Λ4 =
, Λ5 =
, Λ6 =
.
0 1
1.1667 1
2.5667 1
4.9 1
The matrix
 cij obtains the following values according to Eq.
 (2.6):
−1 0
1
2
3
4
5
c =
. The semisimple
−4.9 0 1.1667 0 −3.5 −10.2667 −24.5
part SA is calculated according to Eq. (2.6):

0
−1
0
0
0
0
0
0
0
0

−1
0
0
0
0
0
0
0
0
0


0
0
1
−1
0
0
0
0
0
0

 0.25
0
−1
1
0
0
0
0
0
0

 −0.0156 0.0156
0
0
2
−1
0
0
0
0

 −0.0156 0.0156
0.25
0
−1
2
0
0
0
0

 0.0039 −0.0026 −0.0156 0.0156
0
0
3
−1 0
0

 0.0052 −0.0039 −0.0156 0.0156
0.25
0
−1
3
0
0

 −0.0004 0.0002
0.0039 −0.0026 0.0156 0.0156
0
0
4 −1
−0.0007 0.0004
0.0052
0.0039 0.0156 0.0156 0.25 0 −1 4
Again this result is identical with Example 3 from [5]. It is also easy to verify
that the nilpotency holds, since (A − SA )2 = 0.

5

Further generalizations of Theorem 3.1 and
derived identities

The main result of this section is the generalization of Theorem 3.1, which is
expressed in the following Theorem.
13


















Theorem 5.1. Let g ∈ k[x] be separable of degree n. Let Π ∈ (k[x])m×m such
that det(Π) 6= 0. Then for any polynomials f0 , f1 ,. . . , fm−1 ∈ k[x] there exist
unique polynomial r ∈ k[x] of degree less than mn, such that




r
f0


 f1 
r′







.
. 



 mod g,
Π
=E
.
. 







.
. 
fm−1
r(m−1)
where E := gcd(g, det(Π)).
Proof. We start from

e = ΠΠ
e = det(Π)IM ,
ΠΠ

(5.1)

e is the adjugate of Π and Im is the m × m unit matrix.
where Π
Moreover, since E = gcd(g, det(Π)) one has that there exist H, G ∈ k[x]
such that
H det(Π) + Gg = E.
(5.2)
Combining (5.1) with (5.2) we get,
e = (E − gG)Im .
HΠΠ

(5.3)

Now, according to Theorem 3.1 there exist unique r ∈ k[x] of degree less than
mn such that




r
f0


 f1 
r′







.
. 
e

 = HΠ
 mod g.
(5.4)



.
. 







.
. 
fm−1
r(m−1)
Multiplying (5.4) from the left by Π and setting (5.3) in the resulting identity
we get the conclusion.
Remark 5.2. Choosing Π = Im in Theorem 5.1 we get Theorem 3.1. Therefore
Theorem 3.1 can be regarded as a generalization of Theorem 5.1.
Now we will apply Theorem 5.1 to produce some formulas for polynomials
involving derivatives.
Corrolary 5.3. Let g, g0 , g1 , . . . , gm−1 ∈ k[x] be polynomials. Assume that g
is separable and that
(gi , g) = 1, 0 ≤ i ≤ m − 1.
Then for any f0 , f1 , . . . , fm−1 ∈ k[x] there exists unique r ∈ k[x] of degree less
than mn, such that
gi r(i) = fi

mod g, 0 ≤ i ≤ m − 1.
14

Proof. Applying Theorem 5.1 by

g0 0
 0 g1

 .
Π := 
 .

 .
0
.

. .
. .
.
.

.
. . 0



0
0
.
.
.

.
.




,




gm−1

and afterwards using that E = gcd(g, det(Π) =
the conclusion.

Qm−1
i=0

gi ) = 1 we directly get

Corrolary 5.4. Let g, g0 , g1 , . . . , gm−1 ∈ k[x] be as in Corollary 5.3. Then for
any f0 , f1 , . . . , fm−1 ∈ k[x] there exists unique r of degree less than mn such
that
(gi r)(i) = fi mod g, 0 ≤ i ≤ m − 1.
Proof. Let Π ∈ (k[x])m×m be the matrix defined by





Π=




g
0
1 (1)
0 g1
.
.
.

m−1 (m−1)
gm−1
0

From the assumptions

0

1
1 g1
.
.
.

m−1 (m−2)
gm−1
1

. . .
. . .
.
.
.
. . .

0
0
.
.
.

m−1 (0)
m−1 gm−1






.




(5.5)

(gi , g) = 1, 0 ≤ i ≤ m − 1
we have
(det(Π), g) = 1.

(5.6)

Applying Theorem 5.1 for Π, as given in (5.5), using (5.6) and the Leibnitz’s
rule, we get the conclusion.

References
[1] I.S. Berezin, N.P. Zhidkov, Computing method, Pergamon (1973) (Translated from Russian) Chapter 8, Section 9).
[2] N. Bourbaki, Elements de Mathematique; Algebre, Hermann, Paris, 1958
(Chapter 7, Section 5;
[3] N. Burgoyne, R. Cushman, The decomposition of a linear mapping, Linear
Algebra Appl. 8 (1974) 515–519.
[4] K. Hoffman, R. Kunze, Linear Algebra, second ed., Prentice-Hall, Englewood Cliffs, NJ, 1971(Chapter 7, Section 7).
15

[5] P.F. Hsieh, M. Kohno, Y. Sibuya, Construction of a fundamental matrix
solution at a singular point of the first kind by means of the SN decomposition of matrices, Linear Algebra Appl. 239 (1996) 29–76.
[6] A.H.M. Levelt, The semi-simple part of a matrix, Algoritmen In De Algebra, A Seminar on Algebraic Algorithms, University of Nijmegen, 1993.
[7] T. Mulders, Computation of normal forms for matrices, Algoritmen In De
Algebra, A Seminar onAlgebraic Algorithms, University of Nijmegen, 1993.
[8] R. Sakai and P. Vertesi, Hermite-Fejer interpolations of higher order. III,
Studia Sci. Math. Hungar. 28 (1993), 87–97
[9] D. Schmidt, Construction of the Jordan decomposition by means of Newton’s method, Linear Algebra and its Applications 314 (2000) 75–89.
[10] G. Sobczyk, The generalized spectral decomposition of a linear operator,
College Math. J. 28 (1997), 27-38.
[11] L. Verde-Star, Interpolation approach to the spectral resolution of square
matrices, L’Enseignement Mathematique 52, (2006), 239–253.

16

