A matrix is pseudo-orthogonal if
where is a signature matrix. A matrix satisfying (1) is also known as a -orthogonal matrix, where is another notation for a signature matrix. Of course, if then is orthogonal.
It is easy to show that is also pseudo-orthogonal. Furthermore, is clearly nonsingular and it satisfies
Since is orthogonal, this equation implies that and hence that
What are some examples of pseudo-orthogonal matrices? For and , is of the form
which includes the matrices
The Lorentz group, representing symmetries of the spacetime of special relativity, corresponds to matrices with .
Equation (2) shows that is similar to the inverse of its transpose and hence (since every matrix is similar to its transpose) similar to its inverse. It follows that if is an eigenvalue of then is also an eigenvalue and it has the same algebraic and geometric multiplicities as .
By permuting rows and columns in (1) we can arrange that
We assume that has this form throughout the rest of this article. This form of allows us to conveniently characterize matrices that are both orthogonal and pseudo-orthogonal. Such a matrix must satisfy , which means that , and any such orthogonal matrix is pseudo-orthogonal.
Pseudo-orthogonal matrices arise in hyperbolic problems, that is, problems where there is an underlying indefinite scalar product or weight matrix. An example is the problem of downdating the Cholesky factorization, where in the simplest case we have the Cholesky factorization of a symmetric positive definite and want the Cholesky factorization of , which is assumed to be symmetric positive definite. A more general downdating problem is that we are given
and the Cholesky factorization and wish to obtain the Cholesky factor of . Note that and are . This task arises when we solve a regression problem after the observations corresponding to have been removed. The simple case above corresponds to removing one row (). Assuming that , we would like to obtain cheaply from , and numerical stability considerations dictate that we should avoid explicitly forming . If we can find a pseudo-orthogonal matrix such that
with given by (5) and upper triangular, then
so is the desired Cholesky factor.
The factorization (6) is called a hyperbolic QR factorization and it can be computed by using hyperbolic rotations to zero out the elements of . A hyperbolic rotation has the form (4), and an hyperbolic rotation is an identity matrix with a hyperbolic rotation embedded in it at the intersection of rows and columns and , for some and .
In general, a hyperbolic QR factorization of with and has the form with pseudo-orthogonal with respect to and upper triangular. The factorization exists if is positive definite.
Another hyperbolic problem is the indefinite least squares problem
where , , and are given, and with . For or we have the standard least squares (LS) problem and the quadratic form is definite, while for the problem is to minimize a genuinely indefinite quadratic form. This problem arises, for example, in the area of optimization known as smoothing.
The normal equations for (7) are , and since the Hessian matrix of the quadratic objective function in (7) is it follows that the indefinite least squares problem has a unique solution if and only if is positive definite. To solve the problem we can use a hyperbolic QR factorization to write
Solving the problem now reduces to solving the triangular system , where comprises the first components of . The same equation can also be obtained without using the normal equations by substituting the hyperbolic QR factorization into (7).
The Exchange Operator
A simple technique exists for converting pseudo-orthogonal matrices into orthogonal matrices and vice versa. Let with , partition
and assume is nonsingular. The exchange operator is defined by
It is easy to see that the exchange operator is involutory, that is,
and moreover (recalling that is given by (5)) that
The next result gives a formula for the inverse of .
Lemma 1. Let with nonsingular. If is nonsingular and exists then is nonsingular and .
Proof. Consider the equation
By solving the first equation for and then eliminating from the second equation we obtain
By the same argument applied to , we have
Hence for any and there is a unique and , which implies by (10) that is nonsingular and that .
Now we will show that the exchange operator maps pseudo-orthogonal matrices to orthogonal matrices and vice versa.
Theorem 2. Let . If is pseudo-orthogonal then is orthogonal. If is orthogonal and is nonsingular then is pseudo-orthogonal.
Proof. If is pseudo-orthogonal then , which implies that is nonsingular. Since , it follows that also has a nonsingular block and so exists. Furthermore, using Lemma 1, . But (9) shows that , and we conclude that is orthogonal.
Assume now that is orthogonal with nonsingular. Then exists and Lemma 1 shows that is nonsingular and . Hence, using (9),
which shows that is pseudo-orthogonal.
This MATLAB example uses the exchange operator to convert an orthogonal matrix obtained from a Hadamard matrix into a pseudo-orthogonal matrix.
>> p = 2; n = 4; >> A = hadamard(n)/sqrt(n), Sigma = blkdiag(eye(p),-eye(n-p)) A = 5.0000e-01 5.0000e-01 5.0000e-01 5.0000e-01 5.0000e-01 -5.0000e-01 5.0000e-01 -5.0000e-01 5.0000e-01 5.0000e-01 -5.0000e-01 -5.0000e-01 5.0000e-01 -5.0000e-01 -5.0000e-01 5.0000e-01 Sigma = 1 0 0 0 0 1 0 0 0 0 -1 0 0 0 0 -1 >> Q = exc(A,p), Q'*Sigma*Q Q = 1 1 -1 0 1 -1 0 -1 1 0 -1 -1 0 1 -1 1 ans = 1 0 0 0 0 1 0 0 0 0 -1 0 0 0 0 -1
The code uses the function
function X = exc(A,p) %EXC Exchange operator. % EXC(A,p) is the result of applying the exchange operator to % the square matrix A, which is regarded as a block 2-by-2 % matrix with leading block of dimension p. % p defaults to floor(n)/2. [m,n] = size(A); if m ~= n, error('Matrix must be square.'), end if nargin < 2, p = floor(n/2); end A11 = A(1:p,1:p); A12 = A(1:p,p+1:n); A21 = A(p+1:n,1:p); A22 = A(p+1:n,p+1:n); X21 = A11\A12; X = [inv(A11) -X21; A21/A11 A22-A21*X21];
Hyperbolic CS Decomposition
For an orthogonal matrix expressed in block form there is a close relationship between the singular value decompositions (SVDs) of the blocks, as revealed by the CS decomposition (see What Is the CS Decomposition?). An analogous decomposition holds for a pseudo-orthogonal matrix. Let be pseudo-orthogonal with respect to in (5), and suppose that is partitioned as
Then there exist orthogonal matrices and such that
where , , and , with for all . This is the hyperbolic CS decomposition, and it can be proved by applying the CS decomposition of an orthogonal matrix to .
The leading principal submatrix in (11) generalizes the matrix (4), and in fact it can be permuted into a direct sum of such matrices.
Note that the matrix on the right in (11) is symmetric positive definite. Therefore the singular values of are the eigenvalues of that matrix, namely
Since for all , the first singular values occur in reciprocal pairs, hence the largest and smallest singular values satisfy (with strict inequality unless ). This gives another proof of (3).
While an orthogonal matrix is perfectly conditioned, a pseudo-orthogonal matrix can be arbitrarily ill conditioned, as follows from (3). For example, the MATLAB function
gallery('randjorth') produces a random pseudo-orthogonal matrix with a default condition number of
>> rng(1); A = gallery('randjorth',2,2) % p = 2, n = 4 A = 2.9984e+03 -4.2059e+02 1.5672e+03 -2.5907e+03 1.9341e+03 -2.6055e+03 3.1565e+03 -7.5210e+02 3.1441e+03 -6.2852e+02 1.8157e+03 -2.6427e+03 1.6870e+03 -2.5633e+03 3.0204e+03 -5.4157e+02 >> cond(A) ans = 6.7109e+07
This means that algorithms that use pseudo-orthogonal matrices are potentially numerically unstable. Therefore algorithms need to be carefully constructed and rounding error analysis must be done to ensure that an appropriate form of numerical stability is obtained.
Pseudo-orthogonal matrices form the automorphism group of the scalar product defined by for . More results for pseudo-orthogonal matrices can be obtained as special cases of results for automorphism groups of general scalar products. See, for example, Mackey, Mackey, and Tisseur (2006).
For the set of pseudo-orthogonal matrices is known to have four connected components, a topological property that can be proved using the hyperbolic CS decomposition (Motlaghian, Armandnejad, and Hall, 2018).
One can define pseudo-unitary matrices in an analogous way, as such that . These correspond to the automorphism group of the scalar product for . The results we have discussed generalize in a straightforward way to pseudo-unitary matrices.
The exchange operator is also known as the principal pivot transform and as the sweep operator in statistics. Tsatsomeros (2000) gives a survey of its properties
The hyperbolic CS decomposition was derived by Lee (1948) and, according to Lee, was present in work of Autonne (1912).
This is a minimal set of references, which contain further useful references within.
- Adam Bojanczyk, Nicholas J. Higham and Harikrishna Patel, Solving the Indefinite Least Squares Problem by Hyperbolic QR Factorization, SIAM J. Matrix Anal. Appl. 24(3), 914–931, 2003
- Nicholas J. Higham, -Orthogonal Matrices: Properties and Generation, SIAM Rev. 45(3), 504–519, 2003
- H. C. Lee, Canonical Factorization of Pseudo-Unitary Matrices, Proc. London Math. Soc. s2-50, 230–241, 1948.
- D. Steven Mackey, Niloufer Mackey, and Françoise Tisseur, Structured Factorizations in Scalar Product Spaces, SIAM J. Matrix Anal. Appl. 27(3), 821–850, 2006.
- Sara M. Motlaghian, Ali Armandnejad, and Frank J. Hall, Topological Properties of -Orthogonal Matrices, Linear and Multilinear Algebra 66(12), 2524–2533, 2018.
- Michael Stewart and G. W. Stewart, On Hyperbolic Triangularization: Stability and Pivoting, SIAM J. Matrix Anal. Appl. 19(4), 847–860, 1998
- Michael J. Tsatsomeros, Principal Pivot Transforms: Properties and Applications, Linear Algebra Appl. 307, 151–165, 2000.
Related Blog Posts
- What Is an Orthogonal Matrix? (2020)
- What Is the CS Decomposition? (2020)
This article is part of the “What Is” series, available from https://nhigham.com/category/what-is and in PDF form from the GitHub repository https://github.com/higham/what-is.