Return to Answer

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.

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.

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$ have the same number of eigenvalues in $K$.

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

Assume by contradiction that for some $z \in \partial K$,$|P_t(z)-P_0(z)| = |P_t(z)|+|P_0(z)| $.

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

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 exactly as many eigenvalues of $A_0+Q$ in it as of $A_0$.

Denote the eigenvalues of $A_0$ by $\lambda_1(A_0),...,\lambda_n(A_0)$. Define $A_t=A_0+tQ$.

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\||x|$$

and $$|t| < 1 \Rightarrow |tQx|<|Qx|\le\|Q\||x|.$$

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

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

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.

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.

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

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

I am trying to fill in some details in fedja's answer:

Back to the main proposition:

Lemma 3:

Let $U \in \operatorname{O}_n$,$A \in M_n$ with positive eigenvalues, and let $\delta >0$. There exists a constant $C>0$ (independent of $U,A,\delta$) such that if $|A-U|_{op} \le \delta$, then $|U-I|_{op} \le C\delta$. (In fact one can choose $C=5n$).

Why lemma 3 implies our required result?

Taking $\delta=|A-U|_{op}$ we get: $$|A-I|_{op} \le |A-U|_{op}+|U-I|_{op} \le (C+1)|A-U|_{op}$$. Putting $A=XY,U=U_{A,B}$ this becomes:

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

Attempted proof of the lemma 3:

Assume by contradiction that $|U-I|_{op} > C\delta$.

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|>C\delta$.

Since $\lambda \in \mathbb{S}^1$ lemma (1) implies that the distance of $\lambda$ from the semi-positive $x$ axis is greater than $\frac{1}{2}C\delta$.

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

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 exactly as many eigenvalues of $A_0+Q$ in it as of $A_0$.

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

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\||x|$$

and $$|t| < 1 \Rightarrow |tQx|<|Qx|\le\|Q\||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$.

Back to the main proposition:

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

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.