Correlation Matrices Are Positive Semidefinite

Reported in interviews at JPMorgan Chase Renaissance Technologies

Problem statement

A correlation matrix $C \in \mathbb{R}^{d \times d}$ is the matrix of pairwise correlations of some random vector $Z = (Z_1, \ldots, Z_d)^\top$, where $C_{ij} = \text{Corr}(Z_i, Z_j)$, so the diagonal entries are all 1.

  1. Define what it means for a symmetric matrix $M \in \mathbb{R}^{d \times d}$ to be positive semidefinite (PSD).
  1. Prove that every correlation matrix is PSD.
  1. Address the converse: if $C$ is a symmetric matrix with ones on the diagonal and $C$ is PSD, must there exist a random vector $Z$ whose correlation matrix is exactly $C$? Prove your answer.
Show hint

Which quantity built from a random vector can never be negative, and how could a quadratic form in the matrix equal it?

Relevant roles: Data Scientist, Applied Scientist and Research Scientist.

Related free problems