The following is an interview question.
Given three random variables $X,Y,Z$ and $a,b,c,$ find the minimum value of $Var(aX+bY+cZ)$ subject to the constraint $a^2+b^2+c^2 = 1.$
I solved the problem using Lagrangian multiplier. But the interviewer said it is too tedious and time consuming as we need to solve a lot of equations. In this case, there are $4$.
He suggested the following:
Observe that
$$Var(aX+bY+cZ) = \begin{pmatrix}
a & b & c
\end{pmatrix} \begin{pmatrix}
Var(X) & Cov(X,Y) & Cov(X,Z) \\
Cov(X,Y) & Var(Y) & Cov(Y,Z) \\
Cov(X,Z) & Cov(Y,Z) & Var(Z) \\
\end{pmatrix} \begin{pmatrix}
a \\
b\\
c
\end{pmatrix}.$$
Since all symmetric matrix is diagonalizable, so
$$\begin{pmatrix}
Var(X) & Cov(X,Y) & Cov(X,Z) \\
Cov(X,Y) & Var(Y) & Cov(Y,Z) \\
Cov(X,Z) & Cov(Y,Z) & Var(Z) \\
\end{pmatrix} =
\begin{pmatrix}
– & v_1 & – \\
– & v_2 & – \\
– & v_3 & –
\end{pmatrix}
\begin{pmatrix}
\lambda_1 & 0 & 0 \\
0 & \lambda_2 & 0 \\
0 & 0 & \lambda_3
\end{pmatrix}
\begin{pmatrix}
| & | & | \\
v_1 & v_2 & v_3\\
| & | & |
\end{pmatrix}
$$
where $\lambda_1,\lambda_2, \lambda_3$ are eigenvalues of the covariance matrix with eigenvectors $v_1,v_2,v_3$ respectively.
The interviewer said that from here, it should be easy to see that the minimum occurs at the eigenvector corresponding to the smallest eigenvalue.
But I do not see how to deduce it from equations above.
Best Answer
Let $\Sigma$ be the $3\times 3$ covariance matrix. It can be written as $\Sigma = V\Lambda V^\top$ where $\Lambda$ is diagonal with entries $\lambda_1, \lambda_2, \lambda_3$, and where the columns of $V$ are orthonormal eigenvectors (i.e. $V$ is an orthogonal matrix). (Note that in your question, you or your interviewer mixed up $V$ and $V^\top$.)
You want to find the vector $u$ that minimizes $u^\top \Sigma u$ subject to $\|u\|^2 = 1$.
Consider the similar problem of minimizing $w^\top \Lambda w$ subject to $\|w\|^2 = 1$. Since $w^\top \Lambda w = \lambda_1 w_1^2 + \lambda_2 w_2^2 + \lambda_3 w_3^2$, you can check that the best choice of $w$ is $\begin{bmatrix}1 \\ 0 \\ 0 \end{bmatrix}$ if $\lambda_1$ is the smallest eigenvalue, $\begin{bmatrix}0 \\ 1 \\ 0 \end{bmatrix}$ if $\lambda_2$ is the smallest eigenvalue, and so on. And the minimized value of $w^\top \Lambda w$ is the smallest eigenvalue.
Let us return to the original problem of minimizing $u^\top \Sigma u$. This objective function can be written as $u^\top V \Sigma V^\top u$. Note that $\|V^\top u\| = \|u\|$ because $V$ is an orthogonal matrix. So we can reduce the problem to the second type (with the "change of variables" $w= V^\top u$) and see that this problem also has minimum value equal to the smallest eigenvalue.