Bounding the non-multiplicativity of isometric projection

Question

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.

Answer 1

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.

Answer 2

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.

---