# 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.

• Please let me know the reason for a downvote. – Pushpendre Dec 20 '15 at 3:28
• 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$. – Igor Khavkine Dec 20 '15 at 6:19
• I downvoted, too, but exclusively for the "most urgently" in bold. I find it inappropriate to urge people to hurry here. If you edit it out, you have my upvote. – Federico Poloni Dec 20 '15 at 10:16
• 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. – Federico Poloni Dec 20 '15 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. – Johannes Hahn Dec 20 '15 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-2A+A^2)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)$) – Suvrit Dec 20 '15 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? – Pushpendre Dec 20 '15 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. – Pushpendre Dec 20 '15 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. – Robert Bryant Dec 20 '15 at 16:06