ON THE COUNTERIDENTITY MATRIX

Iyad T. Abu–Jeib

Abstract. We make a comparison between the identity matrix and the counteridentity matrix by studying the eigensystem of J + M, where J is the counteridentity matrix and M is a structured matrix, with the goal of expressing this system entirely in terms of the corresponding eigensystem of M. Also, properties of some parametric families of the form J + ρM are studied.

1. Introduction. Properties of the sum of two matrices have been studied by many mathematicians in many contexts with the objective of finding connections between the eigensystem of the summands and the eigensystem of the sum. In particular, the eigenvalues of the sum of the identity matrix and another matrix is one of the first sums that one encounters in elementary linear algebra. A very useful relative of the identity is the counteridentity J, which is obtained from the identity by reversing the order of its columns. The question we pose is: how closely is the eigensystem of the sum J + M related to that of the matrix M? With no restrictions on M, it appears that little can be said about the connections between these eigensystems. However, we show that if M is centrosymmetric, skew–centrosymmetric, or diagonal, then the question has a simple explicit answer. One consequence of our analysis is the construction of an analytic homotopy H(t), 0 ≤ t ≤ 1, in the space of diagonalizable matrices, between J = H(0) and any real skew–symmetric skew–centrosymmetric matrix S = H(1) such that H(t) has only real or pure imaginary eigenvalues for 0 ≤ t ≤ 1.

We begin with a discussion of the counteridentity matrix. By the main 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. The main counterdiagonal is sometimes called the secondary diagonal or the main anti–diagonal. We will simply say counterdiagonal when we refer to the main counterdiagonal.

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

The counteridentity is sometimes called the exchange matrix or the anti– identity matrix or the contra–identity matrix or the flip matrix.

We denote the transpose of a matrix A by A^{T}, the Hermitian/conjugate transpose of A by A^{H}, and the flip–transpose (reflection of the entries about the counterdiagonal) by A^{F}. As usual, I denotes the identity matrix. Recall that a matrix A is persymmetric if A^{F} = A, centrosymmetric if JAJ = A, and skew–centrosymmetric if JAJ = −A. A matrix A is doubly skew if it is skew–symmetric and skew– centrosymmetric. Thus, a matrix is symmetric persymmetric (such a matrix is sometimes called doubly symmetric) if and only if it is symmetric centrosymmetric. Similarly, a matrix is skew–symmetric persymmetric if and only if it is doubly skew. We note that Toeplitz matrices are persymmetric. Hence, symmetric Toeplitz matrices are symmetric centrosymmetric and skew–symmetric Toeplitz matrices are doubly skew.

A vector x is called symmetric if Jx = x and skew–symmetric if Jx = −x. We will denote the set of all n×1 vectors that are either symmetric or skew–symmetric by E.

Recall that the sum of the eigenvalues of a matrix A is equal to the trace of A, denoted tr(A). We employ the notation ⌈x⌉ for the smallest integer greater than or equal to x and ⌊x⌋ for the largest integer less than or equal to x. We will denote the diagonal matrix whose diagonal elements are d_{1}, d_{2}, …, d_{n} by diag(d_{1}, d_{2}, …, d_{n}).

Here are some simple and easily verified properties of the counteridentity matrix. We assume that all matrices in the first five parts are n × n.

1. J = [δ_{i,n−i+1}], where δ_{i,j} is the Kronecker delta.

2. J^{T} = J = J^{−1}.

3. det(J) = 1 if n mod 4 = 0 or 1 and det(J) = −1 if n mod 4 = 2 or 3.

4. A^{F} = JA^{T} J.

5. ⌊\frac{n}{2}⌋ eigenvalues of J are equal to −1 and the remaining eigenvalues are equal to 1.

6. If n is even, then the columns of the matrix

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

where J and I are n/2 by n/2, form n orthonormal eigenvectors of the n × n counteridentity. If n is odd, then the columns of the matrix

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

where J and I are ⌊n/2⌋ by ⌊n/2⌋, form n orthonormal eigenvectors of the n×n counteridentity. We note here that Q_{1} and Q_{2} were used by some researchers to block–diagonalize centrosymmetric matrices and derive results about them. For more information, see [2]. We note that although the definition of Q_{1} stated in [2] is the transpose of Q_{1} as stated here, all proofs in that paper correctly use Q_{1}.

2. Centrosymmetric and Skew–Centrosymmetric Summands. In this section we analyze the relationship between the eigenvalues/eigenvectors of J + S and the eigenvalues/eigenvectors of S, where S is either centrosymmetric or skew– centrosymmetric. (For basic facts about centrosymmetric matrices, see [4, 5].) The proof of the following proposition is straightforward, and hence, it is omitted.

\underline{Proposition 2.1}. Let S be an n × n nonzero centrosymmetric matrix, let γ be the number of linearly independent eigenvectors of S, and let A = J + S. Then (a) A and S share γ linearly independent eigenvectors that belong to E.

(b) If x is symmetric, then (λ, x) is an eigenpair of S if and only if (1 + λ, x) is an eigenpair of A.

(c) If x is skew–symmetric, then (λ, x) is an eigenpair of S if and only if (−1+λ, x) is an eigenpair of A.

Observe that the ±1’s in the preceding proposition are the eigenvalues of the matrix J. If, in addition, S is also real symmetric, then the eigenvalues of S can be ordered as λ_{1}, λ_{2}, … λ_{n} such that the eigenvalues of A are enumerated as

−1 + λ_{1}, −1 + λ_{2}, …, −1 + λ_{⌊n/2⌋}, 1 + λ_{⌊n/2⌋+1}, …, 1 + λ_{n}.

Thus, the eigenvalues of J can be ordered as μ_{1}, μ_{2}, …, μ_{n} in such a way that the eigenvalues of J + S are exactly μ_{j} + λ_{j}, j = 1, …, n, where the λ_{j}’s are the eigenvalues of S. This is the best relationship between the eigenvalues of the summands and the eigenvalues of the sum that we can hope for.

The situation with a skew–centrosymmetric summand S is not so clear as in the centrosymmetric case. Nonetheless, the eigensystem of J + S can be largely determined in terms of S.

\underline{Theorem 2.2}. Let S be an n × n nonzero skew–centrosymmetric matrix and let A = J + S. Then

(a) Every eigenvector of S is an eigenvector of A^{2}.

(b) ±μ is an eigenvalue of S if and only if ±\sqrt{μ^{2} + 1} is an eigenvalue of A.

(c) If, in addition, S is also skew–symmetric, then the eigenvalues of A are either real or pure imaginary, and if A and S share an eigenvector, then S is singular and 1 or −1 is an eigenvalue of A. Moreover, if (λ, x) is an eigenpair of A, then (λ, Jx) is an eigenpair of A^{T}, and if, in addition, S is also nonsingular, then (−λ, Sx) is an eigenpair of A^{T}.

\underline{Proof}.

A^{2} = (S + J)(S + J) = S^{2} + SJ + JS + J^{2} = S^{2} + SJ − SJ + I = S^{2} + I

from which (a) follows. Furthermore, if λ is an eigenvalue of A, then λ^{2} = μ^{2} + 1, for some eigenvalue μ of S. Thus, (b) is proved. Now if S is also skew–symmetric and if λ is an eigenvalue of A, then λ^{2} = 1 + μ^{2}, for some eigenvalue μ = bi of S, where b ∈ ℝ. Thus, λ^{2} = 1 − b^{2} and hence, λ = ±\sqrt{1 − b^{2}}. Therefore, λ is real if and only if |b| ≤ 1 and pure imaginary if and only if |b| > 1. Now suppose that (μ, x) is an eigenpair of S and (λ, x) is an eigenpair of A. Then

λx = Ax = Sx + Jx = μx + Jx.

Hence, Jx = (λ − μ)x. Thus, (λ − μ) is an eigenvalue of J, which implies either λ = μ + 1, or λ = μ − 1. But now λ is either real or pure imaginary, and μ is pure imaginary. This forces μ to be zero and λ to be 1 or −1. Finally, let (λ, x) be an eigenpair of A. Then Sx + Jx = λx, which implies JSx + JJx = λJx. Thus, (−S + J)Jx = λJx, which implies (λ, Jx) is an eigenpair of A^{T}. (Note that Jx ≠ 0 because J is nonsingular.) Now since SSx+SJx = λSx, we have (S −J)Sx = λSx. If S is nonsingular, then Sx ≠ 0, and hence, (λ, Sx) is an eigenpair of −A^{T}.

In the case of the identity matrix, we have that I − S is invertible for any skew–symmetric matrix S. This is the basis for the so–called Cayley transform S → (I−S)^{−1}(I+S) which establishes a one–to–one correspondence between skew– symmetric matrices and orthogonal matrices. Theorem 2.2 shows that a direct analogue is not possible for the counteridentity J, since J − S may be singular. Another application of this theorem is the following.

\underline{Corollary 2.3}. Let S be an n×n nonzero doubly skew matrix and let A = J +S. If, for every eigenvalue μ of S, |μ| < \sqrt{2}, then | det(A)| ≤ 1.

\underline{Proof}. Let \{μ_{j}\}_{j=1}^{n} be the eigenvalues of S, where μ_{j} = r_{j}i, 1 ≤ j ≤ n (r_{j} ∈ ℝ). By Theorem 2.2, the eigenvalues {λ_{j}}_{j=1}^{n} of A^{2} are given by λ_{j} = 1+μ_{j}^{2} = 1−r_{j}^{2}, 1 ≤ j ≤ n. Now since −\sqrt{2} < r_{j} < \sqrt{2}, it follows that −1 < λ_{j} ≤ 1, 1 ≤ j ≤ n. Now recall that the determinant of A^{2} is equal to the product of its eigenvalues, which implies the corollary.

Now let S be doubly skew and let A = J + S. Since S is diagonalizable, then so is A^{2}. It follows that A^{2} has no Jordan blocks of order greater than 1, so the same is true for A. Therefore, A is diagonalizable. Note also that the eigenvalues of A are real or pure imaginary, which enables us to make an interesting homotopy construction.

\underline{Example 2.4}. We construct an analytic homotopy H(t), 0 ≤ t ≤ 1, in the (topological) space of diagonalizable matrices, between J = H(0) and any n × n real doubly skew matrix S = H(1) such that H(t) has only real or pure imaginary eigenvalues for 0 ≤ t ≤ 1. Specifically, define

H(t) = (1 − t)J + tS.

Clearly, H(0) = J and H(1) = S and H(t) is analytic in t. Furthermore, for 0 < t < 1, we have

H(t) = (1 − t) (J + \frac{t}{(1 − t)}S) .

Now \frac{1}{1−t}H(t) is diagonalizable (which implies H(t) is diagonalizable) and by Theorem 2.2 its eigenvalues are real or pure imaginary.

3. Diagonal Summands. In the following theorem and corollaries we examine diagonal updates of the counteridentity matrix. We also examine the eigenvalues of matrices with zeros everywhere except on the main diagonal and the main counterdiagonal and matrices with zeros everywhere except on the main counterdiagonal.

\underline{Theorem 3.1}. Let D_{1} = diag(d_{1}, d_{2}, …, d_{n}) and D_{2} = diag(e_{1}, e_{2}, …, e_{n}) be diagonal matrices, let A = D_{1} + JD_{2}, and let

M = \{\frac{d_{i} + d_{n−i+1} ± \sqrt{(d_{i} + d_{n−i+1})^{2} + 4(e_{i}e_{n−i+1} − d_{i}d_{n−i+1})}}{2}, i = 1, 2, …, ⌊\frac{n}{2}⌋\}.

Then if λ is an eigenvalue of A, then λ ∈ M if n is even, and λ ∈ M ∪\{e_{⌈ \frac{n}{2} ⌉} +d_{⌈ \frac{n}{2} ⌉}\} if n is odd.

\underline{Proof}. Let (λ, x) be an eigenpair of A and let x = [x_{1} x_{2} ⋯ x_{n}]^{T}. We get the equations:

e_{i}x_{n−i+1} = (λ − d_{i})x_{i}, i = 1, 2, …, n.

Notice that if n is even, then we can partition the above system into \frac{n}{2} systems. Each system consists of two equations of two variables x_{i} and x_{n−i+1}. Solving the equations yields the result. If n is odd, then we have a similar situation. The only difference is that we get an additional equation (the middle one) of one variable which is x_{⌈n⌉}.

Note that A in the previous theorem has zeros everywhere except possibly on the main diagonal and the main counterdiagonal.

\underline{Corollary 3.2}. Let D = diag(d_{1}, d_{2}, …, d_{n}) be a diagonal matrix, let A = J + D, and let

M = \{\frac{d_{i} + d_{n+1−i} ± \sqrt{(d_{i} + d_{n+1−i})^{2} − 4(d_{i}d_{n+1−i} − 1)}}{2}, i = 1, 2, …, ⌊\frac{n}{2}⌋\}.

Then if λ is an eigenvalue of A, then λ ∈ M if n is even, and λ ∈ M ∪ \{1 + d_{⌈ \frac{n}{2} ⌉}\} if n is odd.

\underline{Proof}. The proof follows directly from the previous theorem by taking D_{1} = D and D_{2} = I.

\underline{Corollary 3.3}. Let D = diag(d_{1}, d_{2}, …, d_{n}) be a diagonal matrix, let A = JD, and let M = \{±\sqrt{d_{i}d_{n+1−i}}, i = 1, 2, …, ⌊\frac{n}{2}⌋\}. If λ is an eigenvalue of A, then λ ∈ M if n is even, and λ ∈ M ∪ \{d_{⌈ \frac{n}{2} ⌉}\} if n is odd.

\underline{Proof}. The proof follows directly from Theorem 3.1 by taking D_{1} = 0 and D_{2} = D.

Note that A in the previous corollary has zeros everywhere except possibly on the counterdiagonal.

4. Rank One Summands. In this section, we examine rank one updates of the counteridentity. In the case of a general rank one complex matrix of the form uv^{H} very little can be deduced about J + uv^{H}. Indeed, if one perturbs J slightly so that the resulting J̃ has simple eigenvalues, Anderson [3] shows that the sum J̃+ uv^{H} can have arbitrarily prescribed spectrum for suitable vectors u, v. If one specializes to a rank one real matrix ρuu^{T}, where ρ is a real number and u a real vector, then the standard divide–and–conquer algorithm, together with deflation [6] can be used to compute the eigensystem of the sum J + ρuu^{T}, since J is real symmetric. However, if explicit formulas are desired, one more specialization is needed. We consider the case of a nonzero real symmetric vector u. It is harmless to assume that u is a unit vector (u^{T} u = 1) and we do so. Thus, we have a parametric family of matrices H_{ρ} = J + ρuu^{T}.

First, we consider an analogous parametric family P_{ρ} = I + ρuu^{T}. The eigenvalues of the rank one matrix ρuu^{T} are ρ and 0, the latter with multiplicity n − 1, and the corresponding eigenvectors of ρuu^{T} form an orthonormal basis u = u_{1}, u_{2}, …, u_{n}. Thus, one immediately obtains these standard facts:

(a) The eigenvectors of uu^{T} are eigenvectors of P_{ρ}.

(b) n − 1 eigenvalues of P_{ρ} are equal to 1 and the remaining eigenvalue is equal to 1 + ρ.

(c) det(P_{ρ}) = 1 + ρ.

(d) If ρ ≠ −1, then P_{ρ} is nonsingular and P_{ρ}^{−1} = P_{μ}, where μ = \frac{−ρ}{1+ρ}.

In our setting, the analogous facts for the counteridentity turn out to be quite similar.

\underline{Theorem 4.1}. Let ρ be a real number, u an n × 1 unit symmetric real vector and H_{ρ} = J + ρuu^{T}. Then

(a) The eigenvectors of uu^{T} are eigenvectors of H_{ρ}.

(b) If n is odd (respectively, even), then \frac{n−1}{2} (respectively, \frac{n}{2} − 1) eigenvalues of H_{ρ} are equal to 1 and \frac{n−1}{2} (respectively, \frac{n}{2}) eigenvalues are equal to −1. The remaining eigenvalue is 1 + ρ.

(c) det(H_{ρ}) = (1 + ρ) if ⌊\frac{n}{2}⌋ is even and it is equal to −(1 + ρ) if ⌊\frac{n}{2}⌋ is odd.

(d) If ρ ≠ −1, then H_{ρ}^{−1} = H_{σ}, where σ = \frac{−ρ}{1+ρ}.

\underline{Proof}. Let u = u_{1}, u_{2}, …, u_{n} be an orthonormal basis of eigenvectors of uu^{T} corresponding to eigenvalues 1, 0, …, 0, respectively. The vector u_{1} is unique up to sign, and since uu^{T} is real symmetric centrosymmetric, there are ⌈n/2⌉ orthonormal symmetric eigenvectors and ⌊n/2⌋ orthonormal skew–symmetric eigenvectors of uu^{T}. The vector u = u_{1} is given to be symmetric. Therefore, of the remaining eigenvectors, ⌈n/2⌉ − 1 are symmetric and ⌊n/2⌋ are skew–symmetric.

Now note that H_{ρ}u_{1} = (1 + ρ)u_{1}. If u_{j}, j > 1, is a symmetric vector, we also see that H_{ρ}u_{j} = Ju_{j} + ρuu^{T} u_{j} = u_{j}, while if u_{j} is skew–symmetric, then H_{ρ}u_{j} = −u_{j}. Parts (a) and (b) follow from these facts. Part (c) is immediate from (b). To prove (d), note that Juu^{T} = uu^{T} = uu^{T} J and

H_{ρ}H_{σ} = (J + ρuu^{T} ) (J + σuu^{T} )
= J^{2} + ρuu^{T} J + Jσuu^{T} + ρσuu^{T}
= I + (ρ + σ + ρσ)uu^{T} .

One can also prove the previous theorem by considering H_{ρ}^{2} = I +(2ρ+ρ^{2})uu^{T}.

\underline{Remark}. We note that the one parameter family \{P_{ρ} = I + ρuu^{T} | ρ ≠ −1\} forms a topological group. On the other hand, the corresponding one parameter family for the counteridentity {H_{ρ} = J + ρuu^{T} | ρ ≠ −1} has all the trappings of a topological group except that the closure law fails.

For the case when u is skew–symmetric and for more general results about rankone perturbations of centrosymmetric matrices (note that J is centrosymmetric), we refer the reader to [1].

\underline{References}

1. I. Abu-Jeib, “Rank–One Perturbations and Transformations of Centrosymmetric Matrices,” New Zealand J. Math., 33 (2004), 1–10.

2. I. Abu–Jeib, “Centrosymmetric Matrices: Properties and an Alternative Approach,” Can. Appl. Math. Q., 10 (2002), 429–445.

3. J. Anderson, “A Secular Equation for the Eigenvalues of a Diagonal Matrix Perturbation,” Linear Algebra Appl., 246 (1997), 49–70.

4. A. Andrew, “Eigenvectors of Certain Matrices,” Linear Algebra and Appl., 7 (1973), 151–162.

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

6. J. Demmel, Applied Numerical Linear Algebra, SIAM, Philadelphia, 1997.

Iyad T. Abu–Jeib Department of Mathematics and Computer Science Fenton Hall SUNY College at Fredonia Fredonia, NY 14063 email: abu-jeib@cs.fredonia.edu