21
$\begingroup$

Let $A \in \mathbb{R}^{n \times n}$ be a given symmetric positive definite matrix. I would like to find the maximal rotation $A$ can create over any unit vector $x \in \mathbb{R}^n$. In other words, the minimum value of (or a lower bound on) \begin{align*} \frac{x^\top A x}{\|x\|_2 \| Ax\|_2} = \frac{\sum_{i} \lambda_i \alpha_i}{\sqrt{\sum_i \lambda^2_i \alpha_i}} \end{align*} over $\alpha_i$, where $\lambda_i$ is the $i$th largest eigenvalue of $A$, and $\alpha_i \geq 0, \sum_i \alpha_i = 1$ (where we defined $\alpha_i= (Q^\top x)^2_i$, where $A$ has eigendecomposition $A=Q\Lambda Q^\top$.

Clearly, any eigenvector of $A$ creates no rotation (i.e. maximizes the above ratio), so intuitively the minimizing $x$ needs to be away from the eigenvectors. I tried writing down the Lagrangian, but could not reach anywhere.

$\endgroup$
  • 1
    $\begingroup$ If $n=2$, then the minimum is attained at $\alpha_1=\lambda_2/(\lambda_1+\lambda_2)$ and $\alpha_2=\lambda_1/(\lambda_1+\lambda_2)$ and is equal to $$\frac{2\sqrt{\lambda_1 \lambda_2}}{\lambda_1+\lambda_2}$$ $\endgroup$ – san May 14 '17 at 2:55
  • 1
    $\begingroup$ You can just assume that $A$ is diagonal. Then work at the cases $n=3$ and $n=4$ and see if there is some pattern. $\endgroup$ – san May 14 '17 at 2:56
  • 2
    $\begingroup$ @san Interesting to see that the minimum is the ratio of the geometric and arithmetic means of the eigenvalues — at least for $n=2$. $\endgroup$ – Rodrigo de Azevedo May 14 '17 at 9:39
9
+50
$\begingroup$

A few days after asking the question, I was able to solve this. Since it seems that there is general interest, I am posting the answer. @san's answer holds in arbitrary dimensions.

Let $\kappa$ be the condition number of $A$, i.e., $\kappa := \frac{\lambda_{\max}(A)}{\lambda_{\min}(A)}$.

Let $\mathcal{W}$ be the subspace spanned by $\{ x, Ax \}$, and let $W \in \mathbb{R}^{d \times 2}$ be a matrix whose columns form an orthonormal basis for $\mathcal{W}$. Then $x$ and $Ax$ can be represented as \begin{align*} x &= Wr_1 \\ Ax &= Wr_2, \end{align*} which implies \begin{align*} r_2 = W^\top A W r_1 = Q^\top D Q r_1, \end{align*} where since $W^\top A W$ is still a positive definite matrix it has the $2\times 2$ eigendecomposition $Q^\top D Q$. Defining $q_i = Qr_i$ for $i=1,2$, note that the quantity we are interested in can be equivalently represented as \begin{align*} \frac{x^\top Ax}{\| Ax\|} = \frac{r_1^\top r_2}{\| r_2\|} = \frac{q_1^\top q_2}{\| q_2\|}, \end{align*} where $q_2 = Dq_1$. Further note that for any unit vector $v$, \begin{align*} v^\top D v = v^\top Q^\top D Qv = v^\top W^\top A W v, \end{align*} and since $\| Wv\|=1$, the eigenvalue ratio (the ratio of the two non-zero elements of $D$) of $D$ cannot be larger than the largest possible eigenvalue ratio of $A$, which is $\kappa$.

[To see this, assume the contrary, i.e., $\frac{d_2}{d_1}>\kappa$. Then one can choose $v_1 = [1\;\;0]$, and $v_2 =[0\;\;1]$ respectively, to get $\frac{v_1^\top A v_1}{v_2^\top A v_2} > \kappa$, which means there exists unit vectors $u_1 = Wv_1$ and $u_2 = Wv_2$ such that $\frac{u_1^\top A u_1}{u_2^\top A u_2} > \kappa$, which is a contradiction since $u_1^\top A u_1 \leq \lambda_{\max}$, $u_2^\top A u_2 \geq \lambda_{\min}$, and $\frac{\lambda_{\max}}{\lambda_{\min}} =\kappa$.]

Representing $q_1 = [ \cos\phi \;\; \sin\phi]^\top$ for some angle $\phi$, $\frac{q_2}{\| q_2 \|}$ can then be written as $q_2 = \left[ \frac{d_1}{\sqrt{d_1^2 + d_2^2}} \cos \phi \;\; \frac{d_2}{\sqrt{d_1^2 + d_2^2}} \sin \phi\right]^\top$, where $d_1$ and $d_2$ are the two diagonal elements of $D$. Note that minimizing the inner product $\frac{q_1^\top q_2}{\| q_2\|}$ is equivalent to maximizing the function \begin{align*} \tan\left( \tan^{-1}\left( \frac{d_2}{d_1} \tan \phi\right)- \phi\right) = \frac{\left(\frac{d_2}{d_1} - 1\right) \tan \phi}{1 + \frac{d_2}{d_1} \tan^2 \phi} \end{align*} over $\phi$. By setting the derivative to zero, we find that the minimizing $\phi$ is given by $\cos^{-1} \left(\frac{d_2-d_1}{d_2+d_1}\right)$. Therefore \begin{align*} \frac{x^\top Ax}{\| Ax\|} = \frac{q_1^\top q_2}{\| q_2\|} = \frac{d_1}{\sqrt{d_1^2 + d_2^2}} \cos^2 \phi + \frac{d_2}{\sqrt{d_1^2 + d_2^2}} \sin^2 \phi \geq \frac{2\sqrt{\frac{d_2}{d_1}}}{1 + \frac{d_2}{d_1}} \geq \frac{2\sqrt{\kappa}}{1 + \kappa}. \end{align*}

Edit: As @san suggested, this lower bound is achieved when $\alpha_1 = \frac{1}{\kappa+1}$, $\alpha_n = \frac{\kappa}{\kappa+1}$, and $\alpha_i = 0$ for $1 <i <n$.

$\endgroup$
  • 2
    $\begingroup$ I have two questions. 1) $v^\top W^\top M W v$ should really be $v^\top W^\top A W v$, right ? 2) Could you elaborate on why "the eigenvalue ratio of $D$ cannot be larger than the largest possible eigenvalue ratio of $A$" ? The only thing I see is that any eigenvalue of $D$ can be written $v^\top W^\top A W v$ for some $v$, but how do we relate that to the eigenvalues of $A$ ? $\endgroup$ – Ewan Delanoy May 15 '17 at 6:56
  • 2
    $\begingroup$ And the minimum is attained at $\alpha_1=1/(1+k)$, $\alpha_n=k/(1+k)$ and $\alpha_k=0$ for $k=2,\dots,n-1$. $\endgroup$ – san May 15 '17 at 15:11
  • 1
    $\begingroup$ @EwanDelanoy 1) Yes, I corrected this typo. 2) I have now added an explanation of why that is the case. $\endgroup$ – karakusc May 16 '17 at 2:42

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.