24
$\begingroup$

$\newcommand{\GLp}{\operatorname{GL}_n^+}$ $\newcommand{\SLs}{\operatorname{SL}^s}$ $\newcommand{\dist}{\operatorname{dist}}$ $\newcommand{\Sig}{\Sigma}$ $\newcommand{\id}{\text{Id}}$ $\newcommand{\SOn}{\operatorname{SO}_n}$ $\newcommand{\SOtwo}{\operatorname{SO}_2}$ $\newcommand{\GLtwo}{\operatorname{GL}_2^+}$

I am trying to find the Euclidean distance between the set of matrices of constant determinant and $\SOn$, i.e calculating $$ F(s)= \min_{A \in \GLp,\det A=s} \dist^2(A,\SOn). $$

Since the problem is $\SOn$-invariant we can effectively work with SVD; Using geometric reasoning, we can reduce the problem to diagonal matrices with at most two distinct values for its entries:

Indeed, denote by $\SLs$ the submanifold of matrices with determinant $s$; Let $\Sig \in \SLs$ be a closest matrix to $\SOn$. By orthogonal invariance, we can assume $\Sig$ is positive diagonal. Then its unique closest matrix in $\SOn$ is the identity. Consider the minimizing geodesic between $I,\Sig$: $$ \alpha(t) =\id+t(\Sig-\id). $$ Since a minimizing geodesic to a submanifold is orthogonal to it, we have $$\dot \alpha(1) \in (T_{\Sig}SL^{s})^{\perp}=(T_{(\sqrt[n]s)^{-1}\Sig}SL^{1})^{\perp}=\big((\sqrt[n]s)^{-1}\Sig T_{\id}SL^{1}\big)^{\perp}=\big(\Sig \text{tr}^{-1}(0)\big)^{\perp}.$$

Since $\Sig^{-1} \in \big(\Sig \text{tr}^{-1}(0)\big)^{\perp} $ is a basis for $\big(\Sig \text{tr}^{-1}(0)\big)^{\perp}$, we deduce

$$ \Sig-\id=\dot \alpha(1)=\lambda \Sig^{-1} \, \, \text{for some} \, \, \lambda \in \mathbb{R}, \, \text{i.e}$$

$$ \sigma_i-1=\frac{\lambda}{\sigma_i} \Rightarrow \sigma_i^2-\sigma_i-\lambda=0.$$ We see from the equation that if $\sigma_i$ is a solution, then so it $1-\sigma_i$, so if we denote by $a$ one root, the other must be $1-a$.

We just proved $\{\sigma_1,\dots,\sigma_n\} \subseteq \{a,1-a \}$.

Moreover, if the closest matrix $\Sigma$ does indeed have two distinct diagonal values, then they must be of the form $a,1-a$; Since both are positive, this implies $0<a<1$. So, we can assume WLOG that $a<\frac{1}{2}$.


So, we are led to the following optimization problem:

$$ F(s)=\min_{a \in (0,\frac{1}{2}),a^k(1-a)^{n-k}=s,0 \le k \le n, k \in \mathbb{N}} k(a-1)^2+(n-k)a^2. \tag{1}$$

I solved some special case below, but I don't see a good way to solve the general problem.

Partial results so far:

  1. By letting $k=0$ (or $k=n$) we get $F(s) \le n(\sqrt[n]s-1)^2$. This bound can always be realized by a conformal matrix.
  2. $F$ decreases with the dimension: Denote by $F_n$ the function which corresponds to dimension $n$; By taking the last singular value to be $1$, we see that $F_{n+1} \le F_n$ for any $n$. In particular $F_{n} \le F_2$. ($F_2$ is computed explicitly below). Is the decrease strict?

  3. In dimension $2$, a phase transition occurs: I prove below that

$$F(s) = \begin{cases} 2(\sqrt{s}-1)^2, & \text{ if }\, s \ge \frac{1}{4} \\ 1-2s, & \text{ if }\, s \le \frac{1}{4} \end{cases}$$

In other words, for $A \in \GLtwo$, $$ \dist^2(A,\SOtwo) \ge \begin{cases} 2(\sqrt{\det A}-1)^2, & \text{ if }\, \det A \ge \frac{1}{4} \\ 1-2\det A, & \text{ if }\, \det A \le \frac{1}{4} \end{cases}. $$ When $\det A \ge \frac{1}{4}$ equality holds if and only if $A$ is conformal. When $\det A < \frac{1}{4}$ equality does not hold when $A$ is conformal: The closest matrices to $\SOtwo$ with a given determinant $s=\det A$ (up to compositions with elements in $\SOtwo$) are

$$ \begin{pmatrix} \frac{1}{2} + \frac{\sqrt{1-4\det A}}{2} & 0 \\\ 0 & \frac{1}{2} - \frac{\sqrt{1-4\det A}}{2} \end{pmatrix}, \begin{pmatrix} \frac{1}{2} - \frac{\sqrt{1-4\det A}}{2} & 0 \\\ 0 & \frac{1}{2} + \frac{\sqrt{1-4\det A}}{2} \end{pmatrix} $$

when $\det A < \frac{1}{4}$, and

$$ \begin{pmatrix} \sqrt{\det A} & 0 \\\ 0 & \sqrt{\det A} \end{pmatrix} $$

when $\det A \ge \frac{1}{4}$.


Edit:

  1. By Tim's answer below, we know that if the minimizer is not conformal, then one value $0<a<\frac{1}{2}$ shows one time, and the other value (which is $1-a$) shows $n-1$ times. Since $$\max_{a \in (0,1)}a(1-a)^{n-1}=\frac{1}{n}(1-\frac{1}{n})^{n-1},$$ we deduce that if $s > \frac{1}{n}(1-\frac{1}{n})^{n-1}$ the minimizer is conformal (the other candidate "$a,1-a$" does not exist). Tim also showed that if $s \le (\frac{1}{2})^n$ then the minimizer is not conformal. It remains to determine what happens when $(\frac{1}{2})^n <s<\frac{1}{n}(1-\frac{1}{n})^{n-1}$.

  2. Even in the case $s \le (\frac{1}{2})^n$, we do not have an explicit expression for the minimal value $F(s)$. Can we obtain such an expression? or an estimate? This amounts to estimating the smallest* root of the equation $a(1-a)^{n-1}=s$ (or equivalently finding the unique root in $(0,\frac{1}{n})$).

See here.

*Tim also showed that the winning root is the smallest one.


Analysis of the case when $n$ is even and $n=2k$:

Claim:

$$ \text{Let } \, \,F(s)=\min_{a,b \in \mathbb{R}^+,a^{\frac{n}{2}}b^{\frac{n}{2}}=s} \frac{n}{2} \big( (a-1)^2+(b-1)^2 \big). \tag{2}$$ Then $$F(s) \le f(s) := \begin{cases} n(\sqrt[n]s-1)^2, & \text{ if }\, s^{\frac{2}{n}} \ge \frac{1}{4} \\ \frac{n}{2}(1-2s^{\frac{2}{n}}), & \text{ if }\, s^{\frac{2}{n}} \le \frac{1}{4} \end{cases}$$

Expressing the constraint as $g(a,b)=ab-s^{\frac{2}{n}}=0$, and using Lagrange's multipliers method we see that there exist a $\lambda$ such that

$$ (2(a-1),2(b-1))=\lambda \nabla g(a,b)=\lambda(b,a)$$ so $a-1=\frac{b}{2}\lambda,b-1=\frac{a}{2}\lambda$.

Summing, we get $$ (a+b)-2=\frac{\lambda}{2}(a+b) \Rightarrow (a+b) (1-\frac{\lambda}{2})=2.$$ This implies $\lambda \neq 2$, so we divide and obtain $$ a+b=\frac{4}{2-\lambda} \Rightarrow a=\frac{4}{2-\lambda}-b. \tag{3}$$ So, $$a-1=\frac{4}{2-\lambda}-b-1=\frac{b}{2}\lambda \Rightarrow b(\frac{2+\lambda}{2})=\frac{2+\lambda}{2-\lambda} .$$

If $\lambda \neq -2$, then $b=\frac{2}{2-\lambda}$, which together with equation $(3)$ imply $a=b$.

Suppose $\lambda=-2$. Then $a=1-b$, so $s^{\frac{2}{n}}=ab=b(1-b)$. Since $a=1-b,b,s$ are positive we must have $0<b<1,0<s^{\frac{2}{n}}\le\frac{1}{4}$. (Since $\max_{0<b<1} b(1-b)=\frac{1}{4}$).

In that case, $$ \frac{n}{2} \big( (a-1)^2+(b-1)^2 \big) =\frac{n}{2} \big( b^2+(b-1)^2 \big)=\frac{n}{2} \big( 1-2b(1-b) \big)=\frac{n}{2}(1-2s^{\frac{2}{n}}).$$

Since $$\frac{n}{2}(1-2s^{\frac{2}{n}}) \le n(\sqrt[n]s-1)^2,$$ with equality holds iff $s^{\frac{2}{n}}=\frac{1}{4}$ we are done.

The conclusion for the $2$-dim case is immediate.

$\endgroup$
  • $\begingroup$ Why must the closest matrix have at most two unique values? Maybe the proof of this will shed light on what value for k is optimal? I agree that the expressions for fixed k seem to be too messy to compare with each other, but if we could narrow it down to a few possibilities, then it might not be so bad. $\endgroup$ – Noah Stephens-Davidowitz Aug 13 '17 at 23:40
  • $\begingroup$ I actually added the proof of the reduction to "two values only" an hour ago:) My original proof for that was via Lagrange's multipliers, but the new proof I found is much more geometric. To summarize, the reduction uses all the "geometric insight" I could come up with about the problem. (The orthogonality of a minimizing geodesic to both submanifolds at the intersection point). Unfortunately, I do not see any more information we could get from this proof. $\endgroup$ – Asaf Shachar Aug 14 '17 at 0:49
12
+50
$\begingroup$

(Basically) Full answer

  • For $s \geq 1$ we always take the matrix with diagonals $s^{1/n}$.
  • For $s < 1$ and we have two possibilities. For $n$ small enough we take (still) the matrix with diagonals $s^{1/n}$. For $n$ large enough we instead solve $$a(1-a)^{n-1} = s$$ and take the smaller of the (at most two) solutions. The optimizer will be the matrix with one diagonal $a$ and the rest $1-a$. (Note for $s$ small enough we will have $a \approx s$ and $dist \approx 1$.

Intuitive optimizers

First, to get some intuition for the problem realize that the behavior of the solution is going to depend on $s$. If $s$ is very large, then it is best to take all the eigenvalues equal. This is easy to visualize: the closest point on the graph of $xyz=1000$ to $(1,1,1)$ is $(10,10,10)$. enter image description here

On the other hand, if $s$ is very small then taking all the values the same gives a distance of about $n$. By taking one eigenvalue to be $s$ and the rest to be $1$ we can have a distance of $1$ from the identity.

Dimensionless problem

We pick up from your optimization problem (1). It is convenient to write $\alpha = k/n$ and $L = \log(s)/n$ so that your optimization problem is equivalent to minimizing $$G(a,b,\alpha) = \alpha (a-1)^2 + (1-\alpha) (b-1)^2$$ over the set $$H(a,b,\alpha) = L, \quad a>0,\quad b>0,\quad \alpha \in [0,1], \quad n\alpha \in \mathbb{N}$$ where $H(a,b,\alpha)$ is $$H(a,b,\alpha) = \alpha \log (a) + (1-\alpha) \log (b).$$

We can perform the method of Lagrange multipliers in the $a$ and $b$ coordinates. This will give us that either $b=a$ or $b = (1-a)$. A more direct path to this result is to observe in your equation $$\sigma^2 - \sigma - \lambda = 0 \text{ for some } \lambda \in \mathbb{R}$$ we have that if $\sigma$ is a solution, so is $(1-\sigma)$.

The easy competitor

Now if $a = b$ then $\alpha$ is irrelevant, and we have the first competitor to the minimization $$a = b = e^L, \quad \alpha = \text{anything}, \quad dist = (e^L-1)^2$$

The harder competitor The case $b = 1-a$ is harder to analyze. First note that for this solution we must restrict to $a < 1$. Given that $b = 1-a$ we can rewrite our optimization as minimizing $$\alpha (a-1)^2 + (1-\alpha)a^2 $$ over the set \begin{equation}\tag{1} \alpha \log(a) + (1 - \alpha) \log(1-a) = L \end{equation} \begin{equation} \tag{2} a \in (0,1/2), \quad a \leq \min(e^L, 1-e^L), \quad n\alpha \in \mathbb{N} \end{equation} The first constraint above comes from assuming (WLOG) $a$ is smaller than $b$. The second is from observing that $L$ is a convex combination of $\log a$ and $\log (1-a)$ so $\log (a) \leq L \leq \log(1-a)$.

To simplify, we can solve the constraint $\alpha \log a + (1-\alpha)\log (1-a)$ for $\alpha$: \begin{equation} \tag{3} \alpha = \frac{L - \log(1-a)}{\log(a) - \log(1-a)} \end{equation} and now rewrite our minimization as: minimize $$f(a) = \frac{(L - \log(1-a))(1-a)^2 + (\log(a)-L)a^2}{\log(a)-\log(1-a)}$$ over $$a \in (0, \min(e^L, 1-e^L)), \quad n\alpha \in \mathbb{N}$$

Now we claim the following three facts:

  1. $f(a)$ as zero or one critical points
  2. $\lim_{a \to 0}f(a) = 0$
  3. $f(e^L) = f(1-e^L) = (e^{L}-1)^2$

Given these three facts we see that if we forget the condition $n \alpha \in \mathbb{N}$ from our constraints we see that the infimum of $f$ is $0$ which is not realized for $a > 0$. The function $f(a)$ either looks like enter image description here or enter image description here (These are L = -1/5 and -3.) The red line in these pictures is the value from taking the matrix of diagonals, (e^L - 1)^2.

If we now enforce the discrete condition $n \alpha \in \mathbb{N}$ we see that it suffices to check the smallest $a$ possible against $(e^L -1 )^2$.

Checking these facts I checked items 2 and 3 with a CAS. For item 1 I did the following. First implicitly differentiate the constraint (1) with respect to $a$ to find $$ \frac{d\alpha}{da} \left(\log a - \log(1-a) \right) = - \left(\frac{\alpha}{a} - \frac{1-\alpha}{1-a} \right) $$ Then differentiate $f$ and set it to zero to find $$ 2 (a - \alpha) \left(\log a - \log(1-a) \right) = (-2a + 1) \left( \frac{\alpha}{a} - \frac{1-\alpha}{1-a} \right) $$ Multiply by $a(1-a)$ to find $$ 2a(1-a)(a-\alpha) \left( \log a - \log(1-a) \right) = (-2a+1) \left(\alpha - a \right) $$ If $\alpha \neq a$ we can divide by $\alpha-a$ and find (checking that there's only one solution) $a = 1/2$. This is disallowed by our constraints (2). On the other hand, we have a solution if $\alpha = a$. Then, check that there is at most one solution to (1) with $\alpha = a$.

Add-on: I will write what I know about $f(a)$ more precisely.

  • For $L \geq \log (1/2)$ there is a solution to the constraint $\alpha \log a + (1-\alpha) \log (1-a) = L$ with $a= \alpha$. Equivalently, for $1/2 \leq y < 1$ there is a solution to $\frac{a^a}{(1-a)^{1-a}} = y$. There are actually two solutions on $[0, 1]$ related by $a_1 = 1-a_2$, so since we enforce $a<1/2$ there is only one solution on our domain for $a$.

  • For $L < \log (1/2)$ there is no solution with $a = \alpha$.

  • This means that $f$ as a function of $a$ has a critical point if $L \geq \log(1/2)$, namely where $a = \alpha$. If $L \leq \log(1/2)$ there is no critical point.

Edit: Here are some pictures for why the smallest value of $a$ below does always corresponds to the smallest value of $\alpha$. I think it's helpful to visualize first. Here is $\alpha$ as a function of $a$ for $L = \log(.99)$, $L = \log(.51)$, $L = \log(1/2)$, and $L = \log(.49)$.

$L = \log(.99)$ enter image description here $L = \log(.51)$ enter image description here $L = \log(.5)$ enter image description here $L = \log(.49)$ enter image description here

If $L \leq \log(1/2)$ then $\alpha$ as a function of $a$ has no critical points and is increasing (similar reasoning as with $f(a)$). Therefore taking the smallest possible $\alpha$ gives you the smallest possible $a$.

If $L > \log(1/2)$ then for $a \in [0, 1-e^{L}] = [0, min(e^L, 1-e^L)]$, $\alpha$ has a single critical point, a maximum, and is zero at the endpoints. Therefore, we can (mistakenly) choose $\alpha = 1/1000$ and then take $a$ to be large. But, you can visualize all allowable values of $a$ by drawing a discrete collection of horizontal lines on this picture (here's $L = log(.51), n=10$): enter image description here The possible choices of $a$ in our discrete set are given by intersections of the red lines with our blue curve, by the nature of the function each red line has two intersections with the blue curve. The lowest red line has both the smallest and largest value of $a$. This picture also illustrates how to find the counterexample to your stackexchange question.

$\endgroup$
  • 1
    $\begingroup$ Many thanks for your effort. I still have some questions: (1) Why facts $(1)-(3)$ imply the smallest $a$ possible (which makes $n\alpha$ an integer) is the only relevant candidate? If I understood correctly $f(a)$ might increase up to its critical point, then decrease after it. The minimum point can be after the critical point, right? (2) In the expression for the derivative of the constraint, I think it should be $\frac{d\alpha}{da} \left(\log a - \log(1-a) \right) = - \left(\frac{\alpha}{a} -\frac{1-\alpha}{1-a} \right)$ right? (There is a minus sign missing). $\endgroup$ – Asaf Shachar Aug 29 '17 at 13:55
  • 1
    $\begingroup$ (1) If $f(a)$ is strictly increasing it's clear we want to take the smallest $a$ possible. Now, suppose that $f'(a)$ changes sign at some point $a_*$. Then, on $[a_*, min(e^L, e^{1-L})]$ we will have $f(a)$ decreasing, and so $f(a) > (e^L-1)^2$ by fact (3). So, if you take anything after $a_*$ you're not going to do better than the easy competitor of a diagonal matrix. If you take anything before $a_*$ you want to take the smallest possible $a_*$. (2) You were right about the sign, I fixed it. $\endgroup$ – Tim Carson Aug 29 '17 at 14:17
  • $\begingroup$ Thanks, it's clear now. Something else bothers me now: How do you conclude that taking the smallest possible $a$, amounts to choosing one value $(a)$ once, and the other value $(1-a)$ $n-1$ times? This does not seem to be true, see here. Thanks for your patience. $\endgroup$ – Asaf Shachar Aug 29 '17 at 17:24
  • $\begingroup$ Good point, that is not to trivial to check. See the edit. At this point I've been loose with what I've done by hand and done by CAS and done by numerical computation, but I hope everything can be checked by hand. $\endgroup$ – Tim Carson Aug 29 '17 at 19:30
  • 1
    $\begingroup$ Here's why if $s \geq 1$ the diagonal matrices win. Recall that lagrange multipliers told us that for any $\alpha$, the only possibilities are $a = b$ or $a = 1-b$. Since $a$ and $b$ are positive, if the second solution exists then $a$ and $b$ are less than 1. Then we find that $H(a,b,\alpha)$ is negative, so $\log(s^{1/n})$ is negative, so $s < 1$. $\endgroup$ – Tim Carson Aug 29 '17 at 21:52

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.