ALGORITHMS FOR CENTROSYMMETRIC AND SKEW-CENTROSYMMETRIC MATRICES

Iyad T. Abu-Jeib

Abstract. We present a simple algorithm that reduces the time complexity of solving the linear system Gx = b, where G is a centrosymmetric/skew-centrosymmetric matrix. We also reduce the time complexity of solving some complex linear systems. We propose efficient methods for multiplying centrosymmetric/skew-centrosymmetric matrices.

1. Introduction. Melman [7] proposed an efficient algorithm for computing the product Gv, where G is a symmetric centrosymmetric matrix and v is a vector. In this paper, we present a simple efficient algorithm for solving Gx = b, where G is a centrosymmetric/skew-centrosymmetric matrix and b is a vector. In our algorithm G does not have to be symmetric or skew-symmetric. Some complex linear systems can be converted to real systems and then solved by using our algorithm. Finally, we propose efficient methods for finding the product MN, where M and N are n × n matrices and at least one of them is centrosymmetric or skew-centrosymmetric.

We employ the following notation. We denote the transpose of a matrix A by A^{T}. We use the notation ⌊x⌋ for the largest integer less than or equal to x. As usual, I denotes the identity matrix. Throughout this paper we let δ = ⌊\frac{n}{2}⌋. By the main counterdiagonal (or simply counterdiagonal) of a square matrix we mean the positions which proceed diagonally from the last entry in the first row to the first entry in the last row. We mean by the time complexity the number of flops. When counting flops, we treat addition/subtraction the same as multiplication/division.

\underline{Definition 1.1}. The counteridentity matrix, denoted J, is the square matrix whose elements are all equal to zero except those on the counterdiagonal, which are all equal to 1.

Multiplying a matrix A by J from the left results in reversing the rows of A and multiplying A by J from the right results in reversing the columns of A. Throughout this paper J is used to denote the counteridentity matrix.

There are various kinds of symmetries that we will use in this paper. For convenience, we summarize them in the following definition.

\underline{Definition 1.2}. Let A be an n × n matrix.

(1) A is persymmetric if JAJ = A^{T}.

(2) A is centrosymmetric if JAJ = A.

(3) A is skew-centrosymmetric if JAJ = −A.

Centrosymmetric and skew-centrosymmetric matrices arise in many fields including communication theory, statistics, physics, harmonic differential quadrature, differential equations, numerical analysis, engineering, sinc methods, magic squares, and pattern recognition. For applications of these matrices, see [1, 3, 4, 5, 6, 8]. Note that symmetric Toeplitz matrices are symmetric centrosymmetric, and skew-symmetric Toeplitz matrices are skew-symmetric skew-centrosymmetric.

Now we state the following two theorems that can be proved easily. The second theorem can be found in [2].

\underline{Theorem 1.3}. Let S be an n × n skew-centrosymmetric matrix. If n is even, then S can be written as

S = [ \begin{matrix}A & −JCJ \\ C & −JAJ \end{matrix} ] ,

where A, J and C are δ × δ. If, in addition, S is skew-symmetric, then A is skew-symmetric and C is persymmetric. If n is odd, then S can be written as

S = [ \begin{matrix}A & z & −JCJ \\ y & 0 & −yJ \\ C & −Jz & −JAJ \end{matrix} ] ,

where A, J, and C are δ×δ, z is δ×1, and y is 1×δ. If, in addition, S is skewsymmetric, then y = −z^{T}, A is skew-symmetric, and C is persymmetric.

\underline{Theorem 1.4}. Let H be an n × n centrosymmetric matrix. If n is even, then H can be written as

H = [ \begin{matrix}A & JCJ \\ C & JAJ \end{matrix} ] ,

where A, J, and C are δ × δ. If, in addition, H is symmetric, then A is symmetric and C is persymmetric. If n is odd, then H can be written as

[ \begin{matrix}A & z & JCJ \\ y^{T} & q & y^{T} J \\ C & Jz & JAJ \end{matrix} ] ,

where A, J, and C are δ × δ, z and y are δ × 1, and q is a scalar. If, in addition, H is symmetric, then y = z, A is symmetric, and C is persymmetric.

2. Algorithms. We present simple efficient algorithms for solving Gx = b, where G is centrosymmetric/skew-centrosymmetric and x and b are vectors. We do that by transforming the problem to solving two linear systems “half” the size of the original one. First, we handle centrosymmetric matrices of even order, then centrosymmetric matrices of odd order, then skew-centrosymmetric matrices, then other matrices such as Hermitian persymmetric matrices.

\underline{2.1 Centrosymmetric Matrices of Even Order}. Let H be an n × n centrosymmetric matrix, where n is even, let x and b be n × 1 vectors, let H be decomposed as in Theorem 1.4, and let

Q_{1} = \frac{1}{\sqrt{2}} [ \begin{matrix}I & I \\ −J & J \end{matrix} ] ,

where I and J are δ × δ. Then, Q_{1}^{T} HQ_{1} = D_{1}, where

D_{1} = [ \begin{matrix}L & 0 \\ 0 & M_{1} \end{matrix} ] ,

where L = A − JC and M_{1} = A + JC. Now let

x = [ \begin{matrix}x_{1} \\ x_{2} \end{matrix} ] and b = [ \begin{matrix}b_{1} \\ b_{2} \end{matrix} ] ,

where x_{1}, x_{2}, b_{1}, b_{2} are δ × 1. Thus, Hx = b if and only if D_{1}Q_{1}^{T} x = Q_{1}^{T} b if and only if

[ \begin{matrix}L & 0 \\ 0 & M_{1} \end{matrix} ] [ \begin{matrix}x_{1} − Jx_{2} \\ x_{1} + Jx_{2} \end{matrix} ] = [ \begin{matrix}b_{1} − Jb_{2} \\ b_{1} + Jb_{2} \end{matrix} ] .

The last equation can be simplified to

[ \begin{matrix}Lx_{1}′ \\ M_{1}x_{2}′ \end{matrix} ] = [ \begin{matrix}b_{1} & ′ \\ b_{2} & ′ \end{matrix} ] ,

where x_{1}′ = x_{1} − Jx_{2}, x_{2}′ = x_{1} + Jx_{2}, b_{1}′ = b_{1} − Jb_{2}, and b_{2}′ = b_{1} + Jb_{2}. Thus, to solve Hx = b for x:

(1) Find L, M_{1}, b_{1}′, and b_{2}′.

(2) Solve the two systems Lx_{1}′ = b_{1}′ and M_{1}x_{2}′ = b_{2}′ for x′_{1} and x′_{2}.

(3) Obtain the solution

x = [ \begin{matrix}x_{1} \\ x_{2} \end{matrix} ]

of the original system from x_{1}′ and x_{2}′ as follows:

x_{1} = \frac{1}{2} (x_{1}′ + x_{2}′) , x_{2} = \frac{1}{2}J (x_{2}′ − x_{1}′) .

Note that the time complexity of the first step of the algorithm is \frac{1}{2}n^{2}+ O(n) (\frac{1}{2}n^{2}+n additions/subtractions and no multiplications/divisions) and the time complexity of the third step is O(n) (n additions/subtractions and n multiplications). The time complexity of the second step depends on the method used to solve the systems. The second step is the step that leads to the reduction of the time complexity, because instead of solving a linear system of n equations, we end up solving two linear systems half the size of the original one. For example, if the original system is solved with Gaussian elimination, then the time complexity will be \frac{2}{3}n^{3}+O(n^{2}). But, if Gaussian elimination is used to solve the two systems in the second step, then the time complexity of our algorithm will be \frac{1}{6}n^{3} +O(n^{2}), which is a significant reduction. If a method more efficient than Gaussian elimination is used, then the time complexity of our algorithm will be less. If, in addition, H is symmetric or skew-symmetric or Toeplitz, then the time complexity of our algorithm will reduce further.

\underline{2.2 Centrosymmetric Matrices of Odd Order}. Let H be an n × n centrosymmetric matrix, where n is odd, let x and b be n × 1 vectors, let H be decomposed as in Theorem 1.4, and let

Q_{2} = \frac{1}{\sqrt{2}} [ \begin{matrix}I & 0 & I \\ 0 & \sqrt{2} & 0 \\ −J & 0 & J \end{matrix} ] ,

where I and J are δ × δ. Then, Q_{2}^{T} HQ_{2} = D_{2}, where

D_{2} = [ \begin{matrix}L & 0 \\ 0 & M_{2} \end{matrix} ] ,

where L = A − JC and

M_{2} = [ \begin{matrix}q & \sqrt{2}y^{T} \\ \sqrt{2}z & A + JC \end{matrix} ] .

Now let

x = [ \begin{matrix}x_{1} \\ α \\ x_{2} \end{matrix} ] and b = [ \begin{matrix}b_{1} \\ β \\ b_{2} \end{matrix} ] ,

where x_{1}, x_{2}, b_{1}, b_{2} are δ × 1 and α and β are numbers. Then Hx = b if and only if D_{2}Q_{2}^{T} x = Q_{2}^{T} b if and only if

[ \begin{matrix}Lx_{1}′ \\ M_{2}x_{3} \end{matrix} ] = [ \begin{matrix}b_{1} & ′ \\ b_{3} \end{matrix} ] ,

where x_{1}′ = x_{1} − Jx_{2}, b_{1}′ = b_{1} − Jb_{2},

x_{3} = [ \begin{matrix}\sqrt{2}α \\ x_{2} & ′ \end{matrix} ], b_{3} = [ \begin{matrix}\sqrt{2}β \\ b_{1} + Jb_{2} \end{matrix} ] ,

and x_{2}′ = x_{1} + Jx_{2}.

Thus, to solve Hx = b for x:

(1) Find L, M_{2}, b_{1}′, and b_{3}.

(2) Solve the two systems Lx_{1}′ = b_{1}′ and M_{2}x_{3} = b_{3} for x′_{1} and x_{3}.

(3) Let

x_{3} = [ \begin{matrix}γ \\ x_{2} & ′ \end{matrix} ] ,

where x_{2}′ is δ × 1. Obtain the solution

x = [ \begin{matrix}x_{1} \\ α \\ x_{2} \end{matrix} ]

of the original system from x_{1}′ and x_{3} as follows:

x_{1} = \frac{1}{2} (x_{1}′ + x_{2}′) , α = \frac{1}{\sqrt{2}}γ, x_{2} = \frac{1}{2}J (x_{2}′ − x_{1}′) .

Note that the time complexity of the first step of the algorithm is \frac{1}{2}n^{2} + O(n) and the time complexity of the third step is O(n). The time complexity of the second step depends on the method used to solve the systems. (See the last paragraph of the last subsection.)

\underline{2.3 Skew-centrosymmetric Matrices}. The algorithm for skewcentrosymmetric matrices of even order can be derived in a similar way to the algorithm for centrosymmetric matrices of even order, but here we use the decomposition described in Theorem 1.3. Another way to do it is as follows. Let S be an n × n skew-centrosymmetric matrix, where n is even, let b be an n × 1 vector, let m = \frac{n}{2}, and let

E = [ \begin{matrix}−I & 0 \\ 0 & I \end{matrix} ] ,

where I is the m × m identity matrix. It is easy to see H = ES is centrosymmetric. Thus, to solve Sx = b for x, solve Hx = Eb by the algorithm of Subsection 2.1.

\underline{2.4 Complex Systems}. Let R = H + iS, where H is an n × n real centrosymmetric matrix and S is an n × n real skew-centrosymmetric matrix. Let X = X_{1} + iX_{2} and B = B_{1} + iB_{2}, where X_{1}, X_{2}, B_{1}, and B_{2}, are n × 1 real vectors. Then, RX = B if and only if

[ \begin{matrix}H & −S \\ S & H \end{matrix} ] [ \begin{matrix}X_{1} \\ X_{2} \end{matrix} ] = [ \begin{matrix}B_{1} \\ B_{2} \end{matrix} ] .

Note that the above system can be written as

[ \begin{matrix}H & JSJ \\ S & JHJ \end{matrix} ] [ \begin{matrix}X_{1} \\ X_{2} \end{matrix} ] = [ \begin{matrix}B_{1} \\ B_{2} \end{matrix} ] .

Now we can use the algorithm of Subsection 2.1 to solve this system, which leads to a reduction in the time complexity. Thus, instead of solving the complex system RX = B, we can solve the two real systems (H −JS)X′_{1} = B′_{1} and (H +JS)X′_{2} = B′_{2}, where B′_{1} = B_{1} −JB_{2} and B′_{2} = B_{1} +JB_{2}. The solution of the complex system is \frac{1}{2}(X′_{1} +X′_{2})+ \frac{1}{2}iJ(X′_{2} −X′_{1}). For example, if R is an n × n Hermitian persymmetric matrix, then R = H + iS, where H is an n × n real symmetric centrosymmetric matrix and S is an n × n real skew-symmetric skew-centrosymmetric matrix. Hence, we can use the idea described above to solve the complex system RX = B.

3. Multiplication of Matrices. Let M and N be n × n matrices and let at least one of them be centrosymmetric/skew-centrosymmetric. To reduce the time complexity of finding the product MN, we use similar ideas to those we used in the previous section. For example, if M is centrosymmetric of even order, then we replace M by Q_{1}D_{1}Q_{1}^{T} (see Subsection 2.1). If the standard multiplication algorithm is used, then the reduction in time complexity that results from using this idea is as follows:

(1) About 75% if both matrices are centrosymmetric/skew-centrosymmetric (or one is centrosymmetric and the other is skew-centrosymmetric). Here, instead of multiplying two n × n matrices, we end up multiplying two matrices “half” the size.

(2) About 50% if one of the matrices is arbitrary and the other is centrosymmetric/skew-centrosymmetric. Here, instead of multiplying two n × n matrices, we end up multiplying four matrices “half” the size. Note that a more efficient algorithm like Strassen’s algorithm or Cop-

persmith and Winograd’s algorithm can be used to multiply the matrices “half” the size mentioned above instead of using the standard multiplication algorithm.

\underline{References}

1. A. L. Andrew, “Centrosymmetric Matrices,” SIAM Rev., 40 (1998), 697–698.

2. A. Cantoni and P. Butler, “Eigenvalues and Eigenvectors of Symmetric Centrosymmetric Matrices,” Linear Algebra Appl., 13 (1976), 275–288.

3. A. Cantoni and P. Butler, “Properties of the Eigenvectors of Persymmetric Matrices With Applications to Communication Theory,” IEEE Trans. Comm., COM-24 No. 8 (1976), 804–809.

4. L. Datta and S. Morgera, “On the Reducibility of Centrosymmetric Matrices - Applications in Engineering Problems,” Circuits Systems Signal Process, 8 (1989), 71–96.

5. I. J. Good, “The Inverse of a Centrosymmetric Matrix,” Technometrics, 12 (1970), 925–928.

6. R. B. Mattingly, “Even Order Regular Magic Squares Are Singular,” Amer. Math. Monthly, 107 (2000), 777–782.

7. A. Melman, “Symmetric Centrosymmetric Matrix-Vector Multiplication,” Linear Algebra Appl., 320 (2000), 193–198.

8. F. Stenger, “Matrices of Sinc Methods,” J. Comput. Appl. Math., 86 (1997), 297–310.

Mathematics Subject Classification (2000): 65F05

Iyad T. Abu-Jeib Department of Computer Science and Information Systems SUNY Fredonia Fredonia, NY 14063 email: abu-jeib@cs.fredonia.edu