# Fast Algorithms for Solving FLSR-Factor Block Circulant Linear Systems and Inverse Problem of A

Authors: Zhaolin Jiang
Journal: Abstract and Applied Analysis
 (2014)

---

## Abstract

Block circulant and circulant matrices have already become an ideal research area for solving various differential equations. In this paper, we give the definition and the basic properties of FLSR-factor block circulant (retrocirculant) matrix over field F. Fast algorithms for solving systems of linear equations involving these matrices are presented by the fast algorithm for computing matrix polynomials. The unique solution is obtained when such matrix over a field F is nonsingular. Fast algorithms for solving the unique solution of the inverse problem of A
X
=
b in the class of the level-2 FLS (
R
,
r
)-circulant(retrocirculant) matrix of type (
m
,
n
) over field F are given by the right largest common factor of the matrix polynomial. Numerical examples show the effectiveness of the algorithms.


---

## Body

## 1. Introduction

It is well known that block circulant and circulant matrices may play a crucial role in solving various differential equations such as bi-Hamiltonian partial differential equations, discretized partial differential equations, Hyperbolic-Parabolic partial differential equations, delay differential equations, undamped matrix differential equations, fractional diffusion equations, and Wiener-Hopf equations. By the radial properties of the fundamental solution and radial symmetry of the solution domain, Chen et al. [1] showed the circulant or block circulant features of the coefficient matrices for problems under pure Dirichlet or Neumann boundary condition. Using circulant matrix, Karasözen and Şimşek [2] considered periodic boundary conditions such that no additional boundary terms will appear after semidiscretization. In [3], the resulting dense linear system exhibits a special structure which can be solved very efficiently by a circulant preconditioned conjugate gradient method. Meyer and Rjasanow [4] have given an effective direct solution method for certain boundary element equations in 3D. The main theory of circulant dynamics considered in [5] is about circulant matrix. Ruiz-Claeyssen et al. [6] discussed factor block circulant and periodic solutions of undamped matrix differential equations. Wilde [7] developed a theory for the solution of ordinary and partial differential equations whose structure involves the algebra of circulants. Using circulant contraction of boundary, Chow and Milnes [8] got a numerical solution of a class of Hyperbolic-Parabolic partial differential equations. The Strang-type preconditioner was also used to solve linear systems from differential algebraic equations and delay differential equations; see [9–11].Circulant matrices arise in many applications in mathematics, physics, and other applied sciences in problems possessing a periodicity property [12–19] and they have been put on a firm basis with the work of Davis [20] and Jiang and Zhou [21]. The circulant matrices, long a fruitful subject of research [20, 21], have in recent years been extended in many directions [22–26]. Factor block circulant matrices and x
n
-
x
-
1-circulants are other natural extensions of this well-studied class and can be found in [12, 13].Algorithms for solving systems of linear equations involving matrices with the circulant or factor circulant orr-circulant structure were introduced in [27–32].The problem of finding a real matrixA of order n, satisfying A
X
=
b, for given n-dimension real vectors X and b, is called the inverse problem of the linear system A
X
=
b. The applications of this problem come from the study of absolute stability of a class of direct control systems [33]. Many authors have studied this problem for some special structured matrices: Peng and Hu [34] for reflexive and antireflexive matrices and Don [35], Chu [36], and Dai [37] for symmetric matrices.The fast algorithms presented in this paper avoid the problems of error and efficiency produced by computing a great number of triangular functions by means of other general fast algorithms. There is only error of approximation when the fast algorithm is realized by computers, so the result of the computation is accurate in theory. Specially, the result computed by a computer is accurate over the rational number field.Definition 1.
LetA
0
,
A
1
,
…
,
A
m
-
1
,
R be square matrices each of order n. We assume that R commutes with each of the A
k’s. A FLS R-factor block circulant matrix of type (
m
,
n
) over field F, denoted by FLScir
c
R
(
A
0
,
A
1
,
…
,
A
m
-
1
), is meant to be a square matrix of the form
(1)
A
=
[
A
0
A
1
⋯
A
m
-
1
R
A
m
-
1
A
0
+
A
m
-
1
⋯
A
m
-
2
R
A
m
-
2
R
A
m
-
1
+
A
m
-
2
⋯
A
m
-
3
⋯
⋯
⋯
⋯
R
A
2
R
A
3
+
A
2
⋯
A
1
R
A
1
R
A
2
+
A
1
⋯
A
0
+
A
m
-
1
]
.A FLSR-factor block circulant matrix of type (
m
,
1
) will be referred to as a scalar FLS r-circulant matrix [38–40]. In this case the matrix R reduces to a nonzero scalar that we will denote by r. When R is the identity matrix I, we drop the word “factor” in the above definition. This kind of matrices is just FLS block circulant. In particular, when A
0
,
A
1
,
…
,
A
m
-
1
,
R are all FLS r-circulant matrices, this kind of matrix is called level-2 FLS (
R
,
r
)-circulant matrix of type (
m
,
n
).Definition 2.
LetA
0
,
A
1
,
…
,
A
m
-
1
,
R be square matrices each of order n. We assume that R commutes with each of the A
k’s. A FLS R-factor block retrocirculant matrix of type (
m
,
n
) over field F, denoted by FLSretrocir
c
R
(
A
0
,
A
1
,
…
,
A
m
-
1
), is meant to be a square matrix of the form
(2)
A
=
[
A
0
⋯
A
m
-
2
A
m
-
1
A
1
⋯
A
0
+
A
m
-
1
R
A
0
A
2
⋯
A
1
+
R
A
0
R
A
1
⋯
⋯
⋯
⋯
A
m
-
2
⋯
A
m
-
3
+
R
A
m
-
4
R
A
m
-
3
A
0
+
A
m
-
1
⋯
A
m
-
2
+
R
A
m
-
3
R
A
m
-
2
]
.A FLSR-factor block retrocirculant matrix of type (
m
,
1
) will be referred to as scalar FLS r-retrocirculant. In this case, the matrix R reduces to a nonzero scalar that we will denote by r. When R is the identity matrix I, we drop the word “factor” in the above definition. This kind of matrices is just FLS block retrocirculant. In particular, when A
0
,
A
1
,
…
,
A
m
-
1
,
R are all FLS r-circulant matrices, this kind of matrix is called level-2 FLS (
R
,
r
)-retrocirculant matrix of type (
m
,
n
).For the convenience of application, we give the obvious results in the following lemmas.Lemma 3.
Let
A
=
F
L
S
c
i
r
c
R
(
A
0
,
A
1
,
…
,
A
m
-
1
)
be a FLS
R
-factor block circulant matrix over
F
and
B
=
F
L
S
r
e
t
r
o
c
i
r
c
R
(
A
m
-
1
,
A
m
-
2
,
…
,
A
1
,
A
0
)
a FLS
R
-factor block retrocirculant matrix over
F
. Then
B
K
=
A
or
B
=
A
K
, where
(3)
K
=
(
0
0
⋯
0
I
0
0
⋯
I
0
⋯
⋯
⋯
⋯
⋯
I
0
⋯
0
0
)
.Lemma 4 (see [31]).
Suppose that the partitioned polynomial matrix
(
F
(
x
)
I
0
G
(
x
)
0
I
)
is changed into the partitioned polynomial matrix
(
D
(
x
)
U
(
x
)
V
(
x
)
0
S
(
x
)
T
(
x
)
)
by a series of elementary row operations, then
D
(
x
)
is the right largest common factor of the matrix polynomial
F
(
x
)
and
G
(
x
)
, and
U
(
x
)
F
(
x
)
+
V
(
x
)
G
(
x
)
=
D
(
x
)
.The matrices, vectors, and polynomials considered in the following are always over any fieldF.


## 2. The Properties of FLSR-Factor Block Circulant Matrix

We defineℵ
R as the basic FLS R-factor block circulant matrix over F; that is,
(4)
ℵ
R
=
(
0
I
0
⋯
0
0
0
0
I
⋯
0
0
⋯
⋯
⋯
⋯
⋯
⋯
0
0
0
⋯
0
I
R
I
0
⋯
0
0
)
m
×
m
.
It is easily verified that the matrix polynomial G
(
x
)
=
x
m
I
n
-
x
I
n
-
R is the form characteristic polynomial of the matrix ℵ
R. In addition, ℵ
R
m
=
R
I
m
n
+
ℵ
R.In view of the structure of the powers of the basic FLSR-factor block circulant matrix ℵ
R over F, it is clear that
(5)
A
=
FLScir
c
R
(
A
0
,
A
1
,
…
,
A
m
-
1
)
=
∑
i
=
0
m
-
1
‍
A
i
ℵ
R
i
.
Thus, A is a FLS R-factor block circulant matrix over F if and only if A
=
F
(
ℵ
R
) for some matrix polynomial F
(
x
) over F. The matrix polynomial F
(
x
)
=
∑
i
=
0
m
-
1
‍
A
i
x
i will be called therepresenter of the FLS R-factor block circulant matrix A over F.By Definition1 and (5), it is clear that A is a FLS R-factor block circulant matrix over F if and only if A commutes with ℵ
R; that is,
(6)
A
ℵ
R
=
ℵ
R
A
.
In addition to the algebraic properties that can be easily derived from the representation (5), we mention the following. The product of two FLS R-factor block circulant matrices is a FLS R-factor block circulant matrix of the same type.Furthermore, two FLSR-factor block circulant matrices,
(7)
A
=
FLScir
c
R
(
A
0
,
A
1
,
…
,
A
m
-
1
)
,
B
=
FLScir
c
R
(
B
0
,
B
1
,
…
,
B
m
-
1
)
,
commute if the A
j’s commute with the B
j’s. Since FLS r-circulant matrices commute under multiplication, then level-2 FLS (
R
,
r
)-circulant matrices commute under multiplication.Theorem 5.
The inverse matrix
A
-
1
of a nonsingular FLS
R
-factor block circulant matrix
A
over
F
is also a FLS
R
-factor block circulant matrix of the same type.Proof.
From representation (5), we have A
=
∑
i
=
0
m
-
1
‍
A
i
ℵ
R
i and A
-
1 is also a FLS R-factor block circulant matrix of the same type if and only if there exist B
0
,
B
1
,
…
,
B
m
-
1 over F such that
(8)
A
-
1
=
∑
i
=
0
m
-
1
‍
B
i
ℵ
R
i
,
where B
0
,
B
1
,
…
,
B
m
-
1 are square matrices each of order n.
SinceA
A
-
1
=
I and ℵ
R
m
+
k
=
R
ℵ
R
k
+
ℵ
R
k
+
1, then
(9)
A
A
-
1
=
(
∑
i
=
0
m
-
1
‍
A
i
ℵ
R
i
)
(
∑
i
=
0
m
-
1
‍
B
i
ℵ
R
i
)
=
∑
i
=
0
m
-
1
‍
D
i
ℵ
R
i
=
I
m
n
if and only if
(10)
D
m
-
1
=
A
0
B
m
-
1
+
A
1
B
m
-
2
+
⋯
D
m
-
1
=
+
A
m
-
2
B
1
+
A
m
-
1
B
0
=
0
,
D
m
-
2
=
R
A
m
-
1
B
m
-
1
+
(
A
0
+
A
m
-
1
)
B
m
-
2
+
⋯
D
m
-
1
=
+
A
m
-
3
B
1
+
A
m
-
2
B
0
=
0
,
D
m
-
1
=
⋮
iiii
D
1
=
R
A
2
B
m
-
1
+
(
R
A
3
+
A
2
)
B
m
-
2
+
⋯
D
1
-
m
=
+
(
A
0
+
A
m
-
1
)
B
1
+
A
1
B
0
=
0
,
iiii
D
0
=
R
A
1
B
m
-
1
+
(
R
A
2
+
A
1
)
B
m
-
2
+
⋯
D
1
-
m
=
+
(
A
0
+
A
m
-
1
)
B
0
=
I
n
,
if and only if
(11)
A
(
B
m
-
1
T
,
…
,
B
1
T
,
B
0
T
)
T
=
(
0
,
…
,
0
,
I
n
)
T
.
Since A is nonsingular, so
(12)
(
B
m
-
1
T
,
…
,
B
1
T
,
B
0
T
)
T
=
A
-
1
(
0
,
…
,
0
,
I
n
)
T
.
By the above system of (12), the existence of B
0
,
B
1
,
…
,
B
m
-
1 in the system of (8) has been proved.Theorem 6.
Let
A
=
F
L
S
c
i
r
c
R
(
A
0
,
A
1
,
…
,
A
m
-
1
)
(
R
≠
0
)
be a FLS
R
-factor block circulant matrix of type
(
m
,
n
)
over
F
. Then
A
is nonsingular if and only if
I
n
is the right largest common factor of the matrix polynomial
F
(
x
)
and
G
(
x
)
, where
F
(
x
)
=
∑
i
=
0
m
-
1
‍
A
i
x
i
and
G
(
x
)
=
x
m
I
n
-
x
I
n
-
R
.Proof.
LetH
(
x
) be the right largest common factor of the matrix polynomial F
(
x
) and G
(
x
). Then there exists matrix polynomial U
1
(
x
),  V
1
(
x
),  Q
(
x
) such that
(13)
U
1
(
x
)
F
(
x
)
+
V
1
(
x
)
G
(
x
)
=
H
(
x
)
,
mmmmmiiimm
F
(
x
)
=
Q
(
x
)
H
(
x
)
.
Substitutingx by ℵ
R in the equation F
(
x
)
=
Q
(
x
)
H
(
x
), we have F
(
ℵ
R
)
=
Q
(
ℵ
R
)
H
(
ℵ
R
). Since F
(
ℵ
R
)
=
A is nonsingular, then H
(
ℵ
R
) is nonsingular. By Theorem 5, we know that there exists matrix polynomial H
1
(
x
) such that H
1
(
ℵ
R
)
H
(
ℵ
R
)
=
I
m
n; then
(14)
H
1
(
x
)
U
1
(
x
)
F
(
x
)
+
H
1
(
x
)
V
1
(
x
)
G
(
x
)
=
H
1
(
x
)
H
(
x
)
=
I
n
.
So I
n is the right largest common factor of the matrix polynomial F
(
x
) and G
(
x
).
Conversely, ifI
n is the right largest common factor of the matrix polynomial F
(
x
) and G
(
x
), then there exists matrix polynomial U
(
x
),  V
(
x
) such that
(15)
U
(
x
)
F
(
x
)
+
V
(
x
)
G
(
x
)
=
I
n
.
Substitutingx by ℵ
R in the above matrix equations, we have
(16)
U
(
ℵ
R
)
F
(
ℵ
R
)
+
V
(
ℵ
R
)
G
(
ℵ
R
)
=
I
m
n
.
Since F
(
ℵ
R
)
=
A and G
(
ℵ
R
)
=
0, then
(17)
U
(
ℵ
R
)
A
=
I
m
n
.
By (17), we know that A is nonsingular.Theorem 7.
Let
B
=
F
L
S
r
e
t
r
o
c
i
r
c
R
(
A
m
-
1
,
…
,
A
1
,
A
0
)
(
R
≠
0
)
be a FLS
R
-factor block retrocirculant matrix of type
(
m
,
n
)
over
F
. Then
B
is nonsingular if and only if
I
n
is the right largest common factor of the matrix polynomial
F
(
x
)
and
G
(
x
)
, where
F
(
x
)
=
∑
i
=
0
m
-
1
‍
A
i
x
i
and
G
(
x
)
=
x
m
I
n
-
x
I
n
-
R
.Proof.
SinceK is nonsingular, by Lemma 3, B is nonsingular if and only if A is nonsingular. By Theorem 6, we know that A is nonsingular if and only if I
n is the right largest common factor of the matrix polynomial F
(
x
) and G
(
x
). Then B is nonsingular if and only if I
n is the right largest common factor of the matrix polynomial F
(
x
) and G
(
x
).Theorem 8.
Let
A
=
F
L
S
c
i
r
c
R
(
A
0
,
A
1
,
…
,
A
m
-
1
)
(
R
≠
0
)
be a nonsingular FLS
R
-factor block circulant matrix of type
(
m
,
n
)
over
F
. Then there exists matrix polynomial
U
(
x
)
such that
A
-
1
=
U
(
ℵ
R
).Proof.
Since matrixA
=
FLScir
c
R
(
A
0
,
A
1
,
…
,
A
m
-
1
) is nonsingular, we can change the partitioned polynomial matrix (
F
(
x
)
I
n
0
G
(
x
)
0
I
n
) into the partitioned polynomial matrix (
I
n
U
(
x
)
V
(
x
)
0
S
(
x
)
T
(
x
)
) by a series of elementary row operations.
By Lemma4, we have
(18)
U
(
x
)
F
(
x
)
+
V
(
x
)
G
(
x
)
=
I
n
.
Substituting x by ℵ
R in the above matrix equations, we have
(19)
U
(
ℵ
R
)
F
(
ℵ
R
)
+
V
(
ℵ
R
)
G
(
ℵ
R
)
=
I
m
n
.
Since F
(
ℵ
R
)
=
A and G
(
ℵ
R
)
=
0, then
(20)
U
(
ℵ
R
)
A
=
I
m
n
.
By (20), we know that A
-
1
=
U
(
ℵ
R
).Theorem 9.
Let
B
=
F
L
S
r
e
t
r
o
c
i
r
c
R
(
A
m
-
1
,
…
,
A
1
,
A
0
)
(
R
≠
0
)
be a nonsingular FLS
R
-factor block retrocirculant matrix of type
(
m
,
n
)
over
F
. Then there exists matrix polynomial
U
(
x
)
such that
B
-
1
=
K
U
(
ℵ
R
).Proof.
By Lemma3, we know that B
=
A
K. Since both B and K are nonsingular, then A is nonsingular and B
-
1
=
K
A
-
1. By Theorem 8, there exists matrix polynomial U
(
x
) such that A
-
1
=
U
(
ℵ
R
). Then B
-
1
=
K
U
(
ℵ
R
).
By Theorems8 and 9, we can get the fast algorithm for finding the inverse of the FLS R-factor block circulant matrix or the inverse of the FLS R-factor block retrocirculant matrix.
Step  1. From the matrix A
=
FLScir
c
R
(
A
0
,
A
1
,
…
,
A
m
-
1
)  (
R
≠
0
)  (or B
=
FLSretrocir
c
R
(
A
m
-
1
,
…
,
A
1
,
A
0
)
(
R
≠
0
)), we get the matrix polynomial F
(
x
)
=
∑
i
=
0
m
-
1
‍
A
i
x
i
,
G
(
x
)
=
x
m
I
n
-
x
I
n
-
R.
Step  2. Change the partitioned polynomial matrix (
F
(
x
)
I
n
G
(
x
)
0
) into the partitioned polynomial matrix (
D
(
x
)
U
(
x
)
0
S
(
x
)
) by a series of elementary row operations.
Step  3. If D
(
x
)
=
I
n, then the matrix A
=
FLScir
c
R
(
A
0
,
A
1
,
…
,
A
m
-
1
) (or B
=
FLSretrocir
c
R
(
A
m
-
1
,
…
,
A
1
,
A
0
)) is nonsingular and A
-
1
=
U
(
ℵ
R
)    (or B
-
1
=
K
U
(
ℵ
R
)).


## 3. Fast Algorithms for Solving a FLSR-Factor Block Circulant (or Retrocirculant) Linear System

Consider the FLSR-factor block circulant (or retrocirculant) linear system
(21)
A
X
=
b
,
where A is a FLS R-factor block circulant (or retrocirculant) matrix of type (
m
,
n
) over F,  X
=
(
x
01
,
x
02
,
…,x
0
n
,
…
,
x
(
m
-
1
)
1
,
x
(
m
-
1
)
2
,
…
,
x
(
m
-
1
)
n
)
T and b
=
(
b
(
m
-
1
)
n
,
…
,
b
(
m
-
1
)
2
,
b
(
m
-
1
)
1
,
…
,
b
0
n
,
…
,
b
02
,
b
01
)
T.IfA is nonsingular, then (21) has a unique solution
(22)
X
=
A
-
1
b
.The key problem is how to findA
-
1
b; for this purpose, we first prove the following results.Theorem 10.
Let
A
=
F
L
S
c
i
r
c
R
(
A
0
,
A
1
,
…
,
A
m
-
1
)
(
R
≠
0
)
be a nonsingular FLS
R
-factor block circulant matrix of type
(
m
,
n
)
over
F
and
b
=
(
b
(
m
-
1
)
n
,
…
,
b
(
m
-
1
)
2
,
b
(
m
-
1
)
1
,
…
,
b
0
n
,
…
,
b
02
,
b
01
)
T. 						Then there exists a unique FLS
R
-factor block circulant matrix
E
=
F
L
S
c
i
r
c
R
(
E
0
,
E
1
,
…
,
E
m
-
1
)
of type
(
m
,
n
)
over
F
such that the unique solution of
A
X
=
b
is the last column (or the first column) of the partitioned matrix
(
E
m
-
1
T
,
…
,
E
1
T
,
(
E
0
+
E
m
-
1
)
T
)
T.Proof.
Since matrixA
=
FLScir
c
R
(
A
0
,
A
1
,
…
,
A
m
-
1
) is nonsingular, the representer of A is F
(
x
)
=
∑
i
=
0
m
-
1
‍
A
i
x
i and G
(
x
)
=
x
m
I
n
-
x
I
n
-
R.
Let the matrix polynomialC
(
x
)
=
(
C
0
-
C
m
-
1
)
+
∑
i
=
1
m
-
1
‍
C
i
x
i be constructed by b
=
(
b
(
m
-
1
)
n
,
…
,
b
(
m
-
1
)
2
,
b
(
m
-
1
)
1,…
,
b
0
n
,
…
,
b
02
,
b
01
)
T,  where C
i
=
FLScir
c
r
(
b
i
1
-
b
i
n
,
b
i
2
,
…
,
b
i
n
)  (or C
i
=
FLScirc
(
b
i
n
,
b
i
1
,
…
,
b
i
(
n
-
1
)
) or C
i
=
FLSretrocir
c
r
(
b
i
n
,
…
,
b
i
2
,
b
i
1
)), the last column (or the first column) of C
i is (
b
i
n
,
…
,
b
i
2
,
b
i
1
)
T, and the matrix C
i commutes with the matrix R, for i
=
0,1
,
…
,
m
-
1.
By Lemma4 and Theorem 6, we can change the partitioned polynomial matrix (
F
(
x
)
⋮
I
n
0
⋮
C
(
x
)
G
(
x
)
⋮
0
I
n
⋮
0
) into the partitioned polynomial matrix (
I
n
⋮
U
(
x
)
V
(
x
)
⋮
H
(
x
)
0
⋮
S
(
x
)
T
(
x
)
⋮
H
1
(
x
)
)  by a series of elementary row operations. Then,
(23)
(
U
(
x
)
V
(
x
)
S
(
x
)
T
(
x
)
)
(
F
(
x
)
G
(
x
)
)
=
(
I
n
0
)
,
(
U
(
x
)
V
(
x
)
S
(
x
)
T
(
x
)
)
(
C
(
x
)
0
)
=
(
H
(
x
)
H
1
(
x
)
)
.
That is,
(24)
U
(
x
)
F
(
x
)
+
V
(
x
)
G
(
x
)
=
I
n
,
U
(
x
)
C
(
x
)
=
H
(
x
)
.
Substitutingx by ℵ
R in the above two equations, respectively, we have
(25)
U
(
ℵ
R
)
F
(
ℵ
R
)
+
V
(
ℵ
R
)
G
(
ℵ
R
)
=
I
m
n
.
U
(
ℵ
R
)
C
(
ℵ
R
)
=
H
(
ℵ
R
)
.
Since F
(
ℵ
R
)
=
A and G
(
ℵ
R
)
=
0, then
(26)
U
(
ℵ
R
)
A
=
I
m
n
.
By (26), we know that U
(
ℵ
R
) is a unique inverse A
-
1 of A. Let E
=
H
(
ℵ
R
)
=
FLScir
c
R
(
E
0
,
E
1
,
…
,
E
m
-
1
). By (25), we have
(27)
A
-
1
C
(
ℵ
R
)
=
FLScir
c
R
(
E
0
,
E
1
,
…
,
E
m
-
1
)
.
Since the last column (or the [
(
m
-
1
)
n
+
1
]th column) of the matrix A
-
1
C
(
ℵ
R
) is A
-
1
b and the last column (or the [
(
m
-
1
)
n
+
1
]th column) of the FLScir
c
R
(
E
0
,
E
1
,
…
,
E
m
-
1
) is the last column (or the first column) of the partitioned matrix (
E
m
-
1
T
,
…
,
E
1
T
,
(
E
0
+
E
m
-
1
)
T
)
T,  by (27), we know that the unique solution A
-
1
b of A
X
=
b is the last column (or the first column) of the partitioned matrix (
E
m
-
1
T
,
…
,
E
1
T
,
(
E
0
+
E
m
-
1
)
T
)
T.
By Theorem10, we can get the fast algorithm for solving the FLS R-factor block circulant linear system A
X
=
b, where A
=
FLScir
c
R
(
A
0
,
A
1
,
…
,
A
m
-
1
)  (
R
≠
0
),  X
=
(
x
01
,
x
02
,
…
,
x
0
n
,
…
,
x
(
m
-
1
)
1
,
x
(
m
-
1
)
2
,
…
,
x
(
m
-
1
)
n
)
T,  and b
=
(
b
(
m
-
1
)
n
,
…
,
b
(
m
-
1
)
2
,
b
(
m
-
1
)
1
,
…
,
b
0
n
,
…
,
b
02
,
b
01
)
T.
Step  1. From the FLS R-factor block circulant linear system A
X
=
b, we get the matrix polynomial F
(
x
)
=
∑
i
=
0
m
-
1
‍
A
i
x
i and G
(
x
)
=
x
m
I
n
-
x
I
n
-
R.
Step  2. Let the matrix polynomial C
(
x
)
=
(
C
0
-
C
m
-
1
)
+
∑
i
=
1
m
-
1
‍
C
i
x
i be constructed by b
=
(
b
(
m
-
1
)
n
,
…
,
b
(
m
-
1
)
2
,
b
(
m
-
1
)
1
,
…
,
b
0
n
,
…
,
b
02
,
b
01
)
T, where C
i
=
FLScir
c
r
(
b
i
1
-
b
i
n
,
b
i
2
,
…
,
b
i
n
) (or C
i
=
FLScirc
(
b
i
n
,
b
i
1
,
…
,
b
i
(
n
-
1
)
) or C
i
=
FLSretrocir
c
r
(
b
i
n
,
…
,
b
i
2
,
b
i
1
)), the last column (or the first column) of C
i is (
b
i
n
,
…
,
b
i
2
,
b
i
1
)
T, and the matrix C
i commutes with the matrix R, for i
=
0,1
,
…
,
m
-
1.
Step  3. Change the partitioned polynomial matrix (
F
(
x
)
C
(
x
)
G
(
x
)
0
) into the partitioned polynomial matrix (
D
(
x
)
H
(
x
)
0
H
1
(
x
)
) by a series of elementary row operations.
Step  4. If D
(
x
)
=
I
n, then the FLS R-factor block circulant linear system A
X
=
b has a unique solution. Substituting x by ℵ
R in matrix polynomial H
(
x
), we have the FLS R-factor block circulant matrix E
=
H
(
ℵ
R
)
=
FLScir
c
R
(
E
0
,
E
1
,
…
,
E
m
-
1
). So the unique solution of A
X
=
b is the last column (or the first column) of the partitioned matrix (
E
m
-
1
T
,
…
,
E
1
T
,
(
E
0
+
E
m
-
1
)
T
)
T.Theorem 11.
Let
B
=
F
L
S
r
e
t
r
o
c
i
r
c
R
(
A
m
-
1
,
…
,
A
1
,
A
0
)
(
R
≠
0
)
be a nonsingular FLS
R
-factor block retrocirculant matrix of type
(
m
,
n
)
over
F
and
b
=
(
b
(
m
-
1
)
n
,
…
,
b
(
m
-
1
)
2
,
b
(
m
-
1
)
1
,
…
,
b
0
n
,
…
,
b
02
,
b
01
)
T. 						Then there exists a unique FLS
R
-factor block circulant matrix
E
=
F
L
S
c
i
r
c
R
(
E
0
,
E
1
,
…
,
E
m
-
1
)
of type
(
m
,
n
)
over
F
such that the unique solution of
B
X
=
b
is the last column (or the first column) of the partitioned matrix
(
(
E
0
+
E
m
-
1
)
T
,
E
1
T
,
…
,
E
m
-
1
T
)
T.Proof.
Since bothB and K are nonsingular, by Lemma 3, we know that A is nonsingular and B
X
=
b if and only if A
K
X
=
b. By Theorem 10, we know that there exists a unique FLS R-factor block circulant matrix E
=
FLScir
c
R
(
E
0
,
E
1
,
…
,
E
m
-
1
) of type (
m
,
n
) over F such that the unique solution of A
K
X
=
b in a variable K
X is the last column (or the first column) of the partitioned matrix (
E
m
-
1
T
,
…
,
E
1
T
,
(
E
0
+
E
m
-
1
)
T
)
T. So the unique solution X of B
X
=
b is the last column (or the first column) of the partitioned matrix (
(
E
0
+
E
m
-
1
)
T
,
E
1
T
,
…
,
E
m
-
1
T
)
T.
By Theorem11, we can get the fast algorithm for solving the FLS R-factor block retrocirculant linear system B
X
=
b, where B
=
FLSretrocir
c
R
(
A
m
-
1
,
…
,
A
1
,
A
0
)  (
R
≠
0
),  X
=
(
x
01
,
x
02
,
…
,
x
0
n
,
…
,
x
(
m
-
1
)
1
,
x
(
m
-
1
)
2, …
,
x
(
m
-
1
)
n
)
T,  and b
=
(
b
(
m
-
1
)
n
,
…
,
b
(
m
-
1
)
2
,
b
(
m
-
1
)
1
,
…
,
b
0
n
,
…
,
b
02
,
b
01
)
T.
Step  1. From the FLS R-factor block retrocirculant linear system B
X
=
b, we get the matrix polynomial F
(
x
)
=
∑
i
=
0
m
-
1
‍
A
i
x
i,  G
(
x
)
=
x
m
I
n
-
x
I
n
-
R.
Step  2. Let the matrix polynomial C
(
x
)
=
(
C
0
-
C
m
-
1
)
+
∑
i
=
1
m
-
1
‍
C
i
x
i be constructed by b
=
(
b
(
m
-
1
)
n
,
…
,
b
(
m
-
1
)
2
,
b
(
m
-
1
)
1
,
…
,
b
0
n
,
…
,
b
02
,
b
01
)
T,  where C
i
=
FLScir
c
r
(
b
i
1
-
b
i
n
,
b
i
2
,
…
,
b
i
n
) (or C
i
=
FLScirc
(
b
i
n
,
b
i
1
,
…
,
b
i
(
n
-
1
)
) or C
i
=
FLSretrocir
c
r
(
b
i
n
,
…
,
b
i
2
,
b
i
1
)), the last column (or the first column) of C
i is (
b
i
n
,
…
,
b
i
2
,
b
i
1
)
T, and the matrix C
i commutes with the matrix R, for i
=
0,1
,
…
,
m
-
1.
Step  3. Change the partitioned polynomial matrix (
F
(
x
)
C
(
x
)
G
(
x
)
0
) into the partitioned polynomial matrix (
D
(
x
)
H
(
x
)
0
H
1
(
x
)
) by a series of elementary row operations.
Step  4. If D
(
x
)
=
I
n, then the FLS R-factor block retrocirculant linear system B
X
=
b has a unique solution. Substituting x by ℵ
R in matrix polynomial H
(
x
), we have the FLS R-factor block circulant matrix E
=
H
(
ℵ
R
)
=
FLScir
c
R
(
E
0
,
E
1
,
…
,
E
m
-
1
). So the unique solution of B
X
=
b is the last column (or the first column) of the partitioned matrix (
(
E
0
+
E
m
-
1
)
T
,
E
1
T
,
…
,
E
m
-
1
T
)
T.


## 4. Fast Algorithm for Solving the Inverse Problem ofA
X
=
b

In this section, sufficient and necessary conditions of existence of the unique solution of the inverse problem ofA
X
=
b in the class of the level-2 FLS (
R
,
r
)-circulant matrices of type (
m
,
n
) over F and that of the level-2 FLS (
R
,
r
)-retrocirculant matrices of type (
m
,
n
) over F are presented. Fast algorithms for solving the unique solution of the inverse problem of A
X
=
b in the class of the level-2 FLS (
R
,
r
)-circulant matrices of type (
m
,
n
) over F and that of the level-2 FLS (
R
,
r
)-retrocirculant matrices of type (
m
,
n
) over F are given by the right largest common factor of the matrix polynomial.Theorem 12.
Let
X
=
(
x
01
,
x
02
,
…
,
x
0
n
,
…
,
x
(
m
-
1
)
1
,
x
(
m
-
1
)
2
,
…
,
x
(
m
-
1
)
n
)
T
,
b
=
(
b
01
,
b
02
,
…
,
b
0
n
,
…
,
b
(
m
-
1
)
1,
b
(
m
-
1
)
2
,
…
,
b
(
m
-
1
)
n
)
T
,
R
=
F
L
S
c
i
r
c
r
(
r
0
,
r
1
,
…
,
r
n
-
1
)
,
X
=
F
L
S
c
i
r
c
R
(
X
m
-
1
-
X
0
,
X
m
-
2
,
…
,
X
1
,
X
0
)
, and
B
=
F
L
S
c
i
r
c
R
(
B
m
-
1
-
B
0
,
B
m
-
2
,
…
,
B
1
,
B
0
)
, where
X
i
=
F
L
S
c
i
r
c
r
(
x
i
n
-
x
i
1
,
x
i
(
n
-
1
)
,
…
,
x
i
2
,
x
i
1
)
and
B
i
=
F
L
S
c
i
r
c
r
(
b
i
n
-
b
i
1
,
b
i
(
n
-
1
)
,
…
,
b
i
2
,
b
i
1
)
,
i
=
0,1
,
…
,
m
-
1. 						Then the inverse problem of
A
X
=
b
has a unique solution in the class of the level-2 FLS
(
R
,
r
)
-circulant matrices of type
(
m
,
n
)
if and only if
X
Y
=
b
has a unique solution.Proof.
If the inverse problem ofA
X
=
b has a unique solution in the class of the level-2 FLS (
R
,
r
)-circulant matrices of type (
m
,
n
), then there exists a unique level-2 FLS (
R
,
r
)-circulant matrices of type (
m
,
n
)  A
=
FLScir
c
R
(
A
0
,
A
1
,
…
,
A
m
-
1
) such that A
X
=
b. Then
(28)
FLScir
c
R
(
A
0
,
A
1
,
…
,
A
m
-
1
)
(
X
0
T
,
…
,
X
m
-
1
T
)
T
=
(
B
0
T
,
B
1
T
,
…
,
B
m
-
1
T
)
T
,
where A
i
=
FLScir
c
r
(
a
i
0
,
a
i
1
,
…
,
a
i
(
n
-
1
)
).
Letβ
=
(
a
(
m
-
1
)
(
n
-
1
)
,
…
,
a
(
m
-
1
)
1
,
a
(
m
-
1
)
0
+
a
(
m
-
1
)
(
n
-
1
)
,
…
,
a
1
(
n
-
1
)
,
…
,
a
11
,
a
10
+
a
1
(
n
-
1
)
,
a
0
(
n
-
1
)
+
a
(
m
-
1
)
(
n
-
1
)
,
…,a
01
+
a
(
m
-
1
)
1
,
a
00
+
a
0
(
n
-
1
)
+
a
(
m
-
1
)
0
+
a
(
m
-
1
)
(
n
-
1
)
)
T.
By the multiplication of partitioned matrix and level-2 FLS(
R
,
r
)-circulant matrices commute under multiplication and (28), we know that β is the unique solution of X
Y
=
b.
IfX
Y
=
b has a unique solution  Y
=
(
a
(
m
-
1
)
(
n
-
1
)
,
…
,
a
(
m
-
1
)
1
,
a
(
m
-
1
)
0
,
…
,
a
0
(
n
-
1
)
,
…
,
a
01
,
a
00
)
T, and let A
=
FLScir
c
R
(
A
0
-
A
m
-
1
,
A
1
,
…
,
A
m
-
1
) and B
=
FLScir
c
R
(
B
m
-
1
-
B
0
,
B
m
-
2
,
…
,
B
1
,
B
0
), where A
i
=
FLScir
c
r
(
a
i
0
-
a
i
(
n
-
1
)
,
a
i
1
,
…
,
a
i
(
n
-
1
)
) and B
i
=
FLScir
c
r
(
b
i
n
-
b
i
1
,
b
i
(
n
-
1
)
,
…
,
b
i
2
,
b
i
1
),  i
=
0,1
,
…
,
m
-
1. Then X
A
=
B has a unique solution A
=
X
-
1
B. Since X
-
1
X
=
(
0
,
…
,
0,1
)
T, then A
X
=
X
-
1
B
X
=
B
X
-
1
X
=
b. So A
=
X
-
1
B is the unique solution of the inverse problem of A
X
=
b in the class of the level-2 FLS (
R
,
r
)-circulant matrices of type (
m
,
n
).Theorem 13.
The inverse problem of
A
X
=
b
has a unique solution in the class of the level-2 FLS
(
R
,
r
)
-circulant matrices of type
(
m
,
n
)
if and only if
I
n
is the right largest common factor of the matrix polynomial
D
(
x
)
and
G
(
x
)
, where
D
(
x
)
=
(
X
m
-
1
-
X
0
)
+
∑
i
=
1
m
-
1
‍
X
m
-
1
-
i
x
i
and
G
(
x
)
=
x
m
I
n
-
x
I
n
-
R
and
X
,
b
,
X
i
(
i
=
0,1
,
…
,
m
-
1
)
are given in Theorem12.Proof.
By Theorem12, we know that the inverse problem of A
X
=
b has a unique solution in the class of the level-2 FLS (
R
,
r
)-circulant matrices of type (
m
,
n
) if and only if X
Y
=
b has a unique solution, if and only if X is nonsingular, if and only if I
n is the right largest common factor of the matrix polynomial D
(
x
) and G
(
x
) by Theorem 6, where X is given in Theorem 12.
By Lemma4 and Theorems 12 and 13, we have the following fast algorithms for solving the unique solution of the inverse problem of A
X
=
b in the class of the level-2 FLS (
R
,
r
)-circulant matrices of type (
m
,
n
).
Step  1. From X
=
(
x
01
,
x
02
,
…
,
x
0
n
,
…
,
x
(
m
-
1
)
1
,
x
(
m
-
1
)
2
,
…
,
x
(
m
-
1
)
n
)
T and b
=
(
b
01
,
b
02
,
…
,
b
0
n
,
…
,
b
(
m
-
1
)
1, b
(
m
-
1
)
2
,
…
,
b
(
m
-
1
)
n
)
T, we get the matrix polynomial D
(
x
)
=
(
X
m
-
1
-
X
0
)
+
∑
i
=
1
m
-
1
‍
X
m
-
1
-
i
x
i and H
(
x
)
=
(
B
m
-
1
-
B
0
)
+
∑
i
=
1
m
-
1
‍
B
m
-
1
-
i
x
i, where X
i
=
FLScir
c
r
(
x
i
n
-
x
i
1
,
x
i
(
n
-
1
)
,
…
,
x
i
2
,
x
i
1
) and  B
i
=
FLScir
c
r
(
b
i
n
-
b
i
1
,
b
i
(
n
-
1
)
,
…
,
b
i
2
,
b
i
1
),  i
=
0,1
,
…
,
m
-
1.
Step  2. Change the partitioned polynomial matrix (
D
(
x
)
H
(
x
)
G
(
x
)
0
) into the partitioned polynomial matrix (
U
(
x
)
V
(
x
)
0
S
(
x
)
) by a series of elementary row operations, where G
(
x
)
=
x
m
I
n
-
x
I
n
-
R,  R
=
FLScir
c
r
(
r
0
,
r
1
,
…, r
n
-
1
).
Step  3. If U
(
x
)
=
I
n, then the X
=
FLScir
c
R
(
X
m
-
1
-
X
0
,
X
m
-
2
,
…
,
X
1
,
X
0
) is nonsingular. So the inverse problem of A
X
=
b has a unique solution A
=
X
-
1
B
=
V
(
ℵ
R
) in the class of the level-2 FLS (
R
,
r
)-circulant matrices of type (
m
,
n
).Theorem 14.
Let
X
′
=
(
x
(
m
-
1
)
1
,
x
(
m
-
1
)
2
,
…
,
x
(
m
-
1
)
n
,
…
,
x
01
,
x
02
,
…
,
x
0
n
)
T
. Then the inverse problem of
C
X
′
=
b
has a unique solution in the class of the level-2 FLS
(
R
,
r
)
-retrocirculant matrices of type
(
m
,
n
)
if and only if
X
Y
=
b
has a unique solution, where
X
,
R
, and
b
are given in Theorem12.Proof.
SinceK
X
=
X
′, where X is given in Theorem 12 and K is given in (3), the inverse problem of C
X
′
=
b has a unique solution in the class of the level-2 FLS (
R
,
r
)-retrocirculant matrices of type (
m
,
n
) if and only if the inverse problem of C
K
X
=
b in a variable C
K has a unique solution in the class of the level-2 FLS (
R
,
r
)-circulant matrices of type (
m
,
n
). By Lemma 3, C
K
X
=
b if and only if A
X
=
b. By Theorem 12, we know that the inverse problem of A
X
=
b has a unique solution in the class of the level-2 FLS (
R
,
r
)-circulant matrices of type (
m
,
n
) if and only if X
Y
=
b has a unique solution.Theorem 15.
The inverse problem of
C
X
′
=
b
has a unique solution in the class of the level-2 FLS
(
R
,
r
)
-retrocirculant matrices of type
(
m
,
n
)
if and only if
I
n
is the right largest common factor of the matrix polynomial
D
(
x
)
and
G
(
x
)
, where
D
(
x
)
and
G
(
x
)
are given in Theorem13 and
X
′
and
b
are given in Theorem14.Proof.
From the proof of Theorem14, we know that the inverse problem of C
X
′
=
b has a unique solution in the class of the level-2 FLS (
R
,
r
)-retrocirculant matrices of type (
m
,
n
) if and only if the inverse problem of A
X
=
b has a unique solution in the class of the level-2 FLS (
R
,
r
)-circulant matrices of type (
m
,
n
). By Theorem 13, the inverse problem of A
X
=
b has a unique solution in the class of the level-2 FLS (
R
,
r
)-circulant matrices of type (
m
,
n
) if and only if I
n is the right largest common factor of the matrix polynomial D
(
x
) and G
(
x
).
By Lemma4 and Theorems 14 and 15, we have the following fast algorithms for solving the unique solution of the inverse problem of C
X
′
=
b in the class of the level-2 FLS (
R
,
r
)-retrocirculant matrices of type (
m
,
n
).
Step  1. From X
′
=
(
x
(
m
-
1
)
1
,
x
(
m
-
1
)
2
,
…
,
x
(
m
-
1
)
n
,
…
,
x
01
,
x
02
,
…
,
x
0
n
)
T and b
=
(
b
01
,
b
02
,
…
,
b
0
n
,
…
,
b
(
m
-
1
)
1
,
b
(
m
-
1
)
2
,
…
,
b
(
m
-
1
)
n
)
T, we get the matrix polynomial D
(
x
)
=
(
X
m
-
1
-
X
0
)
+
∑
i
=
1
m
-
1
‍
X
m
-
1
-
i
x
i and H
(
x
)
=
(
B
m
-
1
-
B
0
)
+
∑
i
=
1
m
-
1
‍
B
m
-
1
-
i
x
i, where X
i
=
FLScir
c
r
(
x
i
n
-
x
i
1
,
x
i
(
n
-
1
)
,
…
,
x
i
2
,
x
i
1
) and B
i
=
FLScir
c
r
(
b
i
n
-
b
i
1
,
b
i
(
n
-
1
)
,
…
,
b
i
2
,
b
i
1
),  i
=
0,1
,
…
,
m
-
1.
Step  2. Change the partitioned polynomial matrix (
D
(
x
)
H
(
x
)
G
(
x
)
0
) into the partitioned polynomial matrix (
U
(
x
)
V
(
x
)
0
S
(
x
)
) by a series of elementary row operations, where G
(
x
)
=
x
m
I
n
-
x
I
n
-
R and R
=
FLScir
c
r
(
r
0
,
r
1
,
…
,
r
n
-
1
).
Step  3. If U
(
x
)
=
I
n, then the X
=
FLScir
c
R
(
X
m
-
1
-
X
0
,
X
m
-
2
,
…
,
X
1
,
X
0
) is nonsingular. So the inverse problem of C
X
′
=
b has a unique solution C
=
V
(
ℵ
R
)
K in the class of the level-2 FLS (
R
,
r
)-retrocirculant matrices of type (
m
,
n
).


## 5. Numerical Examples

Example 1.
Solve the FLSR-factor block circulant linear system
(29)
A
X
=
b
,
where A
=
FLScir
c
R
(
A
0
,
A
1
), R
=
(
2
1
3
3
)
,
A
0
=
(
1
2
6
3
)
,
A
1
=
(
1
0
0
1
), and b
=
(
0,3
,
0,3
)
T.
FromA
=
FLScir
c
R
(
A
0
,
A
1
), we get the polynomial matrix
(30)
F
(
x
)
=
(
1
+
x
2
6
3
+
x
)
,
(31)
G
(
x
)
=
(
x
2
-
x
-
2
-
1
-
3
x
2
-
x
-
3
)
,
respectively.
LetC
0
=
FLScir
c
3
(
b
01
-
b
02
,
b
02
)
=
FLScir
c
3
(
3,0
)
=
(
3
0
0
3
),
(32)
C
1
=
FLScir
c
3
(
b
11
-
b
12
,
b
12
)
=
FLScir
c
3
(
3,0
)
=
(
3
0
0
3
)
,
C
(
x
)
=
(
C
0
-
C
1
)
+
C
1
x
=
(
3
x
0
0
3
x
)
.
Then,(33)
(
F
(
x
)
C
(
x
)
G
(
x
)
0
)
=
(
1
+
x
2
3
x
0
6
3
+
x
0
3
x
-
2
-
x
+
x
2
-
1
0
0
-
3
-
3
-
x
+
x
2
0
0
)
.
We can change the above partitioned polynomial matrix into the partitioned polynomial matrix(34)
(
1
0
-
21
2
x
-
25
2
x
2
+
1
2
x
3
+
3
x
4
z
1
0
1
21
2
x
+
9
x
2
5
2
x
-
5
2
x
2
-
3
2
x
3
0
0
*
*
0
0
*
*
)
,
where z
1
=
-
(
5
/
2
)
x
+
(
5
/
3
)
x
2
+
(
19
/
6
)
x
3
-
(
1
/
3
)
x
4
-
(
1
/
2
)
x
5, by a series of elementary row operations, where the polynomials lying in * need not to be known.
SinceD
(
x
)
=
I
2, then the FLS R-factor block circulant linear system A
X
=
b has a unique solution. On the other hand,
(35)
H
(
x
)
=
(
-
21
2
x
-
25
2
x
2
+
1
2
x
3
+
3
x
4
z
1
21
2
x
+
9
x
2
5
2
x
-
5
2
x
2
-
3
2
x
3
)
=
(
-
21
2
-
5
2
21
2
5
2
)
x
+
(
-
25
2
5
3
9
-
5
2
)
x
2
+
(
1
2
19
6
0
-
3
2
)
x
3
+
(
3
-
1
3
0
0
)
x
4
+
(
0
-
1
2
0
0
)
x
5
,
where z
1
=
-
(
5
/
2
)
x
+
(
5
/
3
)
x
2
+
(
19
/
6
)
x
3
-
(
1
/
3
)
x
4
-
(
1
/
2
)
x
5.
Substitutingx by ℵ
R in the above matrix polynomial H
(
x
), we have the FLS R-factor block circulant matrix
(36)
E
=
H
(
ℵ
R
)
=
(
-
5
2
6
-
3
)
I
4
+
(
-
11
5
15
-
6
)
ℵ
R
=
FLScir
c
R
(
E
0
,
E
1
)
,
where E
0
=
(
-
5
2
6
-
3
),  E
1
=
(
-
11
5
15
-
6
), and ℵ
R
=
(
0
I
2
R
I
2
). Then partitioned matrix is as follows:
(37)
(
E
1
E
0
+
E
1
)
=
(
-
11
5
15
-
6
-
16
7
21
-
9
)
.
So the unique solution ofA
X
=
b is the last column of the partitioned matrix (
E
1
E
0
+
E
1
); that is, X
=
(
5
,
-
6,7
,
-
9
)
T.Example 2.
Find the solution of the inverse problem ofA
X
=
b in the class of the level-2 FLS (
R
,
3
)
-circulant matrices of type (
2,2
), where X
=
(
0,1
,
2,3
)
T,  b
=
(
1,2
,
1,2
)
T, and R
=
FLScir
c
3
(
1,3
).
FromX
=
(
0,1
,
2,3
)
T, b
=
(
1,2
,
1,2
)
T, and R
=
FLScir
c
3
(
1,3
), we get the polynomial matrix
(38)
D
(
x
)
=
(
x
2
6
2
+
x
)
,
H
(
x
)
=
(
x
x
3
x
2
x
)
,
(39)
G
(
x
)
=
(
-
1
-
x
+
x
2
-
3
-
9
-
4
-
x
+
x
2
)
,
respectively. Then,
(40)
(
D
(
x
)
H
(
x
)
G
(
x
)
0
)
=
(
x
2
x
x
6
2
+
x
3
x
2
x
-
1
-
x
+
x
2
-
3
0
0
-
9
-
4
-
x
+
x
2
0
0
)
.
We can change the above partitioned polynomial matrix into the partitioned polynomial matrix(41)
[
1
0
z
2
z
3
0
1
z
4
z
5
0
0
*
*
0
0
*
*
]
,
where z
2
=
(
19
/
127
)
x
-
(
63
/
508
)
x
2
+
(
19
/
508
)
x
3
+
(
3
/
508
)
x
4,  z
3
=
(
29
/
762
)
x
-
(
185
/
1524
)
x
2
+
(
8
/
381
)
x
3  +  (
1
/
254
)
x
4,  z
4
=
(
267
/
254
)
x
-
(
39
/
254
)
x
2
-
(
9
/
254
)
x
3, and z
5
=
(
225
/
254
)
x
-
(
10
/
127
)
x
2
-
(
3
/
127
)
x
3, by a series of elementary row operations, where the polynomials lying in * need not to be known.
SinceU
(
x
)
=
I
2, then the inverse problem of A
X
=
b has a unique solution in the class of the level-2 FLS (
R
,
3
)-circulant matrices of type (
2,2
). On the other hand,
(42)
V
(
x
)
=
(
z
2
z
3
z
4
z
5
)
=
(
19
127
29
762
267
254
225
254
)
x
+
(
-
63
508
-
185
1524
-
39
254
-
10
127
)
x
2
+
(
19
508
8
381
-
9
254
-
3
127
)
x
3
+
(
3
508
1
254
0
0
)
x
4
,
where z
2
=
(
19
/
127
)
x
-
(
63
/
508
)
x
2
+
(
19
/
508
)
x
3
+
(
3
/
508
)
x
4,  z
3
=
(
29
/
762
)
x
-
(
185
/
1524
)
x
2
+
(
8
/
381
)
x
3  +  (
1
/
254
)
x
4,  z
4
=
(
267
/
254
)
x
-
(
39
/
254
)
x
2
-
(
9
/
254
)
x
3,  and z
5
=
(
225
/
254
)
x
-
(
10
/
127
)
x
2
-
(
3
/
127
)
x
3.
Substitutingx by ℵ
R in the above matrix polynomial V
(
x
), we know that a unique solution of the inverse problem of A
X
=
b in the class of the level-2 FLS (
R
,
3
)-circulant matrices of type (
2,2
) is
(43)
A
=
V
(
ℵ
R
)
=
-
1
127
(
77
47
141
124
)
I
4
+
1
127
(
48
26
78
74
)
ℵ
R
=
FLScir
c
R
(
A
0
,
A
1
)
=
1
127
(
-
77
-
47
48
26
-
141
-
124
78
74
282
248
-
29
-
21
744
530
-
63
-
50
)
,
where  A
0
=
-
(
1
/
127
)
(
77
47
141
124
),  A
1
=
(
1
/
127
)
(
48
26
78
74
), and ℵ
R
=
(
0
I
2
R
I
2
).


## 6. Conclusion

We give the definition and the basic properties of FLSR-factor block circulant (retrocirculant) matrix over field F. A fast algorithm for solving a FLS R-factor block circulant linear system is presented, and extension is made to solve a FLS R-factor block retrocirculant linear system by using the relationship between a FLS R-factor block circulant matrix and a FLS R-factor block retrocirculant matrix. Sufficient and necessary conditions of existence of the unique solution of the inverse problem of A
X
=
b in the class of a FLS R-factor block circulant (retrocirculant) matrices over field F are presented. Fast algorithms for solving the unique solution of the inverse problem of A
X
=
b in the class of a FLS R-factor block circulant (retrocirculant) matrices over F are given by using the right largest common factor of the matrix polynomial.



---

*Source: 340803-2014-06-17.xml*