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?

  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$
    – whuber
    Commented Jan 3, 2017 at 15:44
  • 2
    $\begingroup$ A search of this site led directly to one of (several) threads containing relevant formulas: stats.stackexchange.com/questions/5747. There are also some useful plots in the answer by felix s. $\endgroup$
    – whuber
    Commented Jan 3, 2017 at 15:45

6 Answers 6


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*}

  • 7
    $\begingroup$ @novice You might want to read about Sylvester's Criterion $\endgroup$ Commented Jan 3, 2017 at 10:10
  • 1
    $\begingroup$ Great answer. I would add the following: The popular way of obtaining gamma is to attempt to find the gamma that would lead to the correlation matrix of smallest nuclear norm (aka ky-fan norm) possible while solving the above equations. For more, look up "matrix completion," "compressive sensing," or check out this report on the topic bit.ly/2iwY1nW. $\endgroup$ Commented Jan 3, 2017 at 23:26
  • 1
    $\begingroup$ For this to be a proof, you need a result in the other direction: if all nontrivial leading minors are $>0$ and the matrix has determinant $\geq 0$, then the matrix is positive semidefinite. $\endgroup$ Commented Jan 4, 2017 at 9:47

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

  • 1
    $\begingroup$ +1, A legitimate geometric reasoning (saying it, I didn't check your computations nonetheless). This is exactly what I've proposed in comments to the question (unfortunately, all the comments were moved by moderator to chat, see the link above). $\endgroup$
    – ttnphns
    Commented Jan 3, 2017 at 20:52
  • $\begingroup$ It seems to me you have "proven" that all correlations must be non-negative, because it appears your calculation will always give zero for the lower limit. If that's not the case, then could you elaborate on how your computation works in general? I really don't trust--or perhaps don't understand--your bound, because in three or more dimensions you can always find a $v_1$ for which both $v_1\cdot v_2=v_1\cdot v_3=0$ and then your bound implies $v_2\cdot v_3$ is always zero! (cc @ttnphns) $\endgroup$
    – whuber
    Commented Jan 3, 2017 at 22:35
  • $\begingroup$ @whuber: Sorry about the confusion. The calculation does not always give zero for the lower limit. I've amended my answer. $\endgroup$
    – yangle
    Commented Jan 4, 2017 at 0:14
  • $\begingroup$ How do you respond to my last concern? It seems to indicate your bounds are incorrect. $\endgroup$
    – whuber
    Commented Jan 4, 2017 at 0:16
  • $\begingroup$ @whuber: In your case, ⟨v1,v2⟩=⟨v1,v3⟩=π/2, hence the bound |⟨v1,v2⟩±⟨v1,v3⟩| is [0, π] as expected. The bound cos⟨v1,v2⟩cos⟨v1,v3⟩∓sin⟨v1,v3⟩sin⟨v1,v2⟩ on γ also works out to be [-1, 1]. $\endgroup$
    – yangle
    Commented Jan 4, 2017 at 0:19

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

enter image description here

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

enter image description here

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 \}$$

  • $\begingroup$ What software will allow me to draw the elliptope? Thanks $\endgroup$
    – Silchara
    Commented Sep 2, 2022 at 14:31
  • $\begingroup$ @Silchara I used Grapher $\endgroup$ Commented Sep 2, 2022 at 16:55

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:

  1. minimize γ subject to matrix is psd.
  2. maximize γ subject to matrix is psd.

For example, these problems can be formulated and numerically solved using YALMIP under MATLAB.

  1. gamma = sdpvar; A = [1 .6 .8;.6 1 gamma;.8 gamma 1]; optimize(A >= 0, gamma)
  2. optimize(A >= 0,-gamma)

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):

enter image description here

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

  • $\begingroup$ If X,Y,Z are random variables, how do you map them to vectors in 3d space (They can only be vectors in 1d space). Also if the RV's are Nx1, then they will be vectors in N dimensional space? $\endgroup$
    – novice
    Commented Jan 4, 2017 at 1:04
  • $\begingroup$ @novice Yes, they are initially 3 vectors in Nd space, but only 3 dimensions are nonredundant. Please follow the 2nd link in the answer and read further reference there to subject space where it is explained. $\endgroup$
    – ttnphns
    Commented Jan 4, 2017 at 1:11

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.