6
$\begingroup$

Every $A \in \text{GL}_n(\mathbb{R})$ has a unique Polar decomposition:

$A=O_AP_A$, $O \in \operatorname{O}_n, P \in \operatorname{Psym}_n$. In particular the orthogonal factor is given by $$O_A=A(\sqrt{A^TA})^{-1}.$$ Question:

Let $A,B \in \operatorname{GL}_n^+$. Does there exist a positive constant $c<1$ such that $$ |AB-O_{AB}| \ge c|AB-O_AO_B|$$

(Where the norm $| \cdot |$ is the standard Euclidean/Frobenius norm)

Motivation:

$O_A$ is the closest matrix in $\text{SO}_n$ to $A$; We can think of it as the isometric projection of $A$. This projection is not multiplicative in general** (i.e $O_{AB} \neq O_AO_B $ for some $A,B$, for a concrete example see here).

My question concerns the boundedness of the "error" (in computing the distacne from $\text{SO}_n$) when using $O_A O_B$ instead of $O_{AB}$.


** Indeed, see this previous question of mine, which concerns the analysis of the pairs of matrices satisfying the multiplicativity property.

$\endgroup$
  • $\begingroup$ $AB$ can be accidentally orthogonal without any of $A$ and $B$ being orthogonal, in which case the left hand side is $0$ but the other one may be not (say,when $B=A^{-1}$ and $A$ fails to commute with $A^T$, in which case you get $A(\sqrt{A^TA})^{-1}A^{-1}\sqrt{AA^T}$ for $O_AO_B$ and I do not see why on Earth that monster should be anywhere near the identity matrix though, to be honest, I didn't try to check formally or even computationally that it isn't.) $\endgroup$ – fedja Sep 15 '16 at 14:16
  • $\begingroup$ Your point seems interesting, though your particular example won't work. It turns out that $O_{A^{-1}}=(O_A)^{-1}$ for every invertible matrix $A$ (not just normal ones). (You can prove this using SVD, or by using the uniqueness of the positive square root). So, we will get that in this case both sides are equal to zero. The problem was that for any $A,B=A^{-1} $ , $O_{AB} =O_AO_B$: In order to try to refute the existence of such a constant we need to examine "bad" pairs where the equality does not hold. $\endgroup$ – Asaf Shachar Sep 15 '16 at 14:28
  • $\begingroup$ @fedja It turns out the investiagtion of these pairs is non trivial and interesting by itself: see here: mathoverflow.net/questions/248842/… $\endgroup$ – Asaf Shachar Sep 15 '16 at 14:28
  • $\begingroup$ Indeed :-) Sometimes I'm too hasty in my conclusions. Then, if you go through the routine you suggested, the question becomes if for any two self-adjoint positive definite matrices $P$ and $Q$ the identity matrix $I$ is the closest one to the product $PQ$ among all orthogonal matrices up to a constant factor. I'll try to think of it :-) $\endgroup$ – fedja Sep 15 '16 at 15:22
  • $\begingroup$ Alas, if we talk about the operator norm, then the constant does depend on the dimension (so, in your notation, $c\approx (\log n)^{-1}$). You seem to care more about the Frobenius norm though. I surmise that it doesn't really make any difference, but am too lazy to try to modify my argument to cover that case now. Let me know if anything is unclear or if you have any other questions :-). $\endgroup$ – fedja Sep 16 '16 at 1:03
5
+50
$\begingroup$

If the constant is allowed to depend upon the dimension, the estimate is simple. Let $A=O_AP_A,B=O_BP_B$, then $AB=O_AO_B(O_B^*P_AO_B)P_B$ and we are left with showing that if the product of two positive definite self-adjoint operators $X=O_B^*P_AO_B$ and $Y=P_B$ is $\delta$-close to a unitary operator $V$, then it is $C\delta$-close to $I$. Now, we do not really know much about $XY$ except that it is conjugate to $X^{1/2}YX^{1/2}$, so all eigenvalues are real positive. Thus, it will suffice to show that if a $\delta$-perturbation of a unitary operator $U$ has real positive eigenvalues, then $U$ is $C\delta$-close to the identity. However, if it were not the case, there would be an eigenvalue of $U$ that is $\frac 12 C\delta$ far from the positive semi-axis. If you now take the Gershgorin disks of radius $\delta$ and if $C>5n$, say (where $n$ is the matrix size), then there would be a connected component of the union of the Gershgorin disks that would not cross the positive semi-axis, so some eigenvalues would be confined there.

I'm still curious if we can get a dimension-independent bound, so don't hurry to accept this answer ;-)

Edit. Since there are some difficulties in understanding, let me go into some details (all of which are totally classical).

Gershgorin-Rouche theorem Let $A_t\quad (t\in[0,1])$ be a continuous family of matrices and $K$ a compact set on the complex plane (with decent boundary, if you want, though it is irrelevant). if the boundary of $K$ is free from the eigenvalues of $A_t$ for all $t\in(0,1)$, then all $A_t$ have the same number of eigenvalues in $K$. In particular, if $A_0$ is normal and $A_t=A_0+tQ$, then each connected component $K$ of the union of closed disks of radius $\|Q\|$ centered at the eigenvalues of $A_0$ has exactly as many eigenvalues of $A_1$ in it as of $A_0$.

Proof The first part is just the classical Rouche theorem about zeroes of analytic functions applied to the characteristic polynomials of $A_t$. To show that second part, let us just show that no $A_t$ can have an eigenvalue $\lambda$ on the boundary of $K$. Indeed, for any non-zero vector $x$, we have $|(A_0-\lambda I)x|\ge \|Q\||x|$ (here we use the normality of $A_0$) and $|tQx|<\|q\||x|$, so, by the triangle inequality $|(A_t-\lambda I)x|>0$.

Now, take $A_0=U$ here and let $K$ be the connected component of the union of disks of radius $\delta$ containing the "faraway" (from the positive real semi-axis) eigenvalue of $U$. Then any $\delta$-perturbation of $U$ must have eigenvalues in $K$. Note that those eigenvalues do not need to be close to any particular eigenvalue of $U$, but they are certainly not real positive, and that's all I need to get a contradiction.

$\endgroup$
  • $\begingroup$ Thanks! However, I am not sure I follow all the details. Would you mind clarifying the following points: (1) In your answer, is U itself a unitary operator? (2) How can you choose the radius of the Gershgorin disks "at your will"? They are determined by the sum of the non-diagonal terms in each row. (I guess you have used implicitly some estimate you did not state). (3) How did you deduce the existence of an eigenvalue far from the positive semi-axis? (I am also not sure what do you mean by "positive semi-axis"; Is it half of the x-axis or the y-axis)? Thanks for your patience. $\endgroup$ – Asaf Shachar Sep 16 '16 at 13:08
  • $\begingroup$ 1) Yes. Actually $U=V$. I was just interrupted when writing and changed the letter for no apparent reason when came back 2) Equal to $\delta$. You are always fine with any $\ell^p$ operator norm, the "row sum" rule arises when $p=\infty$ but I prefer to deal with $\ell^2$ here. 3) $x$-axis, of course. Any connected component of the union of Gershgorin disks contains as many eigenvalues as the number of disks in it and you cannot build a connected chain of length $C\delta/2$ out of $n$ disks of radius $\delta$ if $C>5n$. $\endgroup$ – fedja Sep 16 '16 at 13:29
  • $\begingroup$ Thanks. Unfortunately some things are still not clear to me. I tried to write a more detailed version of your answer as I understand it (CW). I am stuck already at the point of showing existence of such an eigenvalue of $U$, which is far enough from the $x$-axis. (Please see my precise difficulty in the "Attempted proof of the lemma"). $\endgroup$ – Asaf Shachar Sep 16 '16 at 16:19
  • 1
    $\begingroup$ $U$ is unitary, so all eigenvalues of $U$ are on the unit circle. If one of them is far from $1$, it is also far from the positive semi-axis. Also $\|U-I\|$ (the operator norm) is just $\max_{\lambda}|\lambda-1|$ $\endgroup$ – fedja Sep 16 '16 at 16:30
1
$\begingroup$

This is a more detailed version of fedja's answer:

We shall need the following preliminary results:

Lemma 1: Let $\lambda \in \mathbb{S}^1$. Then, the distance of $\lambda$ from $1$ is not greater than twice its distance to the set of non-negative reals.

Proof of lemma 1:

Denote $\lambda = a+ib$. Note that $|\lambda-1|= \sqrt{2-2a}$.

We separate into two cases:

$(1)$: $a \ge 0.$

Since $a \ge 0$, it is clear that $d(\lambda,x_{\ge 0})=|b|$, so

$$2d(\lambda,x_{\ge 0}) \ge |\lambda-1| \iff 2|b| \ge \sqrt{2-2a} \iff 4b^2 \ge 2-2a \iff $$

$$ 2-2a^2=2b^2 \ge 1- a \iff a+1-2a^2 \ge 0$$

This holds since the L.H.S equals $a(1-a)+(1-a^2)$ which is a sum of two non-negative numbers. (Remember $0\le a \le 1$).

$(2)$: $a < 0.$ In that case $d(\lambda,x_{\ge 0})=1$, so the inequality becomes $2 \ge |\lambda-1|$ which is trivial (The diameter of the unit circle is $2$).


Lemma 2:

Let $A_t, \, \,(t\in[0,1])$ be a continuous family of matrices and $K$ a compact set on the complex plane (with a continuous connected boundary). If the boundary of $K$ contains no eigenvalues of $A_t$ for all $t\in(0,1)$, then all $A_t$ for $t \in (0,1)$ have the same number of eigenvalues in $K$, which we denote by $d$. Moreover, the number of eigenvalues of $A_1$ is greater than or equal to $d$.

Proof of lemma 2:

Let $P_t$ be the characteristic polynomial of $A_t$. Then by the assumption on the eigenvalues of $A_t$, $P_t|_{\partial K} \neq 0$.

Since $A_t$ depends continuously on $t$, and the characteristic polynomial of a matrix depends continuously on its entries, $P_t$ depends continuously on $t$.

Fix $t,t' \in (0,1)$ and assume $t <t'$. We want to show $P_t,P_{t'}$ have the same number of roots in $K$. By the Rouch Theorem, this holds if $$ |P_t(z)-P_{t'}(z)| < |P_t(z)|+|P_{t'}(z)| $$ for every $z \in \partial K$.

Assume by contradiction that for some $z \in \partial K$,$|P_t(z)-P_{t'}(z)| = |P_t(z)|+|P_{t'}(z)| $.

Then $P_t(z)\cdot \overline{P_{t'}(z)} \le 0$. Look at the function $s \to P_s(z)\cdot \overline{P_{t'}(z)}$ defined on $[t,t']$; It is positive at $s=t'$, and non-positive at $s=t$. By continuity, there is some $s \in [t,t']$ such that $P_s(z)\cdot \overline{P_{t'}(z)}=0$, which is a contradiction.

Thus, $P_t$ has $d$ roots in $K$ and $n-d$ roots in $K^c$ for every $t \in (0,1)$.

Since roots of a polynomial depend continuously on its coefficients, and since $K^c$ is open we get that $P_1$ cannot have more than $n-d$ roots in $K^c$: If it would had "too many" roots in $K^c$ then this situation would also be true for some $t<1$, contradiction.

So, the number of roots of $P_1$ in $K$ is at least $d$, as required.


Lemma 3:

Let $A_0$ be a normal matrix, $Q$ be an arbitrary non-zero matrix. Then each connected component $K$ of the union of closed disks of radius $\|Q\|_{op}$ centered at the eigenvalues of $A_0$ has at least one eigenvalue of $A_0+Q$ in it.

Proof of lemma 3:

Denote the eigenvalues of $A_0$ by $\lambda_1(A_0),...,\lambda_n(A_0)$. Define $A_t=A_0+tQ$. Note that $A_0$ (and hence $A_t$ for small enough $t$) has an eigenvalue in $\operatorname{int}(K)$.

By lemma 2, it suffices to show that no $A_t$ can have an eigenvalue $\lambda$ on the boundary of $K$.

Let $t \in (0,1)$. Since $\lambda \in \partial K$, it satisfies $|\lambda-\lambda_j(A_0)|\ge\|Q\|_{op}$ for every $j$. Since $A_0-\lambda I$ is normal, its singular values are the absolute values of its eigenvalues, so the minimal singular value of $A_0-\lambda I$ is greater or equal to $\|Q\|_{op}$. This implies that for any non-zero vector $x$, $$|(A_0-\lambda I)x|\ge \|Q\|_{op}|x|$$

and $$|t| < 1 \Rightarrow |tQx|<|Qx|\le\|Q\|_{op}|x|.$$

So, by the triangle inequality $$|(A_t-\lambda I)x|=|(A_0-\lambda I)x-(-tQx)| \ge |(A_0-\lambda I)x| -|tQx| >0.$$

We have shown $\lambda$ is indeed not an eigenvector of $A_t$.

Note that the last estimate used the fact $t$ is strictly smaller than $1$. This is the reason why we needed a version of lemma 2 where nothing is assumed on the eigenvalues of $A_1$ on $\partial K$.


Back to the main proposition:

We want to prove $$(1) \, \, |AB-O_{AB}| \ge c|AB-O_AO_B|$$ for some $1>c>0$. Let $A=O_AP_A,B=O_BP_B$ be the polar decompositions of $A,B$. Then $$AB=O_AO_B(O_B^TP_AO_B)P_B=O_AO_BXY,$$ where we Denote $$X=O_B^TP_AO_B,Y=P_B \, \text{ (both are symmetric positive definite) }$$

Then $(1)$ becomes:$$ |O_AO_BXY-O_{AB}| \ge c|O_AO_BXY-O_AO_B|=c|XY-I|$$

(The last equality holds whether we use the Frobenius norm, or the operator norm, since both are invariant under multiplication by orthogonal matrices).

Denoting $U_{A,B}=(O_AO_B)^{-1}O_{AB}$, and using again the orthogonal invariance of the norm we get that $(1)$ is equivalent to $$ |XY-U_{A,B}| \ge c|XY-I|$$

Note that $XY$ similar to $X^{1/2}YX^{1/2}$, so all its eigenvalues are real positive.

Thus, it suffices to prove the following:

Lemma 4:

Let $U \in \operatorname{O}_n$,$A \in M_n$ with positive eigenvalues. Then $|U-I|_{op} \le 5n|A-U|_{op}$.

Why lemma 4 implies our required result?

$$|A-I|_{op} \le |A-U|_{op}+|U-I|_{op} \le (5n+1)|A-U|_{op}$$ Putting $A=XY,U=U_{A,B}$ this becomes:

$$ |XY-I|_{op} \le (5n+1)|XY-U_{A,B}|_{op}$$

Q.E.D

Proof of the lemma 4:

Assume by contradiction that $|U-I|_{op} > 5n|A-U|_{op}$.

Since $U-I$ is normal $|U-I|_{op} = \max{|\lambda_i-1|}$ (where the $\lambda_i$ are the eigenvalues of $U$). So, there exists an eigenvalue $\lambda$ of $U$, such that $|\lambda-1|>5n|A-U|_{op}$.

Since $\lambda \in \mathbb{S}^1$ lemma (1) implies that the distance of $\lambda$ from the semi-positive $x$ axis is greater than $2\frac{1}{2}n|A-U|_{op}$.

Now we use lemma 3: Take $A_0=U, Q=A-U$ here and let $K$ be the connected component of the union of disks of radius $|A-U|_{op}$ containing the "faraway" (from the positive real semi-axis) eigenvalue of $U$. Then (according to lemma 3) $A$ has at least one eigenvalue in $K$.

But this is impossible:

Since the eigenvalues of $A$ are real positive, the distance between an eigenvalue of $A$ in $K$, and the faraway eigenvalue of $U$ is at least $2\frac{1}{2}n|A-U|_{op}$. So $\operatorname{diam}(K) \ge 2\frac{1}{2}n|A-U|_{op}$.

However, $K$ is a union of at most $n$ disks of radius $|A-U|_{op}$, thus $\operatorname{diam}(K) \le 2n|A-U|_{op}$ which is a contradiction.


$\endgroup$
  • 1
    $\begingroup$ I replied in the previous comment thread. Also, you do not need large $b$: the point $-1$ is also far from the positive semi-axis. All that I'm saying is that on the unit circle the distance to $1$ can only be twice bigger than the distance to non-negative reals. $\endgroup$ – fedja Sep 16 '16 at 17:28
  • $\begingroup$ Thanks, I see that now; Pieces are starting to fall into place... your proof seems very nice indeed. I am now beyond the obstacle of the eigenvalue which is far from the non-negative reals. I still do not understand how exactly did you use the Gershgorin disks. I think you are supposed to use the fact $|U-A|_{op} \le \delta$ to claim there is an eigenvalue of $U$ which is close to an eigenvalue of $A$ (which we know must be real positive). Then, you get that on the one hand $U$ has an eigenvalue close to the $x$-axis, and one eigenvalue that is quite far from it... $\endgroup$ – Asaf Shachar Sep 17 '16 at 13:03
  • $\begingroup$ @fedjabut ... but the gap cannot be bridged using all the Gershgorin disks of $U$. However, I still do not understand how you show there is an eigenvalue of $U$ which is close to one of $A$, nor the precise version of the Gershgorin circle theorem you are using (I did not quite understand the relevance of your previous comment about using different norms, doesn't it become relevant only when using "blocks version" of the theorem?) I would be very happy if you could write more explicitly your full argument. Feel free to edit my answer if you want to. $\endgroup$ – Asaf Shachar Sep 17 '16 at 13:03
  • $\begingroup$ I edited mine :-). See if it is clear now $\endgroup$ – fedja Sep 17 '16 at 15:56
  • 1
    $\begingroup$ You know more: namely that $|\lambda-\lambda_j(A_0)|\ge\|Q\|$ for every $j$. So, the minimal singular value of $A_0-\lambda I$ is large. $\endgroup$ – fedja Sep 17 '16 at 22:53

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.