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$
10
  • $\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$ Dec 20, 2015 at 6:19
  • $\begingroup$ @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. $\endgroup$
    – Pushpendre
    Dec 20, 2015 at 6:27
  • $\begingroup$ 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$). $\endgroup$ Dec 20, 2015 at 6:27
  • 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$ Dec 20, 2015 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$ Dec 20, 2015 at 11:47

2 Answers 2

14
$\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-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
  • 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, 2015 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$
3
  • $\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, 2015 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, 2015 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$ Dec 20, 2015 at 16:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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