On The Pfaffians and Determinants of Some Skew-Centrosymmetric Matrices

Fatih Yılmaz Polatlı Art and Science Faculty

Gazi University 06500 Teknikokullar / Ankara

Turkey

  fatihyilmaz@gazi.edu.tr

Tomohiro Sogabe Graduate School of Engineering

Nagoya University Furo-cho, Chikusa-ku Nagoya, 464-8601 Japan

sogabe@na.cse.nagoya-u.ac.jp

Emrullah Kırklar Polatlı Art and Science Faculty

Gazi University 06500 Teknikokullar / Ankara

Turkey

   e.kirklar@gazi.edu.tr

Abstract

This paper shows that the Pfaffians and determinants of some skew centrosymmetric matrices can be computed by a paired two-term recurrence relation, or a general number sequence of second order. As a result, the complexities of the formulas are of order n. Furthermore, the formulas have no divisions at all, i.e., they fall into the class of breakdown-free algorithms.

1 Introduction

The determinant is one of the basic parameters in matrix theory. The determinant of a square matrix A = (a_{i,j}) ∈ ℂ^{n×n} is defined as

det(A) = ∑_{σ∈S_{n}}sgn(σ)∏^{n} ; i=1a_{i,σ(i)},

where the symbol S_{n} denotes the group of permutations of sets with n elements and the symbol sgn(σ) denotes the signature of σ ∈ S_{n}.

The Pfaffian of a skew-symmetric matrix A = (a_{i,j}) ∈ ℂ^{2k×2k} is defined by

Pf(A) = \frac{1}{2^{k}k!} ∑_{σ∈S_{2k}}sgn(σ)∏^{k} ; i=1a_{σ(2i−1),σ(2i)},  (1)

and is closely related to the determinant. In fact, Cayley’s theorem states that the square of the Pfaffian of a matrix is equal to the determinant of the matrix, i.e.,

det(A) = Pf(A)^{2}.

Matrix A is called a centrosymmetric matrix if A = JAJ^{−1}, where J is the anti-diagonal matrix whose anti-diagonal elements are one with all others being zero. If A = −JAJ^{−1}, the matrix is said to be skew-centrosymmetric. Skew-centrosymmetric matrices arise in many fields of science including numerical solutions of certain differential equations, digital signal processing, information theory, statistics, linear systems theory, and some Markov processes [1, 2, 3, 4, 5, 6].

In general, the complexities of the Pfaffian and the determinant are of the order O(n^{3}). This paper describes efficient computational formulas for the Pfaffians and determinants of special matrices for which the complexities of the formulas are of the order O(n). The formulas have no divisions at all, i.e., the formulas fall into the class of breakdown-free algorithms.

2 Pfaffians of skew-centrosymmetric matrices

Definition 1. A_{n} = (a_{i,j}) and B_{n} = (b_{i,j}) denote n-by-n matrices with the following elements:

a_{i,j} = \begin{cases}a, & if j = i + 1; \\ −a, & if i = j + 1; \\ 0, & otherwise, \end{cases}

b_{i,j} = \begin{cases}(−1)^{i+1}b, & if i + j = n + 1; \\ 0, & otherwise, \end{cases}

where 1 ≤ i, j ≤ n. Definition 2. F_{n} and G_{n} denote 2-by-2 block matrices of the following form:

F_{n} = ( \begin{matrix}A_{k} & B_{k} \\ (−1)^{k}B_{k} & A_{k} \end{matrix} ) , G_{n} = ( \begin{matrix}A_{k} & −B_{k} \\ (−1)^{k+1}B_{k} & A_{k} \end{matrix} ) ,

where n = 2k.

For example, if n = 10, it follows from Definition 2 that

F_{10} = ( \begin{matrix}A_{5} & B_{5} \\ (−1)^{5}B_{5} & A_{5} \end{matrix} )

= ( \begin{matrix}0 & a & 0 & 0 & 0 & 0 & 0 & 0 & 0 & b \\ −a & 0 & a & 0 & 0 & 0 & 0 & 0 & −b & 0 \\ 0 & −a & 0 & a & 0 & 0 & 0 & b & 0 & 0 \\ 0 & 0 & −a & 0 & a & 0 & −b & 0 & 0 & 0 \\ 0 & 0 & 0 & −a & 0 & b & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & −b & 0 & a & 0 & 0 & 0 \\ 0 & 0 & 0 & b & 0 & −a & 0 & a & 0 & 0 \\ 0 & 0 & −b & 0 & 0 & 0 & −a & 0 & a & 0 \\ 0 & b & 0 & 0 & 0 & 0 & 0 & −a & 0 & a \\ −b & 0 & 0 & 0 & 0 & 0 & 0 & 0 & −a & 0 \end{matrix} ) .

We now describe algorithms for computing the Pfaffians of F_{n} and G_{n}. Theorem 3. Let {f_{n}} and {g_{n}} be the recursively defined sequences below:

f_{n} = bg_{n−1} + a^{2}f_{n−2} for f_{1} = b,

g_{n} = −bf_{n−1} + a^{2}g_{n−2} for g_{1} = −b.

Then, for n = 2k, we obtain

f_{k} = Pf(F_{n}) and g_{k} = Pf(G_{n}),

where f_{−1} = 0, f_{0} = 1 and g_{−1} = 0, g_{0} = 1. Proof. The proof is done by induction on k. For k = 1,

F_{2} = ( \begin{matrix}A_{1} & B_{1} \\ −B_{1} & A_{1} \end{matrix} ) = ( \begin{matrix}0 & b \\ −b & 0 \end{matrix} ) and G_{2} = ( \begin{matrix}A_{1} & −B_{1} \\ B_{1} & A_{1} \end{matrix} ) = ( \begin{matrix}0 & −b \\ b & 0 \end{matrix} ) .

The definition of the Pfaffian in (1) clearly indicates that Pf(F_{2}) = b and Pf(G_{2}) = −b. Thus, f_{1} = b = Pf(F_{2}), g_{1} = −b = Pf(G_{2}).

Let us assume that the recurrence relations hold for all t ≤ k. Then we show that they hold for k = t + 1.

F_{2t+2} = ( \begin{matrix}A_{t+1} & B_{t+1} \\ (−1)^{t+1}B_{t+1} & A_{t+1} \end{matrix} )

= ( \begin{matrix}0 & a & 0 & ⋯ & 0 & b \\ −a & & & & & 0 \\ 0 & & A_{t} & −B_{t} & & ⋮ \\ ⋮ & & (−1)^{t+1}B_{t} & A_{t} & & 0 \\ 0 & & & & & a \\ −b & 0 & ⋯ & 0 & −a & 0 \end{matrix} ) .  (2)

From the expansion formula along with 2t + 2 column of (2), it follows that

Pf(F_{2t+2}) = bPf(G_{2t}) + aPf(M_{2t}) = bg_{t} + aPf(M_{2t}),  (3)

where

M_{2t} = ( \begin{matrix}0 & a & 0 & ⋯ & ⋯ & 0 \\ −a & 0 & a & 0 & ⋯ & 0 \\ 0 & a \\ ⋮ & 0 & & A_{t−1} & B_{t−1} \\ ⋮ & ⋮ & & (−1)^{t−1}B_{t−1} & A_{t−1} \\ 0 & 0 \end{matrix} ) .  (4)

From the expansion formula along with the first row of (4), it follows that

Pf(M_{2t}) = aPf(F_{2t−2}) = af_{t−1}.  (5)

From (3) and (5), we have

f_{t+1} = bg_{t} + a^{2}f_{t−1}.

The recurrence relation for g_{t+1} can be obtained similarly.

Corollary 4. f_{n} = (−1)^{n−1}bf_{n−1} + a^{2}f_{n−2} with f_{−1} = 0 and f_{1} = 1.

Corollary 4 shows that the computational costs of Pf(F_{n}) and det(F_{n})(= Pf(F_{n})^{2}) are of the order O(n). Furthermore, the recurrences in Corollary 4 have no divisions. Thus, no breakdown occurs during the computation.

3 Determinant of the skew-centrosymmetric matrix

In this section, we consider the determinant of the matrix F_{n} with n = 2k. It is well known from [3] that the determinant of the 2-by-2 block matrix holds

| \begin{matrix}A & B \\ C & D \end{matrix} | = det(AD − CB)

if AC = CA. Applying the above formula to F_{n} in Definition 2, the determinant of matrix F_{n} equals that of T_{k} := A_{k}^{2} − (−1)^{k}B_{k}^{2}. Thus, we have

|F_{n}| = |T_{k}| = det ( \begin{matrix}−a^{2} + b^{2} & 0 & a^{2} \\ 0 & −2a^{2} + b^{2} & 0 & ... \\ a^{2} & 0 & ... & ... & a^{2} \\ & ... & ... & −2a^{2} + b^{2} & 0 \\ & & a^{2} & 0 & −a^{2} + b^{2} \end{matrix} )_{k×k} .

The matrix T_{k} belongs to the set of k-tridiagonal matrices. Sogabe and El-Mikkawy [8] considered a fast block diagonalization of k-tridiagonal matrices using permutation matrices. Exploiting the block diagonalization method, we can rearrange the matrix T_{k} as below.

(i) We consider the case where k is odd. Let us define the following matrices:

H_{\frac{k−1}{2}} = (h_{i,j}) = \begin{cases}−2a^{2} + b^{2}, & if i = j; \\ a^{2}, & if i = j + 1 or j = i + 1; \\ 0, & otherwise \end{cases}

and

K_{\frac{k+1}{2}} = (k_{i,j}) = \begin{cases}−a^{2} + b^{2}, & if i = j = 1 or i = j = \frac{k+1}{2}; \\ −2a^{2} + b^{2}, & if i = j = 2 … \frac{k−1}{2}; \\ a^{2}, & if i = j + 1 or j = i + 1; \\ 0, & otherwise. \end{cases}

Then,

P^{T} T_{k}P = ( \begin{matrix}H_{\frac{k−1}{2}} & 0 \\ 0 & K_{\frac{k+1}{2}} \end{matrix} ) ,

where the permutation matrix P is determined by using the method in [8]. Obviously,

det(P^{T} T_{k}P) = det T_{k} = det F_{n} = det(H_{\frac{k−1}{2}} ) det(K_{\frac{k+1}{2}} ).

(ii) We consider the case where k is even. Let us define

N_{\frac{k}{2}} = (n_{i,j}) = \begin{cases}−a^{2} + b^{2}, & if i = j = \frac{k}{2}; \\ −2a^{2} + b^{2}, & if i = j = 1 … \frac{k}{2} − 1; \\ a^{2}, & if i = j + 1 or j = i + 1; \\ 0, & otherwise \end{cases}

and

Q_{\frac{k}{2}} = (q_{i,j}) = \begin{cases}−a^{2} + b^{2}, & if i = j = 1; \\ −2a^{2} + b^{2}, & if i = j = 2 … \frac{k}{2}; \\ a^{2}, & if i = j + 1 or j = i + 1; \\ 0, & otherwise. \end{cases}

Then,

P^{T} T_{k}P = ( \begin{matrix}N_{\frac{k}{2}} & 0 \\ 0 & Q_{\frac{k}{2}} \end{matrix} ) .

Obviously,

det(P^{T} T_{k}P) = det T_{k} = det F_{n} = det(N_{\frac{k}{2}} ) det(Q_{\frac{k}{2}} ).

It can be seen that det(N_{\frac{k}{2}} ) = det(Q_{\frac{k}{2}} ).

El-Mikkawy [9] obtained two-term recurrence relation for the determinants of tridiagonal matrices, i.e.,

v_{i} = | \begin{matrix}d_{1} & a_{1} & 0 & … & 0 \\ b_{2} & d_{2} & a_{2} & ... & ⋮ \\ 0 & b_{3} & d_{3} & ... & 0 \\ ⋮ & ... & ... & ... & a_{i−1} \\ 0 & … & 0 & b_{i} & d_{i} \end{matrix} | ,

where v_{i} = d_{i}v_{i−1} − b_{i}a_{i−1}v_{i−2} for v_{0} = 1 and v_{−1} = 0. Using this relation and the Laplace expansion, we obtain the result. If k is even, then

det(N_{\frac{k}{2}} ) = det(Q_{\frac{k}{2}} ) = (−a^{2} + b^{2})w_{\frac{k}{2} −1} − a^{4}w_{\frac{k}{2} −2}.

If k is odd, then

det(K_{\frac{k+1}{2}} ) = (−a^{2} + b^{2})^{2} w_{\frac{k−3}{2}} − 2a^{4}(−a^{2} + b^{2})w_{\frac{k−5}{2}} + a^{8}w_{\frac{k−7}{2}} ,
det(H_{\frac{k−1}{2}} ) = w_{\frac{k−1}{2}} ,

where

w_{i} = | \begin{matrix}−2a^{2} + b^{2} & a^{2} & … & 0 \\ a^{2} & −2a^{2} + b^{2} & ... & ⋮ \\ ⋮ & ... & ... & a^{2} \\ 0 & … & a^{2} & −2a^{2} + b^{2} \end{matrix} | .

Here w_{i} = (−2a^{2} + b^{2})w_{i−1} − a^{4}w_{i−2} for w_{0} = 1 and w_{−1} = 0 .

Consequently, for n = 2k, we obtain (i) If k is odd,

det F_{n} = det T_{k}

= w_{\frac{k−1}{2}} ((−a^{2} + b^{2})^{2} w_{\frac{k−3}{2}} − 2a^{4}(−a^{2} + b^{2})w_{\frac{k−5}{2}} + a^{8}w_{\frac{k−7}{2}} ) .

(ii) If k is even, det F_{n} = det T_{k} = ((−a^{2} + b^{2})w_{\frac{k}{2} −1} − a^{4}w_{\frac{k}{2} −2})^{2} .

4 Examples

Some examples of the Pfaffian and the determinant of the matrix F_{n} (n = 2k) are shown in the following tables. Here F_{n}, P_{n}, and J_{n} are the nth Fibonacci, Pell, and Jacobsthal numbers, respectively.

a = i, b = 1 a = i, b = 2 a = i\sqrt{2}, b = 1
k  Pf(F_{2k})  Pf(F_{2k})  Pf(F_{2k})
1  F_{2} = 1  P_{2} = 2  J_{2} = 1
2  −F_{3} = −2 −P_{3} = −5 −J_{3} = −3
3  −F_{4} = −3 −P_{4} = −12 −J_{4} = −5
4  F_{5} = 5  P_{5} = 29  J_{5} = 11
5  F_{6} = 8  P_{6} = 70  J_{6} = 21
6  −F_{7} = −13 −P_{7} = −169 −J_{7} = −43
7  −F_{8} = −21 −P_{8} = −408 −J_{8} = −85
8  F_{9} = 34  P_{9} = 985  J_{9} = 171
⋮  ⋮  ⋮  ⋮
≡ 0, 1 (mod 4) F_{k+1}  P_{k+1}  J_{k+1}
≡ 2, 3 (mod 4) −F_{k+1}  −P_{k+1}  −J_{k+1}

Examples of the Pfaffians

a = i, b = 1 a = i, b = 2 a = i\sqrt{2}, b = 1
k det (F_{2k})  det (F_{2k})  det (F_{2k})
1  F_{2}^{2}  P_{2}^{2}  J_{2}^{2}
2  F_{3}^{2}  P_{3}^{2}  J_{3}^{2}
3  F_{4}^{2}  P_{4}^{2}  J_{4}^{2}
4  F_{5}^{2}  P_{5}^{2}  J_{5}^{2}
5  F_{6}^{2}  P_{6}^{2}  J_{6}^{2}
6  F_{7}^{2}  P_{7}^{2}  J_{7}^{2}
7  F_{8}^{2}  P_{8}^{2}  J_{8}^{2}
8  F_{9}^{2}  P_{9}^{2}  J_{9}^{2}
⋮  ⋮  ⋮  ⋮
t  F_{t+1}^{2}  P_{t+1}^{2}  J_{t+1}^{2}

Examples of the determinants

5 Acknowledgment

This work has been supported in part by JSPS KAKENHI (Grant No. 26286088).

The authors sincerely appreciate the referee’s comments that enhanced the quality of the manuscript.

References

[1] A. L. Andrew, Centrosymmetric matrices, SIAM Rev. 40 (1988), 697–698.

[2] A. L. Andrew, Eigenvectors of certain matrices, Lin. Alg. Appl. 7 (1973), 151–162.

[3] F. Zhang, Matrix Theory: Basic Results and Techniques, Springer, 1999.

[4] L. Datta and S. Morgera, On the reducibility of centrosymmetric matrices- applications in engineering problems, Circ. Syst. Signal. Pr. 8 (1989), 71–96.

[5] M. El-Mikkawy and F. Atlan, On solving centrosymmetric linear systems, Appl. Math. 4 (2013), 21–32.

[6] J. Weaver, Centrosymmetric (cross-symmetric) matrices, their basic properties, eigenvalues, and eigenvectors, Amer. Math. Monthly 92 (1985), 711–717.

[7] R. Vein and P. Dale, Determinants and Their Applications in Mathematical Physics, Springer, 1999.

[8] T. Sogabe and M. El-Mikkawy, Fast block diagonalization of k-tridiagonal matrices, Appl. Math. Comput. 218 (2011), 2740–2743.

[9] M. El-Mikkawy, A note on a three-term recurrence for a tridiagonal matrix, Appl. Math. Comput. 139 (2003), 503–511.

2010 Mathematics Subject Classification: Primary 15A15; Secondary 15A23. Keywords: Pfaffian, determinant, skew-centrosymmetric matrix.

(Concerned with sequences \underline{A000045}, \underline{A000129}, \underline{A001045}.)

Received June 20 2016; revised versions received July 8 2016; January 18 2017; February 2 2017. Published in Journal of Integer Sequences, February 11 2017.

Return to Journal of Integer Sequences home page.