Maximum angle between a vector $x$ and its linear transformation $A x$

Solution 1:

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