Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It only takes a minute to sign up.
Sign up to join this community
I was asked the following question in an interview.
Let's say we have a correlation matrix of the form
\begin{bmatrix}1&0.6&0.8\\0.6&1&\gamma\\0.8&\gamma&1\end{bmatrix} Find the value of $\gamma$.
I thought I could do something with the eigenvalues, since they should be all greater than or equal to $0$ — the matrix should be positive semidefinite — but I don't think this approach will yield the answer. I am missing a trick. Could you please provide a hint to solve for the same?
We already know $\gamma$ is bounded between $[-1,1]$ The correlation matrix should be positive semidefinite and hence its principal minors should be nonnegative
Thus, \begin{align*} 1(1-\gamma^2)-0.6(0.6-0.8\gamma)+0.8(0.6\gamma-0.8) &\geq 0\\ -\gamma^2+0.96\gamma \geq 0\\ \implies \gamma(\gamma-0.96) \leq 0 \text{ and } -1 \leq \gamma \leq 1 \\ \implies 0 \leq \gamma \leq 0.96 \end{align*}
Here's a simpler (and perhaps more intuitive) solution:
Think of the covariance as an inner product over an abstract vector space. Then, the entries in the correlation matrix are $\cos\langle\mathbf{v}_i,\mathbf{v}_j\rangle$ for the vectors $\mathbf{v}_1$, $\mathbf{v}_2$, $\mathbf{v}_3$, where the angle bracket $\langle\mathbf{v}_i,\mathbf{v}_j\rangle$ denotes the angle between $\mathbf{v}_i$ and $\mathbf{v}_j$.
It is not hard to visualize that $\langle\mathbf{v}_2,\mathbf{v}_3\rangle$ is bounded by $|\langle\mathbf{v}_1,\mathbf{v}_2\rangle\pm\langle\mathbf{v}_1,\mathbf{v}_3\rangle|$. The bound on its cosine ($\gamma$) is thus $\cos\left[\langle\mathbf{v}_1,\mathbf{v}_2\rangle\pm\langle\mathbf{v}_1,\mathbf{v}_3\rangle\right]$. Basic trigonometry then gives $\gamma\in[0.6\times 0.8 - 0.6\times 0.8, 0.6\times 0.8 + 0.6\times 0.8] = [0, 0.96]$.
Edit: Note that the $0.6\times 0.8 \mp 0.6\times 0.8$ in the last line is really $\cos\langle\mathbf{v}_1,\mathbf{v}_2\rangle\cos\langle\mathbf{v}_1,\mathbf{v}_3\rangle\mp \sin\langle\mathbf{v}_1,\mathbf{v}_3\rangle\sin\langle\mathbf{v}_1,\mathbf{v}_2\rangle$ -- the second appearance of 0.6 and 0.8 occurs by coincidence thanks to $0.6^2+0.8^2=1$.
Let us consider the following convex set
$$\Bigg\{ (x,y,z) \in \mathbb R^3 : \begin{bmatrix} 1 & x & y\\ x & 1 & z\\ y & z & 1\end{bmatrix} \succeq \mathrm O_3 \Bigg\}$$
which is a spectrahedron named $3$-dimensional elliptope. Here's a depiction of this elliptope
Intersecting this elliptope with the planes defined by $x=0.6$ and by $y=0.8$, we obtain a line segment whose endpoints are colored in yellow
The boundary of the elliptope is a cubic surface defined by
$$\det \begin{bmatrix} 1 & x & y\\ x & 1 & z\\ y & z & 1\end{bmatrix} = 1 + 2 x y z - x^2 - y^2 - z^2 = 0$$
If $x=0.6$ and $y=0.8$, then the cubic equation above boils down to the quadratic equation
$$0.96 z - z^2 = z (0.96 - z) = 0$$
Thus, the intersection of the elliptope with the two planes is the line segment parametrized by
$$\{ (0.6, 0.8, t) \mid 0 \leq t \leq 0.96 \}$$
Playing around with principal minors may be fine on 3 by 3 or maybe 4 by 4 problems, but runs out of gas and numerical stability in higher dimensions.
For a single "free" parameter problem such as this, it's easy to see that the set of all values making the matrix psd will be a single interval. Therefore, it is sufficient to find the minimum and maximum such values. This can easily be accomplished by numerically solving a pair of linear SemiDefinite Programming (SDP) problems:
For example, these problems can be formulated and numerically solved using YALMIP under MATLAB.
Fast, easy, and reliable.
BTW, if the smarty pants interviewer asking the question doesn't know that SemiDefinite Programming, which is well-developed and has sophisticated and easy to use numerical optimizers for reliably solving practical problems, can be used to solve this problem, and many much more difficult variants, tell him/her that this is no longer 1870, and it's time to take advantage of modern computational developments.
Here is what I meant in my initial comment to the answer and what I perceive @yangle may be speaking about (although I didn't follow/check their computation).
"Matrix should be positive semidefinite" implies the variable vectors are a bunch in Euclidean space. The case of correlation matrix is easier than covariance matrix because the three vector lengths are fixed to be 1. Imagine 3 unit vectors X Y Z and remember that $r$ is the cosine of the angle. So, $\cos \alpha=r_{xy}=0.6$, and $\cos \beta=r_{yz}=0.8$. What might be the boundaries for $\cos \gamma=r_{xz}$? That correlation can take on any value defined by Z circumscribing about Y (keeping angle $r_{yz}=0.8$ with it):
As it spins, two positions are remarkable as ultimate wrt X, both are when Z falls into the plane XY. One is between X and Y, and the other is on the opposite side of Y. These are shown by blue and red vectors. At both these positions exactly the configuration XYZ (correlation matrix) is singular. And these are the minimal and maximal angle (hence correlation) Z can attain wrt X.
Picking the trigonometric formula to compute sum or difference of angles on a plane, we have:
$\cos \gamma = r_{xy} r_{yz} \mp \sqrt{(1-r_{xy}^2)(1-r_{yz}^2)} = [0,0.96]$ as the bounds.
This geometric view is just another (and a specific and simpler in 3D case) look on what @rightskewed expressed in algebraic terms (minors etc.).
Every positive semi-definite matrix is a correlation/covariance matrix (and vice versa).
To see this, start with a positive semi-definite matrix $A$ and take its eigen-decomposition (which exists by the spectral theorm, since $A$ is symmetric) $A=UDU^T$ where $U$ is a matrix of orthonormal eigenvectors and $D$ is a diagonal matrix with eigen values on the diagonal. Then, let $B= U D^{1/2} U^T$ where $D^{1/2}$ is a diagonal matrix with the square root of eignevalues on the diagonal.
Then, take a vector with i.i.d. mean zero and variance 1 entries, $\mathbf{x}$ and note that $B \mathbf{x}$ also has mean zero, and covariance (and correlation) matrix $A$.
Now, to see every correlation/covariance matrix is positive semi-definite is simple: Let $R=E[\mathbf{x}\mathbf{x}^T]$ be a correlation matrix. Then, $R = R^T$ is easy to see, and $\mathbf{a}^T R \mathbf{a} = E[(\mathbf{a}^T \mathbf{x})^2] \geq 0$ so the Rayleigh quotient is non-negative for any non-zero $\mathbf{a}$ so $R$ is positive semi-definite.
Now, noting that a symmetric matrix is positive semi-definite if and only if its eigenvalues are non-negative, we see that your original approach would work: calculate the characteristic polynomial, look at its roots to see if they are non-negative. Note that testing for positive definiteness is easy with Sylvester's Criterion (as mentioned in another answer's comment; a matrix is positive definite if and only if the principal minors all have positive determinant); there are extensions for semidefinite (all minors have non-negative determinant), but you have to check $2^n$ minors in this case, versus just $n$ for positive definite.
