In  we introduced two special classes of rectangular matrices A and B that have the relations
where P and Q are two generalized reflection matrices of dimensions n and m, respectively. A matrix X is said to be a generalized reflection matrix if , i.e., if X is unitary and Hermitian. The matrices A (and B) are referred to as generalized reflexive (and antireflexive respectively) matrices. They are a generalization of centrosymmetric (anti-centrosymmetric) matrices whose special properties have been under extensive studies  -  and a generalization of reflexive (antireflexive) matrices U (V), exploited in    , that have the relations
where P is some reflection (symmetric signed permutation) matrix.
Like U, the generalized reflexive matrices A arise naturally and frequently from physical problems with some sort of reflexive symmetry. Although the generalized antireflexive matrices B also also possess many interesting properties, in this paper, we shall focus only on generalized reflexive matrices. Our main objective is, thus, to present a generalized simultaneous diagonalization theorem and various decomposition schemes for the matrices A so that linear least-squares problems (or linear systems) whose coefficient matrices are of this class can be solved more efficiently. The decomposition schemes can be applied to a great number of scientific and engineering problems.
The organization of this paper is as follows. In §2, we present a generalization to the classical simultaneous diagonalization of two diagonalizable commuting square matrices. Our generalization, referred to as the generalized simultaneous diagonalization, simultaneously diagonalize a rectangular matrix H and two square matrices F and G that have the relation , assuming F and G are diagonalizable. Based on this simultaneous diagonalization, we develop explicit and semi-explicit decomposed forms in §3 for some important types of generalized reflexive matrices. An application of the decompositions to linear least-squares problems of this class is also given to show the usefulness of the decompositions. More numerical examples are provided in §4 to demonstrate the frequent occurrences of generalized reflexive matrices in many scientific and engineering disciplines.
Throughout this paper, we use the superscripts T, *, and −1 to denote the transpose, conjugate transpose, and inverse of matrices (vectors), respectively. The symbol stands for the direct sum of matrices as usual. Unless otherwise noted, we use to denote the identity matrix of dimension k. All matrix-matrix multiplications and additions are assumed to be conformable if their dimensions not mentioned. .
2. Generalized Simultaneous Diagonalization
Before developing the (semi-)explicit block-diagonal structures for some important types of generalized reflexive matrices, we present first the following theoretically simple yet computationally useful observation regarding a simultaneous diagonalization process. Although diagonalization usually refers to square matrices, in this paper, we use the same term for rectangular matrices. In other words, a rectangular matrix is also said to be diagonal if for . Block-diagonal rectangular matrices are defined in an analogous way.
Theorem 2.1. (Generalized Simultaneous Diagonalization) Let and be diagonalizable, . If , then there exist nonsingular matrices and such that
are all diagonal matrices.
Proof. The proof given below basically employs the same technique used in   for the simultaneous diagonalization of two square matrices that commute. Let and be the matrices that diagonalize F and G, respectively:
where the diagonal elements of (respectively ) are the eigenvalues of F (respectively G). Suppose that the matrix F has k distinct eigenvalues with multiplicities , respectively, where ; and the matrix G has l distinct eigenvalues with multiplicities , respectively, where . Assume further that among the k distinct eigenvalues of F, s of them are also eigenvalues of G, . If , then all and are distinct, implying that A is a null matrix, as can be seen later. Therefore, we exclude this trivial case. Without loss of generality, we can assume that
where denotes a block-diagonal matrix and . Note that and are all distinct. Now, partition the matrix , denoted by B, according to the block forms of and as so that are pi-by-qj submatrices, and . If , we have which implies that
Since only if , we know that B is a block-diagonal matrix, or more precisely, if or if . (This can be considered as a block-equivalence decomposition for rectangular matrices.) It is well-known that for any matrix B in there exist unitary matrices and such that the singular value decomposition is diagonal with nonnegative elements  . Now, let and be the matrices that diagonalize and take
Let . We see that is diagonal. Taking
it is clear that
Therefore, they are all diagonal matrices.
Remark 1: Note that the converse of this theorem is not true in general. It is simple to construct such examples from diagonal matrices.
Remark 2: If the diagonalizable matrix F is the same as G, and A is diagonalizable (A is a square matrix in this case), by taking to be the matrices such that are diagonal and replacing with , this theorem along with its converse part (it now exists) then reduces to the classical simultaneous diagonalization theorem for commuting square matrices as given in (  , p. 50).
Note also that this theorem is different from the simultaneous diagonalization theorems presented in   where the simultaneous diagonalization applies to rectangular matrices of the same size.
Corollary 2.2. Let and be Hermitian, . If , then there exist unitary matrices and such that
are all diagonal matrices.
Proof. Since Hermitian matrices are diagonalizable by unitary matrices, the proof is trivial.
The usefulness of Theorem 2.1 or Corollary 2.2 lies in the fact that if we know the eigenpairs of the matrices F and G, then the matrix A can be block-diagonalized into independent submatrices by the eigenvectors (with some proper ordering) of F and G so that a single large problem can be handled via smaller and independent subproblems, yielding computational efficiency and large-grain parallelism at the same time. The question then boils down to whether those eigenpairs can easily be obtained or not. This of course depends on F and G. Fortunately, for our generalized reflexive matrices that come from physical problems, their eigenpairs of P and Q are explicitly known in most cases, as can be seen from the example presented in Section 4. In the next section, we present several generalized reflexive decompositions that lead to either explicit or semi-explicit block-decomposed forms, which are computationally attractive.
3. Decompositions for Generalized Reflexive Matrices
We now turn to generalized reflexive matrices A, which are not necessary square matrices. The decomposition schemes presented below for A are special applications of the general results developed in the previous section. Our main purpose is to obtain explicit forms of the block structure for some frequently encountered cases of A. Let be generalized reflexive. Recall that P and Q are two generalized reflection matrices, which are unitary Hermitian matrices. Therefore, they have at most two distinct eigenvalues 1 and −1. Furthermore, the relation can be expressed as since . From Corollary 2.2, we know that A can be block-diagonalized into two independent submatrices. This information along, however, is not enough from the computational point of view. we still need to know the eigenpairs of P and Q in order to obtain the explicit decomposed form of A. In the following, we derive several explicit or semi-explicit decomposed forms for some important types of generalized reflexive matrices, starting with the simplest one.
Theorem 3.1. Let and , n and m even, be two matrices that take the following forms.
where and are unitary. Let be partitioned as , , with each , and . If , then there exist two unitary matrices X and Y such that
Proof. Clearly, both P and Q are generalized reflection matrices. Therefore, A is a generalized reflexive matrix. Take X and Y to be the unitary matrices
where we have used the unitarity of and and the relations and , which results from the assumption of . Note that and , which also explains, via Corollary 2.2, why this decomposition is possible.
Theorem 3.2. Let and , and , be the following two generalized reflection matrices:
where and are unitary matrices of dimensions p and q, respectively; , . Let be partitioned as , , with , , and . If , then there exist two unitary matrices X and Y such that
Proof. Take X and Y to be the following two unitary matrices:
Then the unitary transformation yields
If , we immediately have the following relations among the submatrices .
Employing these relations and the unitarity of and for (12), we obtain a much simplified form of the transformation . Namely,
Accordingly, we have the results we want:
Note that in (13), can be replaced by and replaced by since . Computationally, one should use the expressions that are easier to compute. Note also that X and Y do not depend on and , and
Remark 3: In Theorem 3.1 and 3.2 if the unitarity requirement of P, Q, X, and Y is lifted, a slightly more general case can be obtained simply by replacing the conjugate transpose with the inverse (existence of and assumed) in places of , , , and . With this replacement, all the results in the proofs remain intact. The matrices A in this case, however, are not necessarily generalized reflexive since P and Q may not be generalized reflection matrices.
Remark 4: Obviously, Theorem 3.2 reduces to Theorem 3.1 if and in (10) do not exist, i.e., . If is present and disappears, then by partitioning A as , and , according to the block forms of P and Q, we have
which is decoupled into two independent sub-blocks when . Analogous to (13), and can be expressed as and , respectively since in this case . Instead, if disappears and remains and the matrix A is partitioned in accordance with P and Q as
then we have
where and because . This transformation again decouples the matrix A into two independent sub-blocks when .
As seen from the transformations presented in the previous section, the decomposed forms of A of this class are very simple to compute. This is especially true when P and Q are reflection (symmetric signed permutation) matrices, which arise frequently in a very wide range of real-world applications, because any reflection matrix can be symmetrically permuted to yield one of the forms of (6) and (10), with and being some signed permutation matrices whereas and some reflection matrices. Furthermore, the decompositions preserve all singular values because they make use of unitarily equivalence transformations, which can be applied to both square matrices and rectangular matrices. Therefore, they are useful not only for linear systems but for linear least-squares problems and singular value problems as well. The only requirement is the existence of the generalized reflexivity property of the matrix A. When P is the same as Q, the decompositions lead to similarity transformations and, accordingly, preserve all eigenvalues. It is exactly this simplicity and preservance of singular values or eigenvalues that makes these decompositions computationally attractive. To demonstrate the usefulness of these decompositions in attacking applications of this type, we present in this section an application of the decompositions to one of the numerical examples described in  , where the same problem is solved using only basic generalized reflexive properties, without resorting to matrix decompositions.
Numerical example. Consider the following overdetermined linear system:
Let A be the coefficient matrix of the overdetermined system. It is simple to observe that A is a generalized reflexive matrix: where
are two reflection matrices. It deserves mentioning that the coefficient matrix A is the edge-node incidence matrix of a level network with reflexive symmetry.
Whether this overdetermined linear system is to be solved via its normal equation or using a QR decomposition instead, we can decompose the original problem into two independent subproblems first, using the decomposition techniques presented in the previous section. Let
The overdetermined system is then transformed to with
where is intentionally inserted to avoid unnecessary multiplications of in forming from b. Now, let be partitioned, according to the block forms of X and Y, as
The transformation can easily be obtained without actually performing expensive matrix-matrix multiplications. We simply use the explicit form of (14) by substituting for and −1 for , yielding
It is simple to obtain without resorting to a dense matrix-vector multiplication.
This transformation then decouples the original system into
The normal equations of (21) and (22) are simply
respectively, whose solutions are and . The final solution x can now be retrieved from and with ease.
whose correctness can be verified from the normal equation of the original system.
At this point, it is clear that the main reason why transformations of this type are so cheap to obtain is not only that explicit forms are available but that no arithmetic multiplications or divisions are involved in forming the decoupled subsystems except the central block row of A and b and the central block column of A, if any, such as and in this example. The dimensions of these blocks are usually very small for large-scale problems with reflexive symmetry because they involve only the nodes/edges on the line or plane of symmetry. Therefore, this extra work can easily be offset by the tremendous savings resulting from solving two smaller subproblems whose sizes are only about half of the original problem. It is worth mentioning that solving sequentially two independent decomposed subproblems each of half size of a single problem is about four times faster than solving the undecomposed one. This is exactly where computational efficiency comes from. The large-grain parallelism induced by these decompositions is an additional advantage when the subproblems are solved on a multiprocessor on multiple networked computers.
We close this section by emphasizing the fact that a great number of scientific and engineering applications require solutions to linear least-squares problems, singular value problems, linear systems, or eigenvalue problems whose coefficient matrices are either generalized reflexive nontrivial reflection matrices P and Q or reflexive P (or Q). Instead of giving more numerical examples, we just mention that the node-edge (or edge-node) incidence matrix of any finite network or graph that possesses reflexive symmetry or that can be redrawn as one that displays reflexive symmetry is generalized reflexive. Refer to  for more numerical examples.
Generalized reflexive matrices, a newly exploited special class of matrices that have the relation with P and Q being some generalized reflection matrices, are a generalization of centrosymmetric matrices and reflexive matrices. Although it is not trivial to realize their existence purely from the entries of a given matrix, this new class of matrices indeed arise very often from physical problems in many areas of scientific and engineering applications, especially from those with reflexive symmetry. Three such nontrivial numerical examples, each from a distinct real-world application area, can be found in  .
A major part of this paper has been devoted to the exploration of computationally attractive decompositions for taking advantage of the special relation possessed by this class of matrices. The decompositions are based on a generalized simultaneous diagonalization theorem presented in this paper and derived using the eigenvectors of P and Q via unitarily equivalence transformations. When the eigenpairs of P and Q are explicitly known, which is usually the case for generalized reflexive matrices that arise from physical problems with reflexive symmetry, the decompositions yield simple and explicit forms of the decomposed submatrices for the matrices A. One of the generalized reflexive matrices presented in this paper has also been employed to serve as an example to show the usefulness of the derived explicit decompositions for decoupling linear least-squares problems whose coefficient matrices are of this class into smaller and independent subproblems. These decompositions, though theoretically simple, can lead to much more efficient computation for large-scale applications. It also induces large-grain parallelism as a by-product. Furthermore, they preserve either the singular values or the eigenvalues of the matrices and, therefore, immediately applicable not only for handling linear least-squares problems and linear systems but for attacking singular value problems or eigenvalue problems.