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

Improve this question
$\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$
    – Igor Khavkine
    Commented 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
    Commented 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$
    – Igor Khavkine
    Commented 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$
    – Federico Poloni
    Commented 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$
    – Johannes Hahn
    Commented Dec 20, 2015 at 11:47

2 Answers 2

Reset to default
15
$\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$.

Improve this answer
$\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
    Commented Dec 20, 2015 at 15:52
3
$\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.

Improve this answer
$\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
    Commented 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
    Commented Dec 20, 2015 at 6:18
  • 1
    $\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
    Commented Dec 20, 2015 at 16:06

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .