# The space of positive definite orthogonal matrices

The matrix $\begin{bmatrix}1 & 0 \\ 0 & -1\end{bmatrix}$ is orthogonal and indefinite. $\begin{bmatrix}1 & 0 \\ 0 & 2\end{bmatrix}$ is positive definite and not orthonormal. and the Identity matrix $I$ is of course both orthogonal and positive definite. Let $S$ be the intersection of orthogonal matrices and positive definite matrices. We have seen that $S$ is non-empty.

By a positive definite matrix, I mean either a symmetric or asymmetric matrix $M \in \mathbb{R}^{p^2}$ whose quadratic form satisfies $\forall x \in \mathbb{R}^p \setminus \{0\}: x^TMx > 0$. Let $P$ denote the set of all positive definite matrices. Then $P$ is a convex cone.

$S$ is not a convex cone, unlike $P$. Also unlike $P$, $S$ is closed under multiplication The product of any two matrices in $S$ is guaranteed to be at least PSD.[1]

I am interested in complete characterizations of this space $S$, which globally behaves more like the space of orthogonal matrices. My real motivation is that I want to know whether there are efficient procedures for testing whether a matrix $M$ is in $S$ that are faster than testing for positive definiteness which requires the calculation of eigenvalues? E.g. such procedures might take only $O(p^2)$ computations. I tried to google for resources but nothing relevant came up.

[1] Orthogonal matrices are of course closed under multiplication. The product of two PD matrices is PD PSD matrices is PSD iff their product itself is normal, which is true in $S$.

Reference: On a product of positive semidefinite matrices, A.R. Meenakshi, C. Rajian, Linear Algebra and its Applications, Volume 295, Issues 1–3, 1 July 1999, Pages 3–6.

In case someone is wondering, the real real reason, why I am interested in this question is because I want to "efficiently" find a "reasonably good" positive definite approximation of a matrix whose $QR$ decomposition is known to me. The details of this part are best left for future.

• Testing orthogonality (at least naively) takes $O(p^3)$ operations because it requires the computation of $M^T M$. I can't think of faster ways of checking that. So unless you already start with the information that $M$ is orthogonal, I don't see how to improve on $O(p^3)$ to test that $M\in S$. Commented Dec 20, 2015 at 6:19
• @IgorKhavkine : Yes you are right, In my application I would know that the matrix is definitely orthonormal apriori. At every step I want to figure out whether the current orthogonal matrix is also PD. Commented Dec 20, 2015 at 6:27
• Also, I think your remark [1] is false. One way to characterize $S$ is to say that it consists of all orthogonal matrices $M$ for which no vector $x$ is rotated to $Mx$ making an angle of more than $\pi/2$ with $x$. But then $S$ cannot be closed under multiplication, as lots of small rotations (hence in $S$) can add up to a big rotation (hence not in $S$). Commented Dec 20, 2015 at 6:27
• Small detail: testing for positive definiteness does not require computation of the eigenvalues. One can run a Cholesky (or LDL^T) factorization and see if the procedure fails. This is signlificantly cheaper. Commented Dec 20, 2015 at 10:28
• @FedericoPoloni That doesn't work, because this tests only for symmetric-and-positive-definiteness. Pushpendre explicitely wants to talk about asymmetric but positive definite matrices. Commented Dec 20, 2015 at 11:47

You may find the Cayley transform to be useful here:

As is well-known and easy to prove, every orthogonal $$n$$-by-$$n$$ matrix $$R$$ that does not have $$-1$$ as an eigenvalue can be written uniquely in the form $$R = (I-A)(I+A)^{-1}$$ for some anti-symmetric matrix $$A$$ for which $$I+A$$ is invertible, and, conversely, if $$A$$ is any anti-symmetric matrix such that $$(I+A)$$ is invertible, the matrix $$R$$ in the above formula is orthogonal and $$I+R$$ is invertible.

In fact, $$A = (I-R)(I+R)^{-1}$$, so $$A$$ is easy to find. The two matrices $$R$$ and $$A$$ are said to be Cayley transforms of each other, and this provides a 'rational parametrization' of the orthogonal group minus the hypersurface consisting of the orthogonal matrices that have $$-1$$ as an eigenvalue. (Note that $$R$$ and $$A$$ commute.)

Now $$R$$ satisfies the stronger condition that $$x^TRx>0$$ for all nonzero $$x\in\mathbb{R}^n$$ if and only if (setting $$y=(I+A)^{-1}x$$ or, equivalently $$x = (I+A)y$$), we have $$0 < x^TRx = y^T(I+A)(I-A)y = y^T(I-A^2)y = |y|^2-|Ay|^2$$ for all $$y\in \mathbb{R}^n$$. Equivalently, the matrix norm of $$A$$, i.e., $$\|A\|$$, should be strictly less than $$1$$.

Thus, via the Cayley transform, your set $$S$$ is parametrized by the open convex set in the vector space of anti-symmetric $$n$$-by-$$n$$ matrices consisting of those anti-symmetric matrices $$A$$ whose matrix norm is less than $$1$$.

• Notice however that testing whether $\|A\| < 1$ will cost $O(n^3)$, something that the OP wants to avoid. Nevertheless, doing Lanczos to approximately compute this norm should be faster in practice (and has the advantage of not requiring explicit computation of $A$ given $R$, because otherwise explicit computation of $A$ again costs $O(n^3)$) Commented Dec 20, 2015 at 15:52

A (real) orthogonal matrix $A$ is positive definite if and only the symmetric matrix $M = A + A^T$ is positive definite. There are many equivalent characterizations of this: one is that all leading principal minors of $M$ are positive.

• If the symmetric matrix $M = A + A^T$ is positive definite, then it's not necessary that $A$ would be orthogonal, right? Or is there a unique antisymmetric matrix $M'$ that when added to $M$ would create an orthogonal matrix? Commented Dec 20, 2015 at 6:05
• For example, let $M = \begin{bmatrix}1 & 1\\1 & 2\end{bmatrix}$, then $M$ is positive definite but $A$ can be $M$ plus any anti symmetric matrix $M'$ divided by two. For example if $M' = \begin{bmatrix}0 & -1\\ -1 & 0\end{bmatrix}$ then A = $(M + M') / 2$ would not be orthogonal. Therefore, the above characterization is unsatisfactory. Commented Dec 20, 2015 at 6:18
• Of course, it's not true that each symmetric matrix $S$ has an anti-symmetric 'partner' $A$ such that $S+A$ is orthogonal. First of all, the eigenvalues of $S$ have to lie in the interval $[-1,1]$ or no such $A$ can exist. Even this is not enough, though. You also need that the eigenvalues of $S$ other than $\pm 1$ (if any) must have even multiplicity. If those conditions are satisfied, though, it is not hard to show that an $A$ exists such that $R = S+A$ is orthogonal. Commented Dec 20, 2015 at 16:06