7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Please let me know the reason for a downvote. $\endgroup$ – Pushpendre Dec 20 '15 at 3:28
  • $\begingroup$ 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$. $\endgroup$ – Igor Khavkine Dec 20 '15 at 6:19
  • 4
    $\begingroup$ 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. $\endgroup$ – Federico Poloni Dec 20 '15 at 10:16
  • 3
    $\begingroup$ 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. $\endgroup$ – Federico Poloni Dec 20 '15 at 10:28
  • 1
    $\begingroup$ @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. $\endgroup$ – Johannes Hahn Dec 20 '15 at 11:47
12
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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)$) $\endgroup$ – Suvrit Dec 20 '15 at 15:52
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Pushpendre Dec 20 '15 at 6:05
  • $\begingroup$ 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. $\endgroup$ – Pushpendre Dec 20 '15 at 6:18
  • $\begingroup$ 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. $\endgroup$ – Robert Bryant Dec 20 '15 at 16:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.