# Computation of a Canonical Form for Linear 2D Systems

Authors: Mohamed Salah Boudellioua
Journal: International Journal of Computational Mathematics
 (2014)

---

## Abstract

Symbolic computation techniques are used to obtain a canonical
form for polynomial matrices arising from discrete 2D linear state-space
systems. The canonical form can be regarded as an extension of the
companion form often encountered in the theory of 1D linear systems. Using
previous results obtained by Boudellioua and Quadrat (2010) on the reduction by
equivalence to Smith form, the exact connection between the original polynomial
matrix and the reduced canonical form is set out. An example is given to
illustrate the computational aspects involved.


---

## Body

## 1. Introduction

Canonical forms play an important role in the modern theory of linear systems. In particular, the so-called companion matrix has been used by many authors in the analysis and synthesis of 1D linear control systems. For instance, Barnett [1] showed that many of the concepts encountered in 1D linear systems theory such as controllability, observability, stability, and pole assignment can be nicely linked via the companion matrix. Boudellioua [2] suggested a matrix form which can be regarded as a 2D companion form for a class of bivariate polynomials. These polynomials arise in the study of 2D linear discrete state-space systems describing, for example, 2D image processing systems, as suggested by Roesser [3]. However in that paper, the author did not establish the exact connection between the original matrix and the reduced canonical form. In this paper, using symbolic computation based on the OreModules [4] Maple package the connection between the original polynomial matrix and the canonical form is established.


## 2. Polynomial Matrices Arising from Linear 2D Systems

A 2D system is a system in which information propagates in two independent directions. These systems arise from applications such as image processing and iterative circuits. Several authors (Attasi [5], Fornasini and Marchesini [6], and Roesser [3]) have proposed different state-space models for 2D discrete linear systems. However, it has been shown that Roesser’s model is the most satisfactory and the most general model since the other models can be embedded in it. The model of Roesser is one in which the local state is divided into horizontal and vertical states which are propagated, respectively, horizontally and vertically by first order difference equations. The model has the form:
(1)
x
h
(
i
+
1
,
j
)
=
A
1
x
h
(
i
,
j
)
+
A
2
x
v
(
i
,
j
)
+
B
1
u
(
i
,
j
)
x
v
i
,
j
+
1
=
A
3
x
h
i
,
j
+
A
4
x
v
i
,
j
+
B
2
u
i
,
j
,
where x
h
(
i
,
j
) is the horizontal state vector, x
v
(
i
,
j
) is the vertical state vector, u
(
i
,
j
) is the input vector, and A
1, A
2, A
3, A
4, B
1, and B
2 are real constant matrices of appropriate dimensions. System (1) can be written in the polynomial form:
(2)
s
I
n
-
A
1
-
A
2
-
A
3
z
I
m
-
A
4
x
h
(
i
,
j
)
x
v
(
i
,
j
)
=
B
1
B
2
u
i
,
j
,
where s represents an advance operator in the horizontal direction and z represents an advance operator in the vertical direction. The polynomial matrix over R
[
s
,
z
],
(3)
T
s
,
z
=
s
I
n
-
A
1
-
A
2
-
A
3
z
I
m
-
A
4
,
is the characteristic matrix associated with (1). Throughout this paper, unless specified otherwise, D
=
K
[
x
1
,
…
,
x
n
] denotes the polynomial ring in the indeterminates x
1
,
…
,
x
n with coefficients in an arbitrary but fixed field K. First we present a few definitions that will be needed later in the paper.


## 3. Definitions

Definition 1.
LetD
=
K
[
x
1
,
…
,
x
n
]. The general linear group G
L
p
(
D
) is defined by
(4)
G
L
p
D
=
M
∈
D
p
×
p
∣
∃
N
∈
D
p
×
p
:
M
N
=
N
M
=
I
p
.
An element M
∈
G
L
p
(
D
) is called a unimodular matrix. It follows that M is unimodular if and only if the determinant of M is invertible in D that is M is a non-zero is a non-zero element of K.One of standard tasks carried out in systems theory is to transform a given system representation into a simpler form before applying any analytical or numerical method. The transformation involved must of course preserve relevant system properties if conclusions about the reduced system are to remain valid about the original one. An equivalence transformation used in the context of multidimensional systems is unimodular equivalence. This transformation can be regarded as an extension of Rosenbrock’s equivalence [7] from the univariate to the multivariate setting and is defined by as follows.Definition 2.
LetT
1 and T
2 denote two q
×
p matrices with elements in D; then, T
1 and T
2 are said to be unimodular equivalent if there exist two matrices M
∈
G
L
q
(
D
) and N
∈
G
L
p
(
D
) such that
(5)
T
2
=
M
T
1
N
.


## 4. Equivalence to Smith Form overD
=
K
x
1
,
…
,
x
n

The Smith formS of a p
×
q matrix P with elements in a domain D is usually the result of an equivalence transformation, that is, a transformation of the form
(6)
S
=
M
T
N
,
where M and N are unimodular matrices with elements in D, that is, square with determinant a unit of D. The resulting Smith form S is given by
(7)
D
0
;
p
<
q
,
D
;
p
=
q
,
D
0
;
p
>
q
,
where D is a t
×
t diagonal matrix given by
(8)
D
=
diag
⁡
(
Φ
1
,
Φ
2
,
…
,
Φ
r
,
0,0
,
…
,
0
)
,
t
=
min
⁡
(
p
,
q
), and r
= rank of T, and the invariant polynomials Φ
i in (8) are given by
(9)
Φ
i
=
d
i
d
i
-
1
,
i
=
1,2
,
…
,
r
,
d
0
=
1 and d
i is the greatest common divisor of the ith order minors of T. In order to show that any matrix can be brought by an equivalence transformation to its Smith form, it is usually required that D is a principal ideal domain or a Euclidean domain. The problem of equivalence of a multivariate polynomial matrix to its Smith form was first studied by Frost and Storey [8] who proposed only necessary conditions. Later Frost and Boudellioua [9] presented necessary and sufficient conditions for a class of bivariate polynomial matrices. Lee and Zak [10] also gave some necessary and sufficient conditions in terms of solutions of some polynomial equations. However, these conditions are difficult to test. Lin et al. [11] extended the result in [9] to the multivariate case and Boudellioua and Quadrat [12] generalized it to a larger class of matrices using a module theoretic approach. The establishment of the equivalence to the Smith form is based on the application of the well known Quillen-Suslin Theorem. For the implementation of Quillen-Suslin Theorem on Maple and applications to multidimensional systems theory, the reader is referred to the paper by Fabianska and Quadrat [13].Theorem 3 (Quillen and Suslin [14, 15]).
LetK be a principal ideal domain and D
=
K
x
1
,
…
,
x
n and let R
∈
D
q
×
p be a matrix which admits a right-inverse R
~
∈
D
p
×
q; that is, R
R
~
=
I
q. Then, there exists a unimodular matrix N
∈
G
L
p
(
D
) such that
(10)
R
N
=
I
q
0
.Now we state the necessary and sufficient conditions for the reduction of a class of polynomial matrices to the Smith form.Theorem 4 (see [9, 11, 12]).
LetT
∈
D
p
×
p, with full row rank; then, T is unimodular equivalent to the Smith form:
(11)
S
=
I
p
-
1
0
0
T
,
where |
T
|
=
det
⁡
(
T
)
∈
D if and only if there exist a vector U
∈
D
p which admits left inverse over D such that the matrix T
U has right inverse over D.


## 5. Canonical Form for Linear 2D Systems

Now letD
=
R
[
s
,
z
] and suppose now that there exists a vector U
∈
D
n
+
m such that the condition in Theorem 4 is satisfied. Then, it follows that the matrix T is equivalent over D to the Smith form:
(12)
S
=
I
n
+
m
-
1
0
0
T
,
where
(13)
T
=
s
I
n
-
A
1
-
A
2
-
A
3
z
I
m
-
A
4
is the 2D characteristic polynomial of the matrix A
=
A
1
A
2
A
3
A
4.Introduce the canonical form given in [2] for a matrix T in form (3) and let
(14)
T
=
∑
j
=
0
m
k
j
(
s
)
z
m
-
j
=
k
0
(
s
)
z
m
+
k
1
(
s
)
z
m
-
1
+
⋯
+
k
m
(
s
)
=
∑
i
=
0
n
‍
∑
j
=
0
m
‍
P
j
,
i
s
n
-
i
z
m
-
j
,
where k
0
(
s
) is monic and has degree equal to n and k
j
(
s
) have degrees less or equal to n, (
j
=
1,2
,
…
,
m
). Consider now the matrix T
F
∈
D
(
n
+
m
)
×
(
n
+
m
) in the canonical form:
(15)
T
F
=
s
I
n
-
F
1
-
A
¯
2
-
A
¯
3
z
I
m
-
F
4
,
where F
1 and F
2 are in companion form; that is,
(16)
F
1
=
0
1
⋯
0
0
0
⋯
0
⋮
⋮
⋱
⋮
F
1
(
n
,
n
)
F
1
(
n
,
n
-
1
)
⋯
F
1
(
n
,
1
)
,
F
4
=
0
1
⋯
0
0
0
⋯
0
⋮
⋮
⋱
⋮
F
4
(
m
,
m
)
F
4
(
m
,
m
-
1
)
⋯
F
4
(
m
,
1
)
,
A
¯
2
=
E
n
0, and E
n is the nth column of I
n.Equating the coefficients of the polynomials|
T
| and |
T
F
| determines uniquely the matrix A
¯
3
=
a
i
j. Furthermore, using the results given in [2], we get
(17)
F
1
n
,
i
=
-
P
0
,
n
-
i
+
1
,
i
=
1,2
,
…
,
n
,
F
4
m
,
j
=
-
P
m
-
j
+
1,0
,
j
=
1,2
,
…
,
m
,
A
¯
3
i
,
j
=
P
(
i
,
0
)
P
(
0
,
n
-
j
+
1
)
-
P
i
,
n
-
j
+
1
-
∑
k
=
1
i
-
1
‍
P
i
-
k
,
0
A
¯
3
k
,
j
.
It should be noted here that the unimodular equivalence of a system described by polynomial matrix T in (3), satisfying the condition in Theorem 4, means that such a system can be reduced to an equivalent presentation involving only one single equation in one unknown function. Furthermore, the class of 2D linear systems in (1) amenable to be reduced to the canonical form described above are those which are strongly controllable as studied by Zerz [16, page 75].Lemma 5.
The matrix in the canonical formT
F in (15) is unimodular equivalent to the Smith form (12).Proof.
Consider the matrixT
F in the canonical form (15), the vector U
=
E
n
+
m, and the highest order minor m
1,2
,
…
,
n
+
m
2,3
,
…
,
n
+
m
+
1 formed from the rows 1,2
,
…
,
n
+
m and columns 2,3
,
…
,
n
+
m
+
1 of the matrix (
T
F
E
n
+
m
); that is,
(18)
m
1,2
,
…
n
+
m
2,3
,
…
,
n
+
m
+
1
=
-
1
0
⋯
0
*
-
1
⋯
0
⋮
⋮
⋱
⋮
*
*
⋯
-
1
.
Clearly the matrix (
T
F
U
)
≡
(
T
F
E
n
+
m
) has right inverse over D since it has a highest order minor m
1,2
,
…
,
n
+
m
2,3
,
…
,
n
+
m
+
1 equal to (
-
1
)
n
+
m. Hence by Theorem 4, the matrix T
F is unimodular equivalent to the Smith form (12):
(19)
S
=
I
n
+
m
-
1
0
0
T
F
.The following result based on the Smith form establishes the connection between a polynomial matrixT in form (3) and its equivalent canonical form T
F in (15).Theorem 6.
LetT be a polynomial matrix in form (3) satisfying the condition given in Theorem 4; then T, is unimodular equivalent over D to the canonical form T
F in (15). Furthermore,
(20)
T
F
=
M
2
-
1
M
2
T
N
1
N
2
-
1
,
where the Smith form S
=
M
1
T
N
1
=
M
2
T
F
N
2.Proof.
By Theorem4, T is equivalent to the Smith form S
1, where S
1
(
n
+
m
,
n
+
m
)
=
|
T
|, and by Lemma 5, T
F is equivalent to the Smith form S
2, with S
2
(
n
+
m
,
n
+
m
)
=
|
T
F
|. Since |
T
|
=
|
T
F
|, it follows that T and T
F are equivalent to the same Smith form; that is, S
1
=
S
2; that is, there exist matrices M
1
,
N
1
,
M
2
,
N
2
∈
G
L
n
+
m
(
D
) such that S
=
M
1
T
N
1
=
M
2
T
F
N
2. By transitivity of the unimodular equivalence, T and T
F are also equivalent with
(21)
T
F
=
M
2
-
1
M
2
T
N
1
N
2
-
1
.


## 6. Illustrative Example

LetD
=
R
[
s
,
z
] and
(22)
T
=
s
+
1
-
1
-
1
1
1
s
-
1
1
2
-
2
z
+
1
-
3
0
-
3
2
z
-
2
,
where |
T
|
=
(
s
2
+
s
+
1
)
z
2
+
(
-
s
2
+
2
s
+
1
)
z
+
4
s
2
-
2
s
+
4. Using the equations in (17), the matrix in canonical form T
F associated with the polynomial |
T
| is obtained as
(23)
T
F
≡
s
I
2
-
F
1
-
A
¯
2
-
A
¯
3
z
I
2
-
F
4
=
s
-
1
0
0
1
s
+
1
-
1
0
2
3
z
-
1
2
-
3
4
z
-
1
.
First, we reduce the matrix T to the Smith form S; that is, compute M
1
∈
G
L
4
(
D
) and N
1
∈
G
L
4
(
D
) such that S
=
M
1
T
N
1 where S is given by (12).Using the method given by Boudellioua and Quadrat [12], consider vector U
1
=
0
0
-
1
-
1
T
∈
D
4 and P
1
=
(
T
U
1
)
∈
D
4
×
5. Using the package OreModules in Maple, see Chyzak et al. [4], we can check that P admits right inverse over D and we can compute minimal parametrization Q
m
∈
D
5 of P, where Q
m
=
Q
1
T
Q
2
T
T and P
1
Q
m
=
0,
(24)
Q
m
=
Q
1
Q
2
=
2
s
+
2
2
s
z
+
1
s
2
+
z
+
4
s
+
z
+
3
z
-
1
s
2
+
z
+
2
s
+
z
+
1
z
2
-
z
+
4
s
2
+
z
2
+
2
z
-
2
s
+
z
2
+
z
+
4
.
Computing the Syzygy Module K
1
∈
D
3
×
4 of Q
1, that is, K
1
Q
1
=
0, gives
(25)
K
1
=
2
1
z
-
1
-
z
-
1
1
s
-
1
1
s
+
1
-
1
-
1
1
,
where the matrix Q
3
∈
D
4
×
3 is the right inverse of K
1; that is,
(26)
Q
3
=
0
1
-
1
0
1
-
1
-
1
2
3
2
+
1
2
+
1
2
z
s
-
1
2
-
1
2
z
s
-
2
-
1
2
z
-
1
2
3
2
+
-
1
2
+
1
2
z
s
1
2
-
1
2
z
s
-
1
-
1
2
z
.
Thus, the matrix N
1
=
(
Q
3
Q
1
)
∈
G
L
4
(
D
) is given by(27)
N
1
=
0
1
-
1
2
+
2
s
0
1
-
1
2
s
-
1
2
3
2
+
1
2
+
1
2
z
s
-
1
2
-
1
2
z
s
-
2
-
1
2
z
z
+
1
s
2
+
4
+
z
s
+
z
+
3
-
1
2
3
2
+
-
1
2
+
1
2
z
s
1
2
-
1
2
z
s
-
1
-
1
2
z
z
-
1
s
2
+
z
+
2
s
+
z
+
1
.The matrix M
1
=
T
Q
3
-
U
-
1
∈
G
L
4
(
D
) is given by(28)
M
1
=
0
0
1
-
1
0
1
0
0
1
0
0
0
2
-
1
2
z
+
1
2
z
2
s
+
1
2
z
2
-
1
+
z
-
2
+
1
2
z
-
1
2
z
2
s
+
3
-
3
2
z
1
2
z
-
1
2
z
+
1and it can be easily verified that the matrix M
1
T
N
1 yields the Smith form:
(29)
S
=
I
3
0
0
Q
2
≡
I
3
0
0
s
2
+
s
+
1
z
2
+
2
s
-
s
2
+
1
z
+
4
s
2
-
2
s
+
4
,
where Q
2
=
|
T
|. Similarly, the matrix T
F is reduced to the Smith form S; that is, compute M
2
∈
G
L
4
(
D
) and N
2
∈
G
L
4
(
D
) such that S
=
M
2
T
F
N
2 where S is given by (12). Now consider vector U
2
=
0
0
0
-
1
T
∈
D
4 and P
2
=
(
T
F
U
2
)
∈
D
4
×
5. Using the package OreModules in Maple, we can check that P
2 admits right inverse over D and we can compute minimal parametrization Q
¯
m
∈
D
5 of P
2, where Q
¯
m
=
Q
¯
1
T
Q
¯
2
T
T and P
2
Q
¯
m
=
0,
(30)
Q
¯
m
=
1
s
s
2
+
s
+
1
s
2
z
+
3
+
z
s
+
2
+
z
z
2
-
z
+
4
s
2
+
z
2
+
2
z
-
2
s
+
z
+
4
+
z
2
.
Computing the Syzygy Module K
2
∈
D
3
×
4 of Q
¯
1, that is, K
2
Q
¯
1
=
0, gives
(31)
K
2
=
2
3
z
-
1
1
s
+
1
-
1
0
s
-
1
0
0
,
where the matrix Q
¯
3
∈
D
4
×
3 is the right inverse of K
1; that is,
(32)
Q
¯
3
=
0
0
0
0
0
-
1
0
-
1
-
s
-
1
-
1
-
z
-
3
-
z
-
s
z
.
Thus, the matrix N
2
=
(
Q
¯
3
Q
¯
1
)
∈
G
L
4
(
D
) is given by
(33)
N
2
=
0
0
0
1
0
0
-
1
s
0
-
1
-
s
-
1
s
2
+
s
+
1
-
1
-
z
-
3
-
z
-
s
z
s
2
z
+
3
+
z
s
+
2
+
z
.
The matrix M
2
=
T
Q
¯
3
-
U
2
-
1
∈
G
L
4
(
D
) is given by
(34)
M
2
=
0
0
1
0
0
1
0
0
1
0
0
0
z
2
+
2
z
-
2
+
z
2
-
z
+
4
s
z
2
-
z
+
4
-
1
+
z
1
and it can be easily verified that the matrix M
2
T
F
N
2 yields the Smith form
(35)
S
=
I
3
0
0
Q
¯
2
≡
I
3
0
0
s
2
+
s
+
1
z
2
+
2
s
-
s
2
+
1
z
+
4
s
2
-
2
s
+
4
,
where Q
¯
2
=
|
T
F
|
=
|
T
|. It follows that the matrix T
F is related to the matrix T by the following transformation:
(36)
T
F
=
M
T
N
,
where M
=
M
2
-
1
M
1
∈
G
L
4
(
D
) and N
=
N
1
N
2
-
1
∈
G
L
4
(
D
) are given by(37)
M
=
1
0
0
0
0
1
0
0
0
0
1
-
1
-
2
-
1
2
z
2
+
1
2
z
s
-
z
+
1
-
1
2
z
2
-
1
-
z
2
-
1
2
z
+
-
2
-
1
2
z
2
+
1
2
z
s
-
1
2
z
+
1
1
2
z
,
N
=
3
+
s
2
+
s
-
1
0
s
+
1
2
+
s
-
1
0
1
2
z
+
1
2
s
2
+
5
2
+
z
s
+
7
2
+
z
1
2
z
+
1
2
s
2
+
5
2
+
z
s
+
2
+
1
2
z
-
1
2
z
-
1
2
s
-
1
2
z
-
3
2
1
2
1
2
z
-
1
2
s
2
+
1
2
+
z
s
+
3
2
+
z
1
2
z
-
1
2
s
2
+
1
2
+
z
s
+
1
+
1
2
z
-
1
2
z
+
1
2
s
-
1
2
z
-
3
2
1
2
.


## 7. Conclusions

In this paper, the Smith form of a bivariate polynomial matrix together with symbolic computation techniques is used effectively to compute the equivalence transformations that reduce a class of 2D polynomial matrices to a canonical form. The classes of matrices considered are those amenable to be reduced by unimodular equivalence to a single equation in one unknown function. These matrices arise from 2D Roesser systems which are strongly controllable.



---

*Source: 487465-2014-12-15.xml*