Let $X$ be some matrix, with dimensions $n \times m$, $Y$ be the independent columns of $X$, and $\bf{z}$ be a vector with dimension that is $n \times 1$ that lies on the unit sphere, that is, $||z|| = 1$. I want to find the maximum value of $||Y^T\bf{z}||^2$. I know the answer to the question relies on knowing the eigenvalues of $YY^T$, but I don't see how eigenvalues relate to maximum distances which I (assume) is what this question is about. I'm wondering if anyone can shed some light on how to get started with a question like this?

  • $\begingroup$ you might want to read about rayleigh ritz ratios after reading user copper.hat's answer. $\endgroup$ – dineshdileep Oct 11 '13 at 7:00

Presumably you are dealing with the Euclidean norm.

You have $\|Y^T z\|^2 = \langle Y^T z, Y^T z \rangle = \langle z, YY^T z \rangle$.

$YY^T$ is symmetric and positive semi-definite, and the maximum value of $\langle z, YY^T z \rangle$ for $\|z\| \le 1$ is given by the maximum eigenvalue of $Y Y^T$ (this can be seen since $YY^T$ can be diagonalized with an orthogonal matrix).

Relevant facts:

If $Q$ is an orthogonal matrix, then $\|Q x\| = \|x\|$.

If $A$ is symmetric and can be diagonalized with an orthogonal matrix, then $\lambda_{\text{min}} \|x\|^2 \le \langle x, Ax \rangle \le \lambda_{\text{max}} \|x\|^2$. To see this, suppose $A = Q \Lambda Q^T$, where $Q$ is an orthogonal and $\Lambda = \operatorname{diag}(\lambda_1,...,\lambda_n)$. Then $\langle x, Ax \rangle = \langle Q^Tx, \Lambda (Q^Tx) \rangle = \sum_k \lambda_k [Q^Tx]_k^2$. Then it is easy to see that $\lambda_{\text{min}} \sum_k [Q^Tx]_k^2 \le \langle x, Ax \rangle \le \lambda_{\text{max}} \sum_k [Q^Tx]_k^2 $, and since $\sum_k [Q^Tx]_k^2 = \|Q^T x\|^2 = \|x\|^2$, we have the desired result. (Also, the bounds are achieved for the appropriate corresponding eigenvector.)

  • $\begingroup$ Did you mean to say $\|Y^T z\|^2 = \langle Y^T z, Y^T z \rangle = \langle z, YY^T z \rangle$? $\endgroup$ – Ken Li Oct 11 '13 at 17:12
  • $\begingroup$ @KenLi: Indeed I did, thanks. $\endgroup$ – copper.hat Oct 11 '13 at 18:41

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.