# Find all $x\in\mathbb{C^n}$ such that $||Ax||_2=1$ and $||x||_2=1$

Given $$A\in\mathbb{C}^{n\times n}$$, find all $$x\in\mathbb{C^n}$$ such that $$||Ax||_2=1$$ and $$||x||_2=1$$.

Lets do SVD: $$A=U\Sigma V^*$$, where $$\Sigma=\mathrm{diag}\{\sigma_1,\ldots,\sigma_n\}$$.

We do change of a coordinates $$x=Vy,$$ then we need to find $$y\in\mathbb{C^n}$$ such that $$||\Sigma y||_2=1$$ and $$||y||_2=1$$.

• Note that $\|\Sigma y \|^2 = 1$ is the same as $\sigma_1^2 y_1^2 + \cdots + \sigma_n^2 y_n^2 = 1$. This is the equation of an ellipsoid in $n$ dimensions.
– user169852
May 18, 2021 at 7:58
• so I need to find points where this ellipsoid touches a sphere given by $||y||_2=1$?
– Lee
May 18, 2021 at 8:00
• You could also use regular optimization methods and use ${\left\| x \right\|}_{2}^{2} \leq 1$ to have a convex function. Then find the $\lambda$ for equality.
– Royi
May 23, 2021 at 4:07
• @Royi since I am searching for all $x$ that satisfy certain constraints, I am not sure how this problem can be formulated as optimization problem.
– Lee
May 23, 2021 at 4:50
• What do you mean by all $x$? It’s easy to describe (intersection of an ellipsis and a sphere). It has nontrivial solutions whenever the singular values have min at most one and max at least one. A rational parametrization (impossible?) is very difficult, but it’s not too hard to project into the axis of the lowest singular value which will give you an ellipsoid that you can inverse project onto 2 pieces on the sphere.
– Eric
May 26, 2021 at 3:18

## 1 Answer

Consider the system

$$\left\{ \begin{matrix} \sigma_1^2|y_1|^2+\sigma_2^2|y_2|^2+\ldots+\sigma_n^2|y_n|^2=1 \\ |y_1|^2+|y_2|^2+\ldots+|y_n|^2=1 \end{matrix}\right.$$

Let $$\sigma_i=\max\{\sigma_1,\ldots,\sigma_n\}$$ and $$\sigma_j=\min\{\sigma_1,\ldots,\sigma_n\}$$.

We are assuming that $$\sigma_i^2>1>\sigma_j^2\geq0$$.

We can rewrite this system as

$$\left\{ \begin{matrix} \sigma_i^2|y_i|^2+\sigma_j^2|y_j|^2=1-\sum_{l\neq i,j}\sigma_l^2|y_l|^2\\ |y_i|^2+|y_j|^2=1-\sum_{l\neq i,j}|y_l|^2 \end{matrix}\right.$$

By Cramer's rule, we obtain

$$|y_j|^2=\det\begin{pmatrix}\sigma_i^2 & 1-\sum_{l\neq i,j}\sigma_l^2 |y_l|^2\\ 1 & 1-\sum_{l\neq i,j}|y_l|^2\end{pmatrix}/\det\begin{pmatrix}\sigma_i^2 & \sigma_j^2\\ 1 & 1\end{pmatrix}$$ and $$|y_i|^2=\det\begin{pmatrix}1-\sum_{l\neq i,j}\sigma_l|y_l|^2 & \sigma_j^2\\ 1-\sum_{l\neq i,j}|y_l|^2 & 1\end{pmatrix}/\det\begin{pmatrix}\sigma_i^2 & \sigma_j^2\\ 1 & 1\end{pmatrix}$$.

Notice that

1. $$\det\begin{pmatrix}\sigma_i^2 & \sigma_j^2\\ 1 & 1\end{pmatrix}=\sigma_i^2-\sigma_j^2>0$$
2. $$\det\begin{pmatrix}\sigma_i^2 & 1-\sum_{l\neq i,j}\sigma_l^2|y_l|^2\\ 1 & 1-\sum_{l\neq i,j}x_l^2\end{pmatrix}=\sigma_i^2-1+\sum_{l\neq i,j}(\sigma_l^2-\sigma_i^2)|y_l|^2$$.

Since $$\sigma_l^2-\sigma_i^2\leq 0$$ e $$0<\sigma_i^2-1$$, we can find a solution when $$\sum_{l\neq i,j}(\sigma_i^2-\sigma_l^2)x_l^2\leq \sigma_i^2-1.$$

1. $$\det\begin{pmatrix}1-\sum_{l\neq i,j}\sigma_l^2|y_l|^2 & \sigma_j^2\\ 1-\sum_{l\neq i,j}|y_l|^2 & 1\end{pmatrix}=1-\sigma_j^2+\sum_{l\neq i,j}(\sigma_j^2-\sigma_l^2)|y_l|^2$$.

Since $$\sigma_j^2-\sigma_l^2\leq 0$$ e $$0<1-\sigma_j^2$$, we can find a solution when $$\sum_{l\neq i,j}(\sigma_l^2-\sigma_j^2)|y_l|^2\leq 1-\sigma_j^2.$$