Chapter 7 · Multivariate Analysis

7.3 Principal Components, Discriminant, Cluster and Canonical Correlation Analysis

Four ways to reduce and organise multivariate data: principal components (the eigenvectors of the covariance matrix), Fisher's linear discriminant and optimal classification rules, hierarchical and $k$-means clustering with their linkages and dendrograms, and canonical correlations between two sets of variables — each with its theory, its computation and its traps.

A modern data set rarely has one or two variables. A hospital records twenty blood markers per patient, a satellite measures reflectance in a dozen wavelength bands, a psychologist scores fifty questionnaire items, and a geneticist measures thousands of genes on a few hundred samples. The multivariate normal theory of §7.1–§7.2 tells us how to make inferences about mean vectors and covariance matrices; this section is about the complementary task of understanding such data: finding the few directions in which the data really vary, separating groups, discovering groups nobody labelled, and relating one block of variables to another. The four classical tools — principal component analysis, discriminant analysis, cluster analysis and canonical correlation analysis — are all, at heart, applications of one piece of linear algebra: the maximisation of a ratio of quadratic forms, solved by an eigenvalue or singular value decomposition.

Principal components maximise $a^{\mathsf T}\Sigma a$ over unit vectors $a$ (an eigenvalue problem for $\Sigma$). Fisher's discriminant maximises the ratio $(a^{\mathsf T}d)^2/(a^{\mathsf T}Sa)$ of between-group to within-group variation (answer: $a\propto S^{-1}d$). Canonical correlations maximise a correlation $a^{\mathsf T}\Sigma_{12}b/\sqrt{a^{\mathsf T}\Sigma_{11}a\;b^{\mathsf T}\Sigma_{22}b}$ (a singular value problem). Cluster analysis is different in flavour — it is combinatorial — but its most popular method, $k$-means, minimises the same within-group sum of squares that appears in the analysis of variance (§6.2). CSIR Part B questions ask for the proportion of variance explained by the first components, a discriminant function or its error rate, a merge height in a dendrogram, or a canonical correlation from a small correlation matrix. Part C questions test the theory: which properties are invariant under rescaling, when an extra variable can help discrimination, which linkages produce a monotone dendrogram, what $k$-means is and is not guaranteed to do, and how canonical correlations compare with ordinary and multiple correlations.

Notation. Vectors are columns and $^{\mathsf T}$ is the transpose. $X=(X_1,\dots,X_p)^{\mathsf T}$ is a random vector with mean $\mu$ and covariance matrix $\Sigma=(\sigma_{ik})$, which is symmetric and positive semidefinite (§7.1). For data $x_1,\dots,x_n\in\mathbb{R}^p$ we write $\bar x=\frac1n\sum x_i$ and $S=\frac1{n-1}\sum_{i=1}^n(x_i-\bar x)(x_i-\bar x)^{\mathsf T}$ for the sample covariance matrix. We use the spectral theorem of linear algebra (Unit 1): a real symmetric $p\times p$ matrix $A$ can be written $A=\sum_{j=1}^p\lambda_je_je_j^{\mathsf T}=E\Lambda E^{\mathsf T}$ with real eigenvalues $\lambda_1\ge\dots\ge\lambda_p$ and an orthonormal basis of eigenvectors $e_1,\dots,e_p$ (the columns of the orthogonal matrix $E$). If $A$ is positive definite, $A^{1/2}=E\Lambda^{1/2}E^{\mathsf T}$ and $A^{-1/2}=E\Lambda^{-1/2}E^{\mathsf T}$. The Mahalanobis distance of §7.1 is $\Delta^2=(\mu_1-\mu_2)^{\mathsf T}\Sigma^{-1}(\mu_1-\mu_2)$.

Principal Component Analysis

Suppose we must summarise $p$ correlated measurements by a single number. A natural choice is the linear combination $a^{\mathsf T}X$ that varies the most — it separates the individuals best. Since $\operatorname{Var}(a^{\mathsf T}X)=a^{\mathsf T}\Sigma a$ can be made as large as we like by scaling $a$, we normalise $\|a\|=1$. Having found the best direction, we look for the best direction among those that carry new information, i.e. that are uncorrelated with what we already have.

📘 Definition 7.10 — Principal components of a random vector

Let $X$ have covariance matrix $\Sigma$. The first principal component of $X$ is a linear combination $Y_1=a_1^{\mathsf T}X$ with $\|a_1\|=1$ that maximises $\operatorname{Var}(a^{\mathsf T}X)$ over all unit vectors $a$. For $k=2,\dots,p$, the $k$-th principal component is $Y_k=a_k^{\mathsf T}X$ with $\|a_k\|=1$ that maximises $\operatorname{Var}(a^{\mathsf T}X)$ over unit vectors $a$ subject to $\operatorname{Cov}(a^{\mathsf T}X,Y_j)=0$ for $j=1,\dots,k-1$ (in the degenerate case that some earlier $Y_j$ has variance $0$ we also require $a\perp a_j$). The vectors $a_k$ are the loadings (coefficient vectors). Often the components are centred, $Y_k=a_k^{\mathsf T}(X-\mu)$; this changes no variance or covariance.

📐 Theorem 7.26 — Principal components from the spectral decomposition

Let $\Sigma=\sum_{j=1}^p\lambda_je_je_j^{\mathsf T}$ with $\lambda_1\ge\lambda_2\ge\dots\ge\lambda_p\ge0$ and $e_1,\dots,e_p$ orthonormal. Then for every unit vector $a$,

$$\lambda_p\le a^{\mathsf T}\Sigma a\le\lambda_1,$$

with the maximum attained at $a=e_1$ and the minimum at $a=e_p$. More generally, the maximum of $a^{\mathsf T}\Sigma a$ over unit vectors $a\perp e_1,\dots,e_{k-1}$ is $\lambda_k$, attained at $a=e_k$. Consequently the principal components are

$$Y_k=e_k^{\mathsf T}X,\qquad\operatorname{Var}(Y_k)=\lambda_k,$$ $$\operatorname{Cov}(Y_j,Y_k)=0\quad(j\ne k).$$

The loadings are unique up to sign exactly when $\lambda_k$ is a simple eigenvalue; if $\lambda_k$ is repeated, any unit vector of its eigenspace (orthogonal to the earlier loadings) will do.

Proof. Expand $a=\sum_jc_je_j$ with $c_j=e_j^{\mathsf T}a$; orthonormality gives $\|a\|^2=\sum_jc_j^2$ and $\Sigma a=\sum_j\lambda_jc_je_j$, so

$$a^{\mathsf T}\Sigma a=\sum_{j=1}^p\lambda_jc_j^2 .$$

If $\|a\|=1$, this is a weighted average of the $\lambda_j$ with weights $c_j^2\ge0$ summing to $1$, so it lies between $\lambda_p$ and $\lambda_1$; it equals $\lambda_1$ when $c=(1,0,\dots,0)$, i.e. $a=e_1$, and $\lambda_p$ when $a=e_p$. If in addition $a\perp e_1,\dots,e_{k-1}$, then $c_1=\dots=c_{k-1}=0$, and $a^{\mathsf T}\Sigma a=\sum_{j\ge k}\lambda_jc_j^2\le\lambda_k\sum_{j\ge k}c_j^2=\lambda_k$, with equality at $a=e_k$.

It remains to match the constraint "uncorrelated with $Y_1,\dots,Y_{k-1}$" with "$a\perp e_1,\dots,e_{k-1}$", arguing by induction on $k$. Suppose $Y_j=e_j^{\mathsf T}X$ for $j\lt k$. Then $\operatorname{Cov}(a^{\mathsf T}X,Y_j)=a^{\mathsf T}\Sigma e_j=\lambda_j\,a^{\mathsf T}e_j$. If $\lambda_j\gt0$, this vanishes iff $a\perp e_j$; if $\lambda_j=0$, orthogonality is required by the definition. So the admissible $a$ are exactly the unit vectors orthogonal to $e_1,\dots,e_{k-1}$, the maximum is $\lambda_k$, and $a_k=e_k$ is a maximiser; hence $Y_k=e_k^{\mathsf T}X$ and $\operatorname{Var}(Y_k)=\lambda_k$. Finally $\operatorname{Cov}(Y_j,Y_k)=e_j^{\mathsf T}\Sigma e_k=\lambda_k e_j^{\mathsf T}e_k=0$ for $j\ne k$. If $\lambda_k\gt\lambda_{k+1}$ and $\lambda_k\lt\lambda_{k-1}$, equality $\sum_{j\ge k}\lambda_jc_j^2=\lambda_k$ forces $c_j=0$ for $j\gt k$, so $a=\pm e_k$; if $\lambda_k$ is repeated, every unit vector of the eigenspace gives equality. ∎

The ratio $a^{\mathsf T}\Sigma a/a^{\mathsf T}a$ is the Rayleigh quotient of $\Sigma$; the theorem is the Rayleigh–Ritz characterisation of eigenvalues, read statistically. In matrix form, $Y=E^{\mathsf T}(X-\mu)$ is an orthogonal change of coordinates — a rotation (possibly with reflections) of the axes to the principal axes of the ellipsoids $\{x:(x-\mu)^{\mathsf T}\Sigma^{-1}(x-\mu)=c^2\}$, which are the contours of the $N_p(\mu,\Sigma)$ density (§7.1). The $k$-th semi-axis of such an ellipsoid has length $c\sqrt{\lambda_k}$ along $e_k$.

📐 Theorem 7.27 — Properties of principal components

With the notation of Theorem 7.26 and $Y=E^{\mathsf T}(X-\mu)$:

  1. Total and generalised variance are preserved: $\sum_{k=1}^p\operatorname{Var}(Y_k)=\sum_k\lambda_k=\operatorname{tr}\Sigma=\sum_i\sigma_{ii}$, and $\prod_k\lambda_k=\det\Sigma$.
  2. Reconstruction: $X=\mu+\sum_{k=1}^pY_ke_k$.
  3. Loadings as correlations: $\operatorname{Cov}(Y_k,X_i)=\lambda_ke_{ik}$, where $e_{ik}$ is the $i$-th entry of $e_k$; hence, if $\sigma_{ii}\gt0$ and $\lambda_k\gt0$,
$$\operatorname{corr}(Y_k,X_i)=\frac{e_{ik}\sqrt{\lambda_k}}{\sqrt{\sigma_{ii}}}.$$
  1. Bounds by the diagonal: $\lambda_1\ge\max_i\sigma_{ii}$ and $\lambda_p\le\min_i\sigma_{ii}$.
  2. Normal case: if $X\sim N_p(\mu,\Sigma)$, then $Y_1,\dots,Y_p$ are independent, $Y_k\sim N(0,\lambda_k)$.

Proof. (1) $\operatorname{Cov}(Y)=E^{\mathsf T}\Sigma E=\Lambda$, so $\sum\operatorname{Var}(Y_k)=\operatorname{tr}\Lambda$ $=\operatorname{tr}(E^{\mathsf T}\Sigma E)$ $=\operatorname{tr}(\Sigma EE^{\mathsf T})=\operatorname{tr}\Sigma$, and $\det\Lambda=\det(E^{\mathsf T})\det\Sigma\det E=\det\Sigma$ because $\det E=\pm1$. (2) $EE^{\mathsf T}=I$, so $X-\mu=EY=\sum_kY_ke_k$. (3) With $u_i$ the $i$-th standard basis vector, $\operatorname{Cov}(Y_k,X_i)=e_k^{\mathsf T}\Sigma u_i=\lambda_ke_k^{\mathsf T}u_i=\lambda_ke_{ik}$; divide by $\sqrt{\lambda_k\sigma_{ii}}$. (4) Take $a=u_i$ in Theorem 7.26: $\lambda_p\le u_i^{\mathsf T}\Sigma u_i=\sigma_{ii}\le\lambda_1$. (5) $Y$ is a linear transformation of a normal vector, hence normal (§7.1), with diagonal covariance $\Lambda$; uncorrelated components of a jointly normal vector are independent. ∎

✏️ Example 1 — Principal components of a $2\times2$ covariance matrix
Let $X=(X_1,X_2)^{\mathsf T}$ have covariance matrix $\Sigma=\begin{pmatrix}5&2\\2&2\end{pmatrix}$. Find the principal components, their variances, the proportion of the total variance explained by the first, and the correlations of each component with $X_1$ and $X_2$. Repeat the analysis for the correlation matrix of $X$.
Eigenvalues $\det(\Sigma-\lambda I)=(5-\lambda)(2-\lambda)-4$ $=\lambda^2-7\lambda+6$ $=(\lambda-6)(\lambda-1)$, so $\lambda_1=6$, $\lambda_2=1$. Check: $\lambda_1+\lambda_2=7=\operatorname{tr}\Sigma$ and $\lambda_1\lambda_2=6=\det\Sigma$.
Eigenvectors $(\Sigma-6I)e=0$ gives $-e_1+2e_2=0$, so $e_1=\frac1{\sqrt5}(2,1)^{\mathsf T}$; then $e_2=\frac1{\sqrt5}(1,-2)^{\mathsf T}$ (orthogonal to $e_1$). Hence $Y_1=\frac{2X_1+X_2}{\sqrt5}$ with variance $6$ and $Y_2=\frac{X_1-2X_2}{\sqrt5}$ with variance $1$.
Proportion $Y_1$ explains $6/7=85.7\%$ of the total variance $\operatorname{tr}\Sigma=7$.
Correlations By Theorem 7.27(3): $\operatorname{corr}(Y_1,X_1)=\frac{(2/\sqrt5)\sqrt6}{\sqrt5}=\frac{2\sqrt6}{5}=0.980$, $\operatorname{corr}(Y_1,X_2)=\frac{(1/\sqrt5)\sqrt6}{\sqrt2}=\sqrt{3/5}=0.775$, $\operatorname{corr}(Y_2,X_1)=\frac{1/\sqrt5}{\sqrt5}=0.2$ and $\operatorname{corr}(Y_2,X_2)=\frac{-2/\sqrt5}{\sqrt2}=-0.632$. Check: $0.980^2+0.2^2=0.96+0.04=1$ and $0.775^2+0.632^2=0.6+0.4=1$ (Exercise I.4).
Correlation matrix $\rho_{12}=2/\sqrt{10}=0.632$, so $R=\begin{pmatrix}1&0.632\\0.632&1\end{pmatrix}$ has eigenvalues $1\pm0.632$, i.e. $1.632$ and $0.368$, with eigenvectors $\frac1{\sqrt2}(1,1)^{\mathsf T}$ and $\frac1{\sqrt2}(1,-1)^{\mathsf T}$. The first component of the standardised variables $Z_i=X_i/\sqrt{\sigma_{ii}}$ is $(Z_1+Z_2)/\sqrt2$, explaining $1.632/2=81.6\%$.
Comment The two analyses disagree: on the covariance scale $X_1$ (variance $5$) dominates the first component, with loadings in the ratio $2:1$; after standardisation both variables count equally. Principal components are not scale invariant, and the choice between $\Sigma$ and $R$ is a modelling decision (see the Counterexamples box).

Why keep only the first few components? Because they give the best low-dimensional picture of $X$ in a precise sense: no other $k$-dimensional projection loses less of the total variance.

📐 Theorem 7.28 — Principal components give the best $k$-dimensional approximation

Let $1\le k\le p$ and let $A$ be any $p\times k$ matrix with orthonormal columns, so that $P=AA^{\mathsf T}$ is the orthogonal projection onto a $k$-dimensional subspace. Then

$$E\big\|(X-\mu)-P(X-\mu)\big\|^2=\operatorname{tr}\Sigma-\operatorname{tr}(A^{\mathsf T}\Sigma A)$$ $$\ge\sum_{j=k+1}^p\lambda_j,$$

with equality when the columns of $A$ are $e_1,\dots,e_k$. For data, with $\Sigma$ replaced by $S$: among all $k$-dimensional affine subspaces through $\bar x$, the one spanned by the first $k$ sample principal directions minimises the sum of squared perpendicular distances $\sum_i\|(x_i-\bar x)-P(x_i-\bar x)\|^2$, and the minimum is $(n-1)\sum_{j\gt k}\hat\lambda_j$.

Proof. Write $W=X-\mu$. Since $P$ is symmetric and idempotent, $\|W-PW\|^2=W^{\mathsf T}W-W^{\mathsf T}PW$, and $E[W^{\mathsf T}MW]=\operatorname{tr}(M\Sigma)$ for any fixed matrix $M$. So the left side equals $\operatorname{tr}\Sigma-\operatorname{tr}(AA^{\mathsf T}\Sigma)=\operatorname{tr}\Sigma-\operatorname{tr}(A^{\mathsf T}\Sigma A)$. Now

$$\operatorname{tr}(A^{\mathsf T}\Sigma A)=\sum_{j=1}^p\lambda_j\|A^{\mathsf T}e_j\|^2=\sum_{j=1}^p\lambda_jw_j,$$

where $w_j=\|A^{\mathsf T}e_j\|^2$ is the squared length of the projection of the unit vector $e_j$ onto the column space of $A$, so $0\le w_j\le1$, and $\sum_jw_j=\operatorname{tr}(A^{\mathsf T}EE^{\mathsf T}A)=\operatorname{tr}(A^{\mathsf T}A)=k$. A sum $\sum\lambda_jw_j$ with $\lambda_1\ge\dots\ge\lambda_p$, weights in $[0,1]$ and total weight $k$ is largest when the weight is put on the $k$ largest $\lambda$'s: indeed $$\sum_{j\le k}\lambda_j-\sum_j\lambda_jw_j=\sum_{j\le k}\lambda_j(1-w_j)-\sum_{j\gt k}\lambda_jw_j$$ $$\ge\lambda_k\Big(\sum_{j\le k}(1-w_j)-\sum_{j\gt k}w_j\Big)=\lambda_k(k-k)=0.$$ Hence $\operatorname{tr}(A^{\mathsf T}\Sigma A)\le\lambda_1+\dots+\lambda_k$, which is the inequality; for $A=(e_1,\dots,e_k)$, $w_j=1$ for $j\le k$ and $0$ otherwise, giving equality. The data version is the same computation with the empirical distribution of the $x_i$ in place of the law of $X$ (expectation becomes $\frac1{n-1}\sum_i$, $\mu$ becomes $\bar x$, $\Sigma$ becomes $S$). ∎

So the first principal component line is the orthogonal regression line: it minimises perpendicular distances, treating all variables symmetrically. The least-squares line of $x_2$ on $x_1$ (§6.3) minimises vertical distances instead, and the two lines differ unless the points are collinear (Exercise I.8).

📘 Definition 7.11 — Sample principal components, scores and proportion of variance

Let $S=\sum_j\hat\lambda_j\hat e_j\hat e_j^{\mathsf T}$ with $\hat\lambda_1\ge\dots\ge\hat\lambda_p\ge0$. The sample principal components are $\hat y_k=\hat e_k^{\mathsf T}(x-\bar x)$; the numbers $\hat y_{ik}=\hat e_k^{\mathsf T}(x_i-\bar x)$ are the scores of observation $i$. The proportion of variance explained by the first $k$ components is

$$\frac{\hat\lambda_1+\dots+\hat\lambda_k}{\hat\lambda_1+\dots+\hat\lambda_p}=\frac{\hat\lambda_1+\dots+\hat\lambda_k}{\operatorname{tr}S}.$$

A scree plot is the graph of $\hat\lambda_k$ against $k$. PCA on the correlation matrix means PCA of the standardised variables $z_{ij}=(x_{ij}-\bar x_j)/\sqrt{s_{jj}}$, whose covariance matrix is the sample correlation matrix $R$; then $\operatorname{tr}R=p$ and the proportion explained by component $k$ is $\hat\lambda_k/p$.

The sample scores have exactly the properties of Theorem 7.27 with respect to the empirical distribution: the $k$-th column of scores has mean $0$ and sample variance $\hat\lambda_k$, and different columns have sample correlation $0$. How many components to keep is a judgement; common rules are: keep enough to explain a stated proportion (often $80$–$90\%$); look for the "elbow" of the scree plot; or, for a correlation matrix, keep components with $\hat\lambda_k\gt1$ (Kaiser's rule — "better than one original variable"), a rule that tends to keep too many when $p/n$ is not small (see the Research–Teaching Nexus). For inference, if $x_1,\dots,x_n$ are iid $N_p(\mu,\Sigma)$ and $\lambda_k$ is a simple eigenvalue of $\Sigma$, then $\sqrt n(\hat\lambda_k-\lambda_k)\to N(0,2\lambda_k^2)$ in distribution (a classical result of T. W. Anderson, stated without proof), which gives the approximate $100(1-\alpha)\%$ interval

$$\frac{\hat\lambda_k}{1+z_{\alpha/2}\sqrt{2/n}}\le\lambda_k\le\frac{\hat\lambda_k}{1-z_{\alpha/2}\sqrt{2/n}}.$$
✏️ Example 2 — Principal component scores for a small data set
Five specimens are measured on two characteristics:
specimen12345
$x_1$68101214
$x_2$35575
Find $S$, its principal components and the proportion of variance explained, compute the scores, and verify that (a) the score columns have sample variances $\hat\lambda_1,\hat\lambda_2$ and are uncorrelated, and (b) the sum of squared perpendicular distances from the points to the first principal axis is $(n-1)\hat\lambda_2$. Reconstruct specimen 4 from its first score alone.
Covariance $\bar x=(10,5)$; deviations $d_1=(-4,-2,0,2,4)$, $d_2=(-2,0,0,2,0)$. $\sum d_1^2=40$, $\sum d_1d_2=8+0+0+4+0=12$, $\sum d_2^2=8$, so $S=\frac14\begin{pmatrix}40&12\\12&8\end{pmatrix}=\begin{pmatrix}10&3\\3&2\end{pmatrix}$.
Components $\lambda^2-12\lambda+11=0$, so $\hat\lambda_1=11$, $\hat\lambda_2=1$; $(S-11I)e=0$ gives $-e_1+3e_2=0$, so $\hat e_1=\frac1{\sqrt{10}}(3,1)^{\mathsf T}$, $\hat e_2=\frac1{\sqrt{10}}(1,-3)^{\mathsf T}$. The first component explains $11/12=91.7\%$.
Scores $\hat y_{i1}=(3d_{i1}+d_{i2})/\sqrt{10}$ $=(-14,-6,0,8,12)/\sqrt{10}$ $=(-4.427,-1.897,0,2.530,3.795)$ and $\hat y_{i2}=(d_{i1}-3d_{i2})/\sqrt{10}$ $=(2,-2,0,-4,4)/\sqrt{10}$ $=(0.632,-0.632,0,-1.265,1.265)$.
(a) Both columns sum to $0$. $\sum\hat y_{i1}^2=(196+36+0+64+144)/10=44$, and $44/4=11=\hat\lambda_1$; $\sum\hat y_{i2}^2=(4+4+0+16+16)/10=4$, and $4/4=1=\hat\lambda_2$. $\sum\hat y_{i1}\hat y_{i2}=(-28+12+0-32+48)/10=0$.
(b) The perpendicular distance from $x_i$ to the line $\bar x+t\hat e_1$ is $|\hat y_{i2}|$, so the sum of squares is $\sum\hat y_{i2}^2=4=(n-1)\hat\lambda_2$, as Theorem 7.28 predicts. No other line through $\bar x$ does better.
Reconstruction $\bar x+\hat y_{41}\hat e_1=(10,5)+\frac{8}{\sqrt{10}}\cdot\frac{(3,1)}{\sqrt{10}}=(12.4,\ 5.8)$; the observed point is $(12,7)$, and the error $(-0.4,1.2)=\hat y_{42}\hat e_2$ is perpendicular to $\hat e_1$.
Check The least-squares slope of $x_2$ on $x_1$ is $s_{12}/s_{11}=0.3$, while the principal axis has slope $1/3$: the two lines are different, and the principal axis is steeper, as Exercise I.8 shows it must be.
🧭 Problem-solving strategy — PCA by hand
  1. Decide between $\Sigma$ (or $S$) and the correlation matrix: use the correlation matrix when the variables are in different units or have very different variances for reasons of scale only.
  2. Look for structure before computing: a block-diagonal matrix splits into separate smaller problems; for $\begin{pmatrix}a&b\\b&a\end{pmatrix}$ the eigenvectors are $(1,\pm1)/\sqrt2$ with eigenvalues $a\pm b$; for the equicorrelation matrix $(1-\rho)I+\rho\mathbf 1\mathbf 1^{\mathsf T}$ they are $1+(p-1)\rho$ (eigenvector $\mathbf 1/\sqrt p$) and $1-\rho$ (repeated).
  3. For a $2\times2$ matrix use $\lambda^2-(\operatorname{tr})\lambda+\det=0$; check every answer with $\sum\lambda_j=\operatorname{tr}$ and $\prod\lambda_j=\det$.
  4. Proportions of variance use $\operatorname{tr}$ ($=p$ for a correlation matrix), never the largest diagonal entries.
  5. For interpretation, convert loadings to correlations $e_{ik}\sqrt{\lambda_k}/\sqrt{\sigma_{ii}}$; for each variable their squares sum to $1$ over $k$.
Interactive 1 — Principal Axes of a Point Cloud

Eighty centred points are drawn with correlation $\rho$ and spread ratio $\sigma_2/\sigma_1$ of your choice. The red and blue axes are the sample principal directions $\hat e_1,\hat e_2$, inside the ellipse of $2\sqrt{\hat\lambda_k}$ semi-axes. The purple line is a trial direction $a=(\cos\theta,\sin\theta)$: the points are projected onto it, and the panel on the right plots the variance $a^{\mathsf T}Sa$ of the projections against $\theta$. Press Play to rotate $a$ and watch the variance peak at $\hat\lambda_1$ exactly when $a=\hat e_1$, while the perpendicular segments (the information lost) are shortest. Then switch to the correlation matrix: the principal directions jump to $45^\circ$ or $135^\circ$ whatever $\rho$ and $\sigma_2/\sigma_1$ are.

s₁₁, s₁₂, s₂₂—
λ̂₁, λ̂₂—
PC1 share λ̂₁/(λ̂₁+λ̂₂)—
ê₁ and its angle—
trial θ: variance aᵀSa—
lost variance tr S − aᵀSa—

Discriminant Analysis and Classification

A bank must decide from an applicant's financial ratios whether to treat the applicant as a likely defaulter; a botanist assigns a specimen to one of two species from its measurements; a screening test labels a patient as healthy or diseased from several blood markers. In each case there are known populations, training data from each, and a new observation $x$ to be allocated. We first find the best possible rule when the populations are known, and then Fisher's sample rule.

📘 Definition 7.12 — Classification rules and the cost of misclassification

Two populations $\mathcal P_1,\mathcal P_2$ have densities $f_1,f_2$ on $\mathbb{R}^p$ and prior probabilities $\pi_1,\pi_2$ ($\pi_1+\pi_2=1$). A classification rule is a partition $\mathbb{R}^p=R_1\cup R_2$: an observation in $R_k$ is allocated to $\mathcal P_k$. The misclassification probabilities are

$$P(2\mid1)=\int_{R_2}f_1(x)\,dx,$$ $$P(1\mid2)=\int_{R_1}f_2(x)\,dx .$$

If allocating a member of $\mathcal P_1$ to $\mathcal P_2$ costs $c(2\mid1)\gt0$ and the reverse error costs $c(1\mid2)\gt0$, the expected cost of misclassification is $\mathrm{ECM}=c(2\mid1)\pi_1P(2\mid1)+c(1\mid2)\pi_2P(1\mid2)$. With equal costs it is proportional to the total probability of misclassification $\mathrm{TPM}=\pi_1P(2\mid1)+\pi_2P(1\mid2)$.

📐 Theorem 7.29 — The minimum-ECM (Bayes) rule

The rule

$$R_1=\Big\{x:\ \frac{f_1(x)}{f_2(x)}\ge k\Big\},\qquad k=\frac{c(1\mid2)\,\pi_2}{c(2\mid1)\,\pi_1},$$

and $R_2$ its complement (with $f_1/f_2=+\infty$ where $f_2=0\lt f_1$), minimises the ECM among all classification rules. Points with $f_1(x)=kf_2(x)$ may be allocated either way without changing the ECM. With equal costs and equal priors, the rule allocates $x$ to the population with the larger density: it is the likelihood ratio rule.

Proof. For any rule, $P(2\mid1)=1-\int_{R_1}f_1$, so

$$\mathrm{ECM}=c(2\mid1)\pi_1$$ $$+\int_{R_1}\big[c(1\mid2)\pi_2f_2(x)-c(2\mid1)\pi_1f_1(x)\big]dx .$$

The first term does not depend on the rule. The integral is smallest when $R_1$ contains every point where the integrand is negative and no point where it is positive, i.e. $R_1=\{x:c(2\mid1)\pi_1f_1(x)\ge c(1\mid2)\pi_2f_2(x)\}$ up to the set where the integrand is $0$, which contributes nothing. Dividing by $c(2\mid1)\pi_1f_2(x)$ gives the stated form. ∎

The same argument with $g$ populations shows that, with equal costs, the rule "allocate $x$ to the $k$ that maximises $\pi_kf_k(x)$" — equivalently, to the population with the largest posterior probability $P(\mathcal P_k\mid x)$ — minimises the total probability of misclassification. This is the Bayes classifier; it is the Neyman–Pearson lemma (§5.1) in another guise, with the threshold $k$ fixed by priors and costs instead of by a size.

📐 Theorem 7.30 — Two normal populations with a common covariance matrix

Let $f_k$ be the $N_p(\mu_k,\Sigma)$ density, $k=1,2$, with $\Sigma$ positive definite and $\mu_1\ne\mu_2$. Put

$$a=\Sigma^{-1}(\mu_1-\mu_2),$$ $$W(x)=a^{\mathsf T}\Big(x-\frac{\mu_1+\mu_2}{2}\Big).$$

Then $\log\{f_1(x)/f_2(x)\}=W(x)$, so the minimum-ECM rule allocates $x$ to $\mathcal P_1$ iff $W(x)\ge\log k$: the boundary is a hyperplane. Under $\mathcal P_1$, $W(X)\sim N(\tfrac12\Delta^2,\Delta^2)$ and under $\mathcal P_2$, $W(X)\sim N(-\tfrac12\Delta^2,\Delta^2)$, where $\Delta^2=(\mu_1-\mu_2)^{\mathsf T}\Sigma^{-1}(\mu_1-\mu_2)$ is the Mahalanobis distance (§7.1). Hence

$$P(2\mid1)=\Phi\Big(\frac{\log k-\Delta^2/2}{\Delta}\Big),$$ $$P(1\mid2)=\Phi\Big(\frac{-\log k-\Delta^2/2}{\Delta}\Big),$$

and with $k=1$ (equal priors and costs) both equal $\Phi(-\Delta/2)$, which decreases to $0$ as $\Delta\to\infty$.

Proof. The normalising constants of $f_1$ and $f_2$ are equal, so

$$\log\frac{f_1(x)}{f_2(x)}=-\tfrac12(x-\mu_1)^{\mathsf T}\Sigma^{-1}(x-\mu_1)$$ $$+\tfrac12(x-\mu_2)^{\mathsf T}\Sigma^{-1}(x-\mu_2).$$

Expanding, the quadratic terms $x^{\mathsf T}\Sigma^{-1}x$ cancel, leaving $(\mu_1-\mu_2)^{\mathsf T}\Sigma^{-1}x-\frac12(\mu_1^{\mathsf T}\Sigma^{-1}\mu_1-\mu_2^{\mathsf T}\Sigma^{-1}\mu_2)$. Since $\Sigma^{-1}$ is symmetric, $\mu_1^{\mathsf T}\Sigma^{-1}\mu_1-\mu_2^{\mathsf T}\Sigma^{-1}\mu_2=(\mu_1-\mu_2)^{\mathsf T}\Sigma^{-1}(\mu_1+\mu_2)$, so the log ratio is $a^{\mathsf T}x-\frac12a^{\mathsf T}(\mu_1+\mu_2)=W(x)$. The rule follows from Theorem 7.29. $W(X)$ is a linear function of a normal vector, hence normal; under $\mathcal P_1$ its mean is $a^{\mathsf T}(\mu_1-\frac{\mu_1+\mu_2}2)=\frac12a^{\mathsf T}(\mu_1-\mu_2)=\frac12\Delta^2$, under $\mathcal P_2$ it is $-\frac12\Delta^2$, and in both cases its variance is $a^{\mathsf T}\Sigma a=(\mu_1-\mu_2)^{\mathsf T}\Sigma^{-1}\Sigma\Sigma^{-1}(\mu_1-\mu_2)=\Delta^2$. Then $P(2\mid1)=P(W\lt\log k\mid\mathcal P_1)$ $=\Phi\big((\log k-\frac12\Delta^2)/\Delta\big)$ and $P(1\mid2)=P(W\ge\log k\mid\mathcal P_2)$ $=1-\Phi\big((\log k+\frac12\Delta^2)/\Delta\big)$, which is the stated value by $1-\Phi(t)=\Phi(-t)$. ∎

If the covariance matrices differ, $\Sigma_1\ne\Sigma_2$, the quadratic terms no longer cancel and the optimal boundary is the quadric $$-\tfrac12x^{\mathsf T}(\Sigma_1^{-1}-\Sigma_2^{-1})x$$ $$+(\mu_1^{\mathsf T}\Sigma_1^{-1}-\mu_2^{\mathsf T}\Sigma_2^{-1})x-\kappa=\log k,$$ where $\kappa=\frac12\log\frac{\det\Sigma_1}{\det\Sigma_2}$ $+\frac12(\mu_1^{\mathsf T}\Sigma_1^{-1}\mu_1-\mu_2^{\mathsf T}\Sigma_2^{-1}\mu_2)$: this is quadratic discriminant analysis (Exercise II.3).

In practice $\mu_1,\mu_2,\Sigma$ are unknown. R. A. Fisher (1936) found the same linear rule from a distribution-free argument: look for the linear combination $y=a^{\mathsf T}x$ whose two group means are as far apart as possible relative to the spread within the groups.

📘 Definition 7.13 — Fisher's linear discriminant

Let $x_{11},\dots,x_{1n_1}$ and $x_{21},\dots,x_{2n_2}$ be training samples from $\mathcal P_1$ and $\mathcal P_2$, with means $\bar x_1,\bar x_2$, covariance matrices $S_1,S_2$, and pooled covariance matrix

$$S_{\text{pl}}=\frac{(n_1-1)S_1+(n_2-1)S_2}{n_1+n_2-2},$$

assumed positive definite. Write $d=\bar x_1-\bar x_2$. For $a\ne0$ the separation ratio of $y=a^{\mathsf T}x$ is $J(a)=(a^{\mathsf T}d)^2/(a^{\mathsf T}S_{\text{pl}}a)$: the squared difference of the group means of $y$ divided by the pooled sample variance of $y$. Fisher's linear discriminant function is $\hat y=\hat a^{\mathsf T}x$ with $\hat a=S_{\text{pl}}^{-1}d$, and Fisher's rule allocates $x_0$ to $\mathcal P_1$ iff

$$\hat a^{\mathsf T}x_0\ge\hat m,\qquad\hat m=\tfrac12\hat a^{\mathsf T}(\bar x_1+\bar x_2).$$
📐 Theorem 7.31 — Fisher's discriminant maximises the separation

For every $a\ne0$,

$$J(a)=\frac{(a^{\mathsf T}d)^2}{a^{\mathsf T}S_{\text{pl}}a}\le d^{\mathsf T}S_{\text{pl}}^{-1}d=D^2,$$

with equality iff $a=cS_{\text{pl}}^{-1}d$ for some $c\ne0$. The maximum $D^2$ is the sample Mahalanobis distance between the group means. Fisher's rule is the minimum-ECM rule of Theorem 7.30 with equal priors and costs, after replacing $\mu_1,\mu_2,\Sigma$ by $\bar x_1,\bar x_2,S_{\text{pl}}$; with priors and costs one compares $\hat a^{\mathsf T}x_0-\hat m$ with $\log k$. The two-sample Hotelling statistic of §7.2 is $T^2=\frac{n_1n_2}{n_1+n_2}D^2$, so the test of $H_0:\mu_1=\mu_2$ is also a test of whether the discriminant separates the populations at all.

Proof. $S_{\text{pl}}$ is positive definite, so $S_{\text{pl}}^{1/2}$ and $S_{\text{pl}}^{-1/2}$ exist. Put $u=S_{\text{pl}}^{1/2}a$ and $v=S_{\text{pl}}^{-1/2}d$. Then $a^{\mathsf T}d=u^{\mathsf T}v$ and $a^{\mathsf T}S_{\text{pl}}a=u^{\mathsf T}u$, so by the Cauchy–Schwarz inequality

$$(a^{\mathsf T}d)^2=(u^{\mathsf T}v)^2\le(u^{\mathsf T}u)(v^{\mathsf T}v)$$ $$=(a^{\mathsf T}S_{\text{pl}}a)\,(d^{\mathsf T}S_{\text{pl}}^{-1}d),$$

with equality iff $u=cv$, i.e. $a=cS_{\text{pl}}^{-1/2}S_{\text{pl}}^{-1/2}d=cS_{\text{pl}}^{-1}d$. With $\hat a=S_{\text{pl}}^{-1}d$, the plug-in version of $W(x)$ in Theorem 7.30 is $d^{\mathsf T}S_{\text{pl}}^{-1}(x-\frac{\bar x_1+\bar x_2}2)=\hat a^{\mathsf T}x-\hat m$, so the two rules coincide. The last statement is the definition of $T^2$ in §7.2 with $D^2$ substituted. ∎

Notice what the proof does not use: normality. Fisher's discriminant is the best linear separator in the sense of $J$ for any distributions with a common covariance matrix; normality is what makes it the optimal classifier and gives the error rates $\Phi(-\Delta/2)$. The rule is also invariant under nonsingular linear changes of the variables (Example 4(c)), unlike principal components.

📐 Theorem 7.32 — Several populations
  1. If $\mathcal P_k=N_p(\mu_k,\Sigma)$, $k=1,\dots,g$, with priors $\pi_k$ and equal costs, the Bayes rule allocates $x$ to the population with the largest linear discriminant score $d_k(x)=\mu_k^{\mathsf T}\Sigma^{-1}x-\frac12\mu_k^{\mathsf T}\Sigma^{-1}\mu_k+\log\pi_k$. With equal priors this is the population whose mean is nearest to $x$ in Mahalanobis distance.
  2. For training samples of sizes $n_1,\dots,n_g$ ($n=\sum n_k$), let $B=\sum_kn_k(\bar x_k-\bar x)(\bar x_k-\bar x)^{\mathsf T}$ and $W=\sum_k\sum_j(x_{kj}-\bar x_k)(x_{kj}-\bar x_k)^{\mathsf T}$ be the between- and within-group matrices, $W$ positive definite. The ratio $a^{\mathsf T}Ba/a^{\mathsf T}Wa$ is maximised by an eigenvector of $W^{-1}B$ for its largest eigenvalue; the successive Fisher discriminants are the eigenvectors of $W^{-1}B$, and at most $\min(g-1,p)$ eigenvalues are nonzero. For $g=2$, $B=\frac{n_1n_2}{n}dd^{\mathsf T}$ and the single discriminant is $W^{-1}d\propto S_{\text{pl}}^{-1}d$.

Proof. (1) $\log(\pi_kf_k(x))=d_k(x)-\frac12x^{\mathsf T}\Sigma^{-1}x+\text{const}$, and the last two terms are the same for every $k$; maximise $\pi_kf_k$ as in the remark after Theorem 7.29. With equal priors, $-2d_k(x)+x^{\mathsf T}\Sigma^{-1}x=(x-\mu_k)^{\mathsf T}\Sigma^{-1}(x-\mu_k)$. (2) Put $b=W^{1/2}a$: the ratio becomes $b^{\mathsf T}Mb/b^{\mathsf T}b$ with $M=W^{-1/2}BW^{-1/2}$ symmetric, a Rayleigh quotient maximised by the top eigenvector of $M$ (Theorem 7.26). If $Mb=\lambda b$ then $W^{-1}B(W^{-1/2}b)=W^{-1/2}Mb=\lambda W^{-1/2}b$, so $a=W^{-1/2}b$ is an eigenvector of $W^{-1}B$ with the same eigenvalue. The vectors $\bar x_k-\bar x$ satisfy $\sum_kn_k(\bar x_k-\bar x)=0$, so they span a space of dimension at most $g-1$; hence $\operatorname{rank}B\le\min(g-1,p)$, and $M$ has at most that many nonzero eigenvalues. For $g=2$, $\bar x_1-\bar x=\frac{n_2}{n}d$ and $\bar x_2-\bar x=-\frac{n_1}{n}d$, which gives $B=\frac{n_1n_2}{n}dd^{\mathsf T}$; then $W^{-1}Ba\propto W^{-1}d$ for every $a$, and $W=(n-2)S_{\text{pl}}$. ∎

Estimating the error rate. The apparent error rate — the proportion of training observations misclassified by a rule built from those same observations — is optimistic, because the rule was tuned to them. Honest estimates use a separate test sample or leave-one-out (Lachenbruch's method): classify each $x_i$ by the rule computed without $x_i$ and count the errors (Exercise II.8). Under normality, $\Phi(-D/2)$ also estimates the error rate, but it is biased downwards for small samples because $D^2$ overestimates $\Delta^2$.

✏️ Example 3 — Fisher's discriminant for two groups
Training samples of $n_1=n_2=20$ items from two production lines give $\bar x_1=(5,3)^{\mathsf T}$, $\bar x_2=(3,4)^{\mathsf T}$ and pooled covariance matrix $S_{\text{pl}}=\begin{pmatrix}2&1\\1&2\end{pmatrix}$. (a) Find Fisher's discriminant function and the allocation rule, and allocate $x_0=(4,3)^{\mathsf T}$. (b) Estimate the misclassification probability under normality. (c) Compare the separation achieved by Fisher's direction with that of the direction $d$ of the mean difference. (d) Is the separation statistically significant?
(a) Direction $d=(2,-1)^{\mathsf T}$ and $S_{\text{pl}}^{-1}=\frac13\begin{pmatrix}2&-1\\-1&2\end{pmatrix}$, so $\hat a=S_{\text{pl}}^{-1}d=\frac13(5,-4)^{\mathsf T}$. Any positive multiple gives the same rule; use $\hat y=5x_1-4x_2$.
(a) Rule The group means of $\hat y$ are $25-12=13$ and $15-16=-1$, so $\hat m=6$: allocate to line 1 iff $5x_1-4x_2\ge6$. For $x_0$: $20-12=8\ge6$, so $x_0$ goes to line 1.
(b) Error rate $D^2=d^{\mathsf T}S_{\text{pl}}^{-1}d=\frac13(10+4)=\frac{14}3=4.667$, $D=2.160$, and $\Phi(-D/2)=\Phi(-1.080)=0.140$: about $14\%$ of items would be misallocated (an optimistic estimate, see above). Check: the variance of $\hat y$ is $(5,-4)S_{\text{pl}}(5,-4)^{\mathsf T}=50-40+32=42$, and $(13-(-1))^2/42=196/42=14/3=D^2$.
(c) Comparison For $a=d$: $J(d)=\frac{(d^{\mathsf T}d)^2}{d^{\mathsf T}S_{\text{pl}}d}=\frac{25}{6}=4.167\lt4.667$. The mean-difference direction ignores the correlation between the variables; Fisher's direction tilts away from $d$ to where the within-group spread is smaller.
(d) Test $T^2=\frac{20\cdot20}{40}D^2=46.67$, and $F=\frac{n_1+n_2-p-1}{p(n_1+n_2-2)}T^2=\frac{37}{76}\times46.67=22.72$ on $(2,37)$ degrees of freedom, far above $F_{2,37,0.05}=3.25$ ($p\approx4\times10^{-7}$). The mean vectors differ, so discrimination is worthwhile.
✏️ Example 4 — Prove or disprove
(a) If each variable is multiplied by a positive constant, the principal components (as linear combinations of the original variables, up to scaling) do not change.
(b) For $p=2$ and $\rho_{12}\gt0$, the first principal component of the correlation matrix is always $(Z_1+Z_2)/\sqrt2$.
(c) Fisher's rule is unchanged if every observation $x$ is replaced by $Cx+c$ with $C$ nonsingular.
(d) If two populations have equal mean vectors, no linear rule $\{a^{\mathsf T}x\ge t\}$ has $P(2\mid1)+P(1\mid2)\lt1$.
(a) False Let $\Sigma=\operatorname{diag}(4,1)$: the first component is $X_1$. Replace $X_2$ by $3X_2$: now $\Sigma=\operatorname{diag}(4,9)$ and the first component is $3X_2$, a different variable altogether. Scaling changes the eigenvectors because $C\Sigma C$ is not similar to $\Sigma$ for a diagonal $C\ne cI$.
(b) True $R=\begin{pmatrix}1&\rho\\\rho&1\end{pmatrix}$ has eigenvalues $1+\rho$ and $1-\rho$ with eigenvectors $(1,1)/\sqrt2$ and $(1,-1)/\sqrt2$, whatever $\rho\gt0$; for $\rho\lt0$ the roles swap, and for $\rho=0$ every direction is a principal direction. The direction carries no information about the strength of the correlation; only the eigenvalues do.
(c) True The new means are $C\bar x_k+c$, so $d\mapsto Cd$, and $S_{\text{pl}}\mapsto CS_{\text{pl}}C^{\mathsf T}$, so $\hat a\mapsto(C^{\mathsf T})^{-1}S_{\text{pl}}^{-1}C^{-1}Cd=(C^{\mathsf T})^{-1}\hat a$. Then $\hat a_{\text{new}}^{\mathsf T}\big((Cx_0+c)-\tfrac12(C\bar x_1+C\bar x_2+2c)\big)$ $=\hat a^{\mathsf T}C^{-1}C\big(x_0-\tfrac12(\bar x_1+\bar x_2)\big)$, which is the old $\hat a^{\mathsf T}x_0-\hat m$. Every observation is allocated exactly as before, and $D^2$ is unchanged.
(d) False Equal means do not make the populations indistinguishable. Take $p=1$, $\mathcal P_1=N(0,4)$, $\mathcal P_2=N(0,1)$ and the rule "allocate to $\mathcal P_1$ iff $x\ge1$". Then $P(2\mid1)=P(N(0,4)\lt1)=\Phi(0.5)=0.6915$ and $P(1\mid2)=P(N(0,1)\ge1)=0.1587$, with sum $0.850\lt1$. The statement is true when the covariance matrices are also equal (then the two populations are identical); here the optimal rule is quadratic, $|x|\gt c$ (Exercise II.3).

Cluster Analysis

Discriminant analysis starts from labelled groups. Cluster analysis looks for groups that nobody has labelled: market segments among customers, subtypes of a disease among patients, communities among species sampled at different sites. The starting point is a measure of how unlike two objects are.

📘 Definition 7.14 — Dissimilarities

A dissimilarity on objects $1,\dots,n$ is a function $d$ with $d(i,j)=d(j,i)\ge0$ and $d(i,i)=0$; it is a metric if also $d(i,k)\le d(i,j)+d(j,k)$, and an ultrametric if $d(i,k)\le\max\{d(i,j),d(j,k)\}$. Common choices for $x_i,x_j\in\mathbb{R}^p$ are the Euclidean distance $\|x_i-x_j\|$, the city-block distance $\sum_l|x_{il}-x_{jl}|$, Euclidean distance after standardising each variable, and the Mahalanobis distance $\sqrt{(x_i-x_j)^{\mathsf T}S^{-1}(x_i-x_j)}$. For binary attributes, with $a$ = number of attributes present in both objects, $b$ and $c$ = present in only one, and $e$ = absent from both, the simple matching similarity is $(a+e)/(a+b+c+e)$ and the Jaccard similarity is $a/(a+b+c)$; a dissimilarity is $1-$similarity.

📘 Definition 7.15 — Agglomerative hierarchical clustering, linkages and the dendrogram

Start with the $n$ singleton clusters. At each step, merge the two clusters $A,B$ with the smallest inter-cluster distance $D(A,B)$, record the merge height $h=D(A,B)$, and repeat until one cluster remains ($n-1$ merges). The linkage defines $D$ from $d$:

  • single linkage (nearest neighbour): $D(A,B)=\min\{d(i,j):i\in A,j\in B\}$;
  • complete linkage (furthest neighbour): $D(A,B)=\max\{d(i,j):i\in A,j\in B\}$;
  • average linkage (UPGMA): $D(A,B)=\frac1{|A||B|}\sum_{i\in A}\sum_{j\in B}d(i,j)$;
  • centroid linkage: $D(A,B)=\|\bar x_A-\bar x_B\|$; Ward's method: $D(A,B)$ is the increase in the within-cluster sum of squares caused by merging $A$ and $B$.

The dendrogram is the tree that draws each merge as a horizontal bar at its height joining the two merged clusters. Cutting it at a level $h$ gives a partition into clusters. The cophenetic distance $c(i,j)$ is the height at which $i$ and $j$ first belong to the same cluster.

📐 Theorem 7.33 — Monotone merge heights and the ultrametric property

For single, complete and average linkage:

  1. after $A$ and $B$ merge, $\min\{D(A,C),D(B,C)\}$ $\le D(A\cup B,C)$ $\le\max\{D(A,C),D(B,C)\}$ for every other cluster $C$;
  2. the successive merge heights are non-decreasing: $h_1\le h_2\le\dots\le h_{n-1}$;
  3. the cophenetic distance is an ultrametric: $c(i,k)\le\max\{c(i,j),c(j,k)\}$ for all $i,j,k$.

For centroid linkage (2) can fail: a later merge can occur at a smaller height (an inversion).

Proof. (1) For single and complete linkage, $D(A\cup B,C)$ is the minimum or the maximum over the pairs in $(A\times C)\cup(B\times C)$, i.e. $\min$ or $\max$ of $D(A,C)$ and $D(B,C)$. For average linkage, splitting the double sum,

$$D(A\cup B,C)=\frac{|A|\,D(A,C)+|B|\,D(B,C)}{|A|+|B|},$$

a weighted mean, which lies between the two values. (2) Let $A,B$ merge at height $h=D(A,B)$, the minimum of $D$ over all pairs of current clusters. After the merge, the distances between clusters not involving $A\cup B$ are unchanged and hence $\ge h$, and by (1) $D(A\cup B,C)\ge\min\{D(A,C),D(B,C)\}\ge h$. So every distance between the new clusters is $\ge h$, and the next merge height is $\ge h$. (3) Let $h=\max\{c(i,j),c(j,k)\}$ and let $t$ be the later of the two merge steps at which $i,j$ and $j,k$ first share a cluster. After step $t$ (clusters only grow), $i$ and $j$ are in one cluster and $j$ and $k$ are in one cluster, which must be the same cluster; so $i$ and $k$ were joined at step $t$ or earlier, at a height $\le h_t=h$ by (2). ∎

The centroid counterexample: three points at the vertices of an equilateral triangle of side $1$. The first merge joins two of them at height $1$; their centroid is the midpoint of a side, at distance $\sqrt3/2=0.866$ from the third vertex, so the second merge happens at $0.866\lt1$ and the dendrogram crosses itself (Exercise III.3). Ward's method is monotone (its update formula, of Lance–Williams type, gives $D(A\cup B,C)\ge D(A,B)$ by the same argument).

📐 Theorem 7.34 — Single linkage, connected components and minimum spanning trees

For $h\ge0$ let $G_h$ be the graph on the objects with an edge $\{i,j\}$ whenever $d(i,j)\le h$. The clusters obtained by performing all single-linkage merges of height at most $h$ are exactly the connected components of $G_h$. Consequently, the $n-1$ single-linkage merge heights are the edge lengths of a minimum spanning tree of the complete graph with edge weights $d(i,j)$.

Proof. Each single-linkage merge of $A$ and $B$ at height $D(A,B)\le h$ is caused by a pair $i\in A,j\in B$ with $d(i,j)=D(A,B)\le h$, i.e. an edge of $G_h$ between them; by induction every cluster formed by merges of height $\le h$ is connected in $G_h$. Conversely, by Theorem 7.33(2) the merges of height $\le h$ are exactly the first ones, and when they are finished every remaining pair of clusters has $D\gt h$ — otherwise a further merge of height $\le h$ would occur. So no edge of $G_h$ joins two different clusters, and each cluster is a union of components of $G_h$. Being connected, each cluster is exactly one component. For the last statement: single linkage examines the pairs in increasing order of $d$ and joins two clusters whenever the pair links different clusters; this is Kruskal's algorithm for the minimum spanning tree, whose accepted edges have lengths equal to the merge heights. ∎

This explains the chaining behaviour of single linkage: two dense groups joined by a thin chain of intermediate points are merged at the small height of the chain's links. Complete linkage favours compact clusters of similar diameter; average linkage is a compromise.

✏️ Example 5 — Single, complete and average linkage on five objects
Five objects have the dissimilarity matrix $$\begin{array}{c|ccccc} &A&B&C&D&E\\\hline A&0&2&6&10&9\\B&2&0&4.5&8.5&8\\C&6&4.5&0&4&7\\D&10&8.5&4&0&3\\E&9&8&7&3&0\end{array}$$ Find the merge sequence and heights under single, complete and average linkage, draw the dendrograms for single and complete linkage, and give the two-cluster partitions.
First two merges The smallest entry is $d(A,B)=2$, and after it the smallest is $d(D,E)=3$ under all three linkages (any linkage distance involving $\{A,B\}$ is at least $\min$ of two entries $\ge4.5$). So $\{A,B\}$ forms at $2$ and $\{D,E\}$ at $3$.
Single $D(AB,C)=\min(6,4.5)=4.5$, $D(DE,C)=\min(4,7)=4$, $D(AB,DE)=\min(10,9,8.5,8)=8$. So $C$ joins $\{D,E\}$ at $4$; finally $D(AB,CDE)=\min(4.5,8)=4.5$. Heights $2,3,4,4.5$; two clusters $\{A,B\},\{C,D,E\}$.
Complete $D(AB,C)=\max(6,4.5)=6$, $D(DE,C)=\max(4,7)=7$, $D(AB,DE)=10$. So $C$ joins $\{A,B\}$ at $6$; finally $D(ABC,DE)=\max(10,9,8.5,8,4,7)=10$. Heights $2,3,6,10$; two clusters $\{A,B,C\},\{D,E\}$.
Average $D(AB,C)=\frac{6+4.5}{2}=5.25$, $D(DE,C)=\frac{4+7}2=5.5$, $D(AB,DE)=\frac{10+9+8.5+8}{4}=8.875$. So $C$ joins $\{A,B\}$ at $5.25$; then $D(ABC,DE)=\frac{10+9+8.5+8+4+7}{6}=7.75$. Heights $2,3,5.25,7.75$; same partition as complete linkage.
Dendrograms The bars are drawn at the merge heights; the dashed lines cut each tree into two clusters.
single linkage complete linkage 024 048 ABCDE ABCDE cut at 4.25cut at 8
Comment $C$ is close to $D$ (distance $4$) but far from $E$ ($7$), and moderately close to both $A$ and $B$. Single linkage looks only at the nearest member and attaches $C$ to $\{D,E\}$; complete and average linkage look at all members and attach it to $\{A,B\}$. The final single-linkage height $4.5$ is much smaller than the complete-linkage height $10$: single linkage always gives the lowest dendrogram (its heights are minima). The single-linkage heights $2,3,4,4.5$ are the edges $AB,DE,CD,BC$ of a minimum spanning tree (Theorem 7.34).

Hierarchical methods give a whole family of partitions. If the number $K$ of clusters is fixed in advance, one can instead optimise a criterion directly.

📘 Definition 7.16 — $k$-means clustering

For data $x_1,\dots,x_n\in\mathbb{R}^p$ and a partition $\mathcal C=\{C_1,\dots,C_K\}$ into nonempty clusters with means $\bar x_k$, the within-cluster, between-cluster and total sums of squares are

$$W(\mathcal C)=\sum_{k=1}^K\sum_{i\in C_k}\|x_i-\bar x_k\|^2,$$ $$B(\mathcal C)=\sum_{k=1}^K|C_k|\,\|\bar x_k-\bar x\|^2,$$ $$T=\sum_{i=1}^n\|x_i-\bar x\|^2 .$$

$k$-means clustering seeks a partition minimising $W(\mathcal C)$. Lloyd's algorithm starts from $K$ centres $c_1,\dots,c_K$ and repeats two steps until nothing changes: assignment — put each $x_i$ in the cluster of its nearest centre (keeping its current cluster in case of a tie); update — replace each centre by the mean of its cluster.

📐 Theorem 7.35 — Properties of $k$-means and Lloyd's algorithm
  1. For any finite set $C$ and any $c\in\mathbb{R}^p$: $\sum_{i\in C}\|x_i-c\|^2$ $=\sum_{i\in C}\|x_i-\bar x_C\|^2+|C|\,\|\bar x_C-c\|^2$. So the mean is the unique best centre.
  2. For every partition, $T=W(\mathcal C)+B(\mathcal C)$; minimising $W$ is the same as maximising $B$.
  3. Each step of Lloyd's algorithm does not increase $\Phi(\mathcal C,c)=\sum_k\sum_{i\in C_k}\|x_i-c_k\|^2$. As long as no cluster becomes empty, the algorithm stops after finitely many steps at a partition in which every point is at least as close to its own cluster mean as to any other mean.
  4. The limit depends on the starting centres and need not minimise $W$ (Example 6).

Proof. (1) Write $x_i-c=(x_i-\bar x_C)+(\bar x_C-c)$ and expand: the cross term is $2(\bar x_C-c)^{\mathsf T}\sum_{i\in C}(x_i-\bar x_C)=0$. (2) Apply (1) to each cluster with $c=\bar x$ and add: $\sum_k\sum_{i\in C_k}\|x_i-\bar x\|^2$ $=\sum_k\big(\sum_{i\in C_k}\|x_i-\bar x_k\|^2+|C_k|\|\bar x_k-\bar x\|^2\big)$, i.e. $T=W+B$; $T$ does not depend on the partition. (3) The assignment step minimises $\Phi(\cdot,c)$ for fixed centres, since each term $\|x_i-c_{k(i)}\|^2$ is minimised separately; the update step minimises $\Phi(\mathcal C,\cdot)$ for a fixed partition by (1). Hence $\Phi$ never increases. After an update, $\Phi(\mathcal C,c)=W(\mathcal C)$. If the next assignment changes the partition to $\mathcal C'$, some point has moved to a strictly nearer centre (ties keep the old cluster), so $\Phi(\mathcal C',c)\lt\Phi(\mathcal C,c)$, and after the following update $W(\mathcal C')\le\Phi(\mathcal C',c)\lt W(\mathcal C)$. Thus $W$ strictly decreases each time the partition changes, no partition can occur twice, and since there are finitely many partitions the algorithm stops; at that point no point is strictly closer to another mean. (4) is shown by Example 6. ∎

In practice $k$-means is run from many random starts and the best result kept. Because $W$ always decreases as $K$ grows (Exercise III.6), $K$ is chosen by other criteria: an "elbow" in the plot of the minimum $W$ against $K$, the ratio $B/T$, the silhouette width, or the gap statistic. $k$-means implicitly assumes compact, roughly spherical clusters of similar spread, and it depends on the scale of the variables, like PCA.

✏️ Example 6 — Lloyd's algorithm can stop at a local minimum
Cluster the seven numbers $1,2,3,8,9,10,25$ into $K=2$ groups by Lloyd's algorithm (a) starting from centres $1$ and $2$; (b) starting from centres $1$ and $25$. Compare the values of $W$ and find the global minimum. What is the minimum for $K=3$?
(a) With centres $1,2$, only the point $1$ is nearer to $1$: clusters $\{1\}$ and $\{2,3,8,9,10,25\}$, means $1$ and $57/6=9.5$. Reassign with the midpoint $5.25$: clusters $\{1,2,3\}$ and $\{8,9,10,25\}$, means $2$ and $13$. The midpoint is now $7.5$, which gives the same clusters: Lloyd stops. $W=(1+0+1)+(25+16+9+144)$ $=2+194=196$.
(b) With centres $1,25$, every point except $25$ is nearer to $1$: clusters $\{1,2,3,8,9,10\}$ and $\{25\}$, means $5.5$ and $25$; the midpoint $15.25$ separates the same clusters, so Lloyd stops at once. $W=20.25+12.25+6.25$ $+6.25+12.25+20.25=77.5$.
Global minimum In an optimal partition every point is nearest to its own cluster mean (otherwise moving it to the nearer mean lowers $W$, as in the proof of Theorem 7.35(3)); in one dimension the sets of points nearest to each of two means are the two sides of their midpoint, so the clusters are intervals and only the $6$ "cut points" need checking. Cutting after $10$ gives $77.5$; after $9$: $165.7$; after $8$: $189.7$; after $3$: $196$; after $2$: $274.5$; after $1$: $341.5$. So (b) is the global minimum and (a) is a local minimum that Lloyd cannot escape: each point of $\{1,2,3\}$ is nearer $2$ than $13$, and each of $8,9,10,25$ is nearer $13$.
Comment The isolated value $25$ dominates the criterion: squared distances make $k$-means sensitive to outliers. With $K=3$ the partition $\{1,2,3\},\{8,9,10\},\{25\}$ gives $W=2+2+0=4$, and $B/T=1-4/T$ with $T=\sum(x_i-\bar x)^2=403.43$, i.e. $B/T=0.990$.
Interactive 2 — Lloyd's Algorithm for k-Means

Each assignment step colours every point by its nearest centre (the shaded background shows the regions of points nearest to each centre); each update step moves every centre (✚) to the mean of its points, leaving a trail. The objective $\Phi=\sum_i\|x_i-c_{k(i)}\|^2$ can only go down (Theorem 7.35). Press Play: after convergence the next starting configuration is tried, and the readout compares the final $W$ from three different starts — they need not agree. Try the elongated clusters with K = 2: k-means prefers a wrong but "rounder" split. On structureless uniform data it still returns clusters.

iteration · next step—
objective Φ (= W after update)—
B/T = 1 − W/T (current clusters)—
points that switched—
final W from starts 1 / 2 / 3—

Canonical Correlation Analysis

Sometimes the variables come in two natural blocks: physical measurements and performance scores of athletes, climate variables and crop yields, a set of blood tests and a set of symptoms. Canonical correlation analysis (H. Hotelling, 1936) asks for the linear combination of the first block that is most correlated with a linear combination of the second, and then for further pairs carrying new information. In this subsection $X$ is a $p$-vector and $Y$ a $q$-vector, and $Y$ no longer denotes principal components. Write

$$\operatorname{Cov}\begin{pmatrix}X\\Y\end{pmatrix}=\begin{pmatrix}\Sigma_{11}&\Sigma_{12}\\\Sigma_{21}&\Sigma_{22}\end{pmatrix},\qquad\Sigma_{21}=\Sigma_{12}^{\mathsf T},$$

with $\Sigma_{11}$ and $\Sigma_{22}$ positive definite, and $m=\min(p,q)$.

📘 Definition 7.17 — Canonical variates and canonical correlations

The first pair of canonical variates is a pair $U_1=a_1^{\mathsf T}X$, $V_1=b_1^{\mathsf T}Y$ with $\operatorname{Var}(U_1)=\operatorname{Var}(V_1)=1$ that maximises $\operatorname{corr}(a^{\mathsf T}X,b^{\mathsf T}Y)$; the maximum $\rho_1^*$ is the first canonical correlation. For $k=2,\dots,m$, the $k$-th pair $(U_k,V_k)$ maximises the same correlation subject to unit variances and to $U_k$ being uncorrelated with $U_1,\dots,U_{k-1}$ and $V_k$ with $V_1,\dots,V_{k-1}$; the maximum is $\rho_k^*$.

📐 Theorem 7.36 — Computing canonical correlations

Let $K=\Sigma_{11}^{-1/2}\Sigma_{12}\Sigma_{22}^{-1/2}$ (a $p\times q$ matrix) have singular value decomposition $K=\sum_{j=1}^m\rho_ju_jv_j^{\mathsf T}$ with $\rho_1\ge\dots\ge\rho_m\ge0$, orthonormal $u_1,\dots,u_m\in\mathbb{R}^p$ and orthonormal $v_1,\dots,v_m\in\mathbb{R}^q$. Then $\rho_k^*=\rho_k$, and the canonical variates are

$$U_k=u_k^{\mathsf T}\Sigma_{11}^{-1/2}X,\qquad V_k=v_k^{\mathsf T}\Sigma_{22}^{-1/2}Y .$$

Equivalently, $\rho_1^{*2}\ge\dots\ge\rho_m^{*2}$ are the $m$ largest eigenvalues of

$$\Sigma_{11}^{-1}\Sigma_{12}\Sigma_{22}^{-1}\Sigma_{21}\quad(p\times p),$$

and $a_k$ is a corresponding eigenvector, normalised by $a_k^{\mathsf T}\Sigma_{11}a_k=1$; then $b_k\propto\Sigma_{22}^{-1}\Sigma_{21}a_k$. The canonical variates satisfy $\operatorname{corr}(U_k,V_l)=0$ for $k\ne l$ as well.

Proof. Put $c=\Sigma_{11}^{1/2}a$ and $d=\Sigma_{22}^{1/2}b$. Then $\operatorname{Var}(a^{\mathsf T}X)=c^{\mathsf T}c$, $\operatorname{Var}(b^{\mathsf T}Y)=d^{\mathsf T}d$ and $\operatorname{Cov}(a^{\mathsf T}X,b^{\mathsf T}Y)=a^{\mathsf T}\Sigma_{12}b=c^{\mathsf T}Kd$, so the problem is to maximise $c^{\mathsf T}Kd$ over unit vectors $c,d$. Using the SVD and then Cauchy–Schwarz,

$$c^{\mathsf T}Kd=\sum_{j=1}^m\rho_j(c^{\mathsf T}u_j)(v_j^{\mathsf T}d)$$ $$\le\rho_1\Big(\sum_j(c^{\mathsf T}u_j)^2\Big)^{1/2}\Big(\sum_j(v_j^{\mathsf T}d)^2\Big)^{1/2}\le\rho_1,$$

because $\sum_j(c^{\mathsf T}u_j)^2\le\|c\|^2=1$ (Bessel's inequality) and likewise for $d$. Equality holds at $c=u_1$, $d=v_1$, so $\rho_1^*=\rho_1$ with $a_1=\Sigma_{11}^{-1/2}u_1$, $b_1=\Sigma_{22}^{-1/2}v_1$. For the $k$-th pair, $\operatorname{Cov}(a^{\mathsf T}X,U_j)=a^{\mathsf T}\Sigma_{11}\Sigma_{11}^{-1/2}u_j=c^{\mathsf T}u_j$, so the constraints say $c\perp u_1,\dots,u_{k-1}$ and similarly $d\perp v_1,\dots,v_{k-1}$. The terms $j\lt k$ of the sum then vanish and the same estimate gives $c^{\mathsf T}Kd\le\rho_k$, with equality at $(u_k,v_k)$. Moreover $\operatorname{Cov}(U_k,V_l)=u_k^{\mathsf T}Kv_l=\rho_l\,u_k^{\mathsf T}u_l=0$ for $k\ne l$. Finally, $KK^{\mathsf T}u_k=\rho_k^2u_k$ reads $\Sigma_{11}^{-1/2}\Sigma_{12}\Sigma_{22}^{-1}\Sigma_{21}\Sigma_{11}^{-1/2}u_k=\rho_k^2u_k$; multiplying on the left by $\Sigma_{11}^{-1/2}$ gives $\Sigma_{11}^{-1}\Sigma_{12}\Sigma_{22}^{-1}\Sigma_{21}a_k=\rho_k^2a_k$, and $K^{\mathsf T}u_k=\rho_kv_k$ gives $b_k=\Sigma_{22}^{-1/2}v_k\propto\Sigma_{22}^{-1}\Sigma_{21}a_k$ when $\rho_k\gt0$. ∎

📐 Theorem 7.37 — Properties of canonical correlations
  1. Invariance: the canonical correlations of $(AX+\alpha,\ BY+\beta)$ equal those of $(X,Y)$ for all nonsingular $A$ ($p\times p$), $B$ ($q\times q$) and vectors $\alpha,\beta$. In particular they can be computed from correlation matrices.
  2. Bounds: $0\le\rho_k^*\le1$; $\rho_1^*\ge|\operatorname{corr}(X_i,Y_j)|$ for all $i,j$; and $\rho_1^*\ge R_{Y_j\cdot X}$, the multiple correlation coefficient of $Y_j$ on $X$ (§7.2). If $q=1$, $\rho_1^*=R_{Y\cdot X}$.
  3. Rank: the number of nonzero canonical correlations is $\operatorname{rank}\Sigma_{12}$; all are $0$ iff $\Sigma_{12}=0$, which for jointly normal $(X,Y)$ means that $X$ and $Y$ are independent.
  4. $\rho_1^*=1$ iff $a^{\mathsf T}X-b^{\mathsf T}Y$ is almost surely constant for some $a\ne0$, $b\ne0$; this cannot happen when the joint covariance matrix is positive definite.

Proof. (1) As $a$ ranges over $\mathbb{R}^p\setminus\{0\}$, so does $A^{\mathsf T}a$, and $a^{\mathsf T}(AX+\alpha)=(A^{\mathsf T}a)^{\mathsf T}X+\text{const}$. So the families of linear combinations, their correlations and the uncorrelatedness constraints are the same for both pairs of vectors, and the successive maxima coincide. Taking $A,B$ diagonal with entries $1/\sqrt{\sigma_{ii}}$ standardises the variables. (2) $\rho_k^*=\rho_k$ is a correlation, and a maximum over a set containing $a=e_i$ (a standard basis vector), $b=e_j$, so $\rho_1^*\ge\operatorname{corr}(X_i,Y_j)$; replacing $b$ by $-b$ handles the absolute value. If $q=1$, the matrix of Theorem 7.36 has the single nonzero eigenvalue $\sigma_{YX}\Sigma_{11}^{-1}\sigma_{XY}/\sigma_{YY}$ (its trace, since it has rank one), where $\sigma_{XY}=\operatorname{Cov}(X,Y)$; this is the squared multiple correlation $R^2_{Y\cdot X}$ of §7.2, so $\rho_1^*=R_{Y\cdot X}$, the largest correlation between $Y$ and a linear combination of $X$. For general $q$, fixing $b=e_j$ restricts the maximisation to the pair $(X,Y_j)$, whose canonical correlation is $R_{Y_j\cdot X}$; hence $\rho_1^*\ge R_{Y_j\cdot X}$. (3) $\Sigma_{11}^{-1/2}$ and $\Sigma_{22}^{-1/2}$ are nonsingular, so $\operatorname{rank}K=\operatorname{rank}\Sigma_{12}$, which is the number of nonzero singular values. For jointly normal vectors, zero cross-covariance is equivalent to independence (§7.1). (4) A correlation equals $1$ iff the two variables are almost surely linearly related with positive slope; then $(a^{\mathsf T},-b^{\mathsf T})$ times the joint vector has variance $0$, so the joint covariance matrix is singular. ∎

Sample canonical correlations and a test. Replacing $\Sigma$ by the sample covariance (or correlation) matrix gives sample canonical correlations $r_1\ge\dots\ge r_m$ and sample canonical variates. The following result, quoted without the distributional part of the proof, is the standard test.

📐 Theorem 7.38 — Testing canonical correlations (Bartlett)

Let the $n$ observations of $(X,Y)$ be iid $N_{p+q}$ with positive definite covariance matrix and sample correlation matrix $R=\begin{pmatrix}R_{11}&R_{12}\\R_{21}&R_{22}\end{pmatrix}$. The likelihood ratio test of $H_0:\Sigma_{12}=0$ (independence of $X$ and $Y$) rejects for small values of

$$\Lambda=\frac{\det R}{\det R_{11}\,\det R_{22}}=\prod_{k=1}^m(1-r_k^2),$$

and under $H_0$, for large $n$, Bartlett's statistic $-\big(n-1-\tfrac12(p+q+1)\big)\log\Lambda$ is approximately $\chi^2_{pq}$. To test that only the first $s$ canonical correlations are nonzero, use

$$-\big(n-1-\tfrac12(p+q+1)\big)\sum_{k=s+1}^m\log(1-r_k^2)$$ $$\approx\ \chi^2_{(p-s)(q-s)} .$$

Proof of the identity. By the Schur complement formula, $\det R=\det R_{11}\det(R_{22}-R_{21}R_{11}^{-1}R_{12})$, and $R_{22}-R_{21}R_{11}^{-1}R_{12}=R_{22}^{1/2}(I-\hat K^{\mathsf T}\hat K)R_{22}^{1/2}$ with $\hat K=R_{11}^{-1/2}R_{12}R_{22}^{-1/2}$. The eigenvalues of $\hat K^{\mathsf T}\hat K$ are $r_1^2,\dots,r_m^2$ together with $q-m$ zeros, so $\det(I-\hat K^{\mathsf T}\hat K)=\prod_k(1-r_k^2)$ and $\det R=\det R_{11}\det R_{22}\prod_k(1-r_k^2)$. The ratio is unchanged if $R$ is replaced by $S$, because the diagonal scalings cancel. That this ratio is the likelihood ratio statistic to the power $2/n$ is a standard computation with the normal likelihood: the unrestricted maximum involves $\det\hat\Sigma$, the maximum under $\Sigma_{12}=0$ involves $\det\hat\Sigma_{11}\det\hat\Sigma_{22}$, and the exponential terms are equal. The $\chi^2$ approximation is Wilks' theorem (§5.1) — $H_0$ removes the $pq$ free parameters of $\Sigma_{12}$ — with Bartlett's correction factor improving the approximation. ∎

✏️ Example 7 — Canonical correlations of two pairs of variables
Two reading scores $X=(X_1,X_2)$ and two arithmetic scores $Y=(Y_1,Y_2)$ have correlation matrix with blocks $$R_{11}=R_{22}=\begin{pmatrix}1&0.5\\0.5&1\end{pmatrix},$$ $$R_{12}=\begin{pmatrix}0.6&0.4\\0.4&0.6\end{pmatrix}.$$ (a) Find the canonical correlations and variates. (b) Check the answer with the eigenvalue form of Theorem 7.36 and with the trace and determinant. (c) Treating these as sample correlations from $n=50$ pupils, test $H_0:\Sigma_{12}=0$ and $H_0$: "the second canonical correlation is $0$" at the $5\%$ level.
(a) Symmetry All three blocks have the form $\begin{pmatrix}\alpha&\beta\\\beta&\alpha\end{pmatrix}$ and so share the eigenvectors $(1,1)$ and $(1,-1)$. Try sums and differences. $\operatorname{Var}(X_1+X_2)=1+1+2(0.5)=3$, $\operatorname{Var}(Y_1+Y_2)=3$, $\operatorname{Cov}(X_1+X_2,Y_1+Y_2)$ $=0.6+0.4+0.4+0.6=2$, so the correlation is $2/3$. $\operatorname{Var}(X_1-X_2)=1+1-1=1$, $\operatorname{Var}(Y_1-Y_2)=1$, $\operatorname{Cov}(X_1-X_2,Y_1-Y_2)$ $=0.6-0.4-0.4+0.6=0.4$. Also $X_1+X_2$ and $X_1-X_2$ are uncorrelated (equal variances), as are $Y_1+Y_2$ and $Y_1-Y_2$.
(a) Answer $\rho_1^*=2/3$ with $U_1=(X_1+X_2)/\sqrt3$, $V_1=(Y_1+Y_2)/\sqrt3$ (total reading versus total arithmetic), and $\rho_2^*=0.4$ with $U_2=X_1-X_2$, $V_2=Y_1-Y_2$ (the contrast between the two skills in each block). Note that $\rho_1^*=0.667$ exceeds every single cross-correlation (at most $0.6$), as Theorem 7.37(2) requires.
(b) Check $R_{11}^{-1}=\frac1{0.75}\begin{pmatrix}1&-0.5\\-0.5&1\end{pmatrix}$, and $M=R_{11}^{-1}R_{12}R_{22}^{-1}R_{21}=\frac1{225}\begin{pmatrix}68&32\\32&68\end{pmatrix}$, with eigenvalues $\frac{100}{225}=\frac49$ (eigenvector $(1,1)$) and $\frac{36}{225}=0.16$ (eigenvector $(1,-1)$): $\rho^*=\frac23,\ 0.4$. Also $\operatorname{tr}M=\frac{136}{225}=0.6044=\frac49+0.16$ and $\det M=\frac{(\det R_{12})^2}{\det R_{11}\det R_{22}}$ $=\frac{0.2^2}{0.75^2}=0.0711=\frac49\times0.16$.
(c) Tests The factor is $n-1-\frac12(p+q+1)=49-2.5=46.5$. For $\Sigma_{12}=0$: $-46.5\,[\log(5/9)+\log0.84]$ $=46.5\times0.7622=35.44$ $\gt\chi^2_{4,0.05}=9.49$; reject ($p\approx4\times10^{-7}$). For the second correlation alone: $-46.5\log0.84=8.11\gt\chi^2_{1,0.05}=3.84$ ($p=0.004$); reject again. Both canonical relations are significant: the blocks are related through overall ability and through the reading–arithmetic contrast.
Comment The joint $4\times4$ correlation matrix is positive definite (its eigenvalues are $0.3,0.5,0.7,2.5$), so these correlations are consistent; in exercises with invented correlations this must always be checked.
⚠️ Counterexamples and pitfalls
  1. PCA depends on the units. With $\Sigma=\begin{pmatrix}1&0.6\\0.6&1\end{pmatrix}$ (both variables in metres) the first component is $(X_1+X_2)/\sqrt2$ with $80\%$ of the variance; record $X_2$ in centimetres and the first component is essentially $X_2$ alone, with $99.99\%$ (Exercise I.7). Covariance-based and correlation-based PCA are different analyses (Example 1).
  2. Correlation-matrix PCA with $p=2$ always gives $45^\circ$. The directions $(1,\pm1)/\sqrt2$ do not depend on $\rho$; only the eigenvalues $1\pm\rho$ do (Example 4(b), Interactive 1).
  3. Repeated eigenvalues make components arbitrary. If $\Sigma=\sigma^2I$, every orthonormal basis gives principal components; software output is then an accident of rounding.
  4. Uncorrelated is not independent. Principal components are always uncorrelated, but independent only under (for example) multivariate normality.
  5. Large variance is not importance. In regression on principal components, the component that predicts the response can be the one with the smallest variance: if $X_1,X_2$ have equal variances, $\operatorname{corr}(X_1,X_2)=0.99$ and $Y=X_1-X_2$, the response is a function of the second component only.
  6. The first principal axis is not the regression line. It minimises perpendicular, not vertical, distances; its slope lies strictly between the slopes of the two regression lines when $0\lt|r|\lt1$ (Example 2, Exercise I.8).
  7. Fisher's direction is not the mean difference. $S_{\text{pl}}^{-1}d$ differs from $d$ unless $d$ is an eigenvector of $S_{\text{pl}}$; in Exercise II.2 the means differ in both variables but the optimal rule uses only $x_1$.
  8. A variable with no mean difference can still help. Adding $X_2$ with equal means but correlation $0.8$ with $X_1$ raises $\Delta^2$ from $1$ to $2.78$ and lowers the error rate from $0.309$ to $0.202$ (Exam corner E5).
  9. Equal means do not prevent discrimination when the covariance matrices differ (Example 4(d)); the optimal rule is then quadratic.
  10. The apparent error rate is optimistic. In Exercise II.8 it is $0$ while leave-one-out gives $25\%$.
  11. Single linkage chains; centroid linkage inverts. Points $1,2,4,7,11,16$ merge one at a time under single linkage (Exercise III.1); the equilateral triangle gives a centroid-linkage dendrogram whose second merge is lower than its first (Theorem 7.33).
  12. $k$-means finds local minima (Example 6), always finds clusters even in uniform noise (Interactive 2), splits elongated clusters wrongly, is pulled by outliers, and its $W$ decreases with $K$, so minimising $W$ cannot choose $K$.
  13. The first canonical correlation can be far larger than every pairwise correlation. With $\operatorname{corr}(X_1,X_2)=0.8$ and $\operatorname{corr}(Y,X_1)=-\operatorname{corr}(Y,X_2)=0.3$, $\rho_1^*=0.949$ (Exercise IV.5). Conversely, canonical weights are not measures of importance: they change with the correlations inside each block.

Exercises

I
Principal components.
  • 1 Find the principal components of $\Sigma=\begin{pmatrix}3&1\\1&3\end{pmatrix}$, the proportion of variance explained by the first, and $\operatorname{corr}(Y_1,X_1)$.
  • 2 Find the principal components of $\Sigma=\begin{pmatrix}4&2&0\\2&4&0\\0&0&3\end{pmatrix}$ and the proportions of variance explained by the first one and by the first two.
  • 3 Find the eigenvalues and eigenvectors of the equicorrelation matrix $R=(1-\rho)I_p+\rho\mathbf 1\mathbf 1^{\mathsf T}$. For which $\rho$ is $R$ positive definite? For $p=5$, $\rho=0.6$, what proportion of the variance does the first component explain?
  • 4 Prove that $\sum_{k=1}^p\operatorname{corr}(Y_k,X_i)^2=1$ for each $i$ when $\Sigma$ is positive definite.
  • 5 Show that $\Sigma$ and $\Sigma+cI$ ($c\gt0$) have the same principal directions, and that the proportion of variance explained by the first component is a non-increasing function of $c$. Interpret $\Sigma+cI$.
  • 6 A sample of $n=200$ gives $\bar x=(10,20)^{\mathsf T}$ and $S=\begin{pmatrix}4.88&3.84\\3.84&7.12\end{pmatrix}$. Find the sample principal components, the scores of $x_0=(13,24)^{\mathsf T}$, and an approximate $95\%$ confidence interval for $\lambda_1$ under normality.
  • 7 Two lengths in metres have $\Sigma=\begin{pmatrix}1&0.6\\0.6&1\end{pmatrix}$. Find the first principal component and its share of the variance. Now record $X_2$ in centimetres. Find the new covariance matrix, the angle between the new first principal direction and the $X_2$-axis, and its share.
  • 8 Show that $\sum_i\|(x_i-\bar x)-(a^{\mathsf T}(x_i-\bar x))a\|^2$ $=(n-1)(\operatorname{tr}S-a^{\mathsf T}Sa)$ for every unit vector $a$. For $p=2$ and $s_{12}\gt0$, prove that the slope of the first principal axis lies between the slopes $s_{12}/s_{11}$ (regression of $x_2$ on $x_1$) and $s_{22}/s_{12}$ (regression of $x_1$ on $x_2$, drawn in the same plane). Check with $S=\begin{pmatrix}5&2\\2&2\end{pmatrix}$.
  • 9 (Applied) A PCA of six standardised water-quality measurements gives eigenvalues $2.9,\ 1.4,\ 0.8,\ 0.5,\ 0.3,\ 0.1$. Give the cumulative proportions, and the number of components kept by Kaiser's rule and by an $80\%$ rule. Which would you report, and why?
Check lab: eigen-decomposition of a covariance or correlation matrix

Type a symmetric matrix of size up to $5\times5$, rows separated by semicolons. The lab computes its eigenvalues (Jacobi rotations), unit eigenvectors, the proportions of variance and their cumulative sums, optionally after converting a covariance matrix to a correlation matrix. Use it for Examples 1 and 2 and Exercises I.1–I.3, I.6, I.7.

eigenvalues λ₁ ≥ λ₂ ≥ …—
proportions (cumulative)—
trace; determinant—
1 Eigenvalues $3\pm1$: $Y_1=(X_1+X_2)/\sqrt2$ with variance $4$, $Y_2=(X_1-X_2)/\sqrt2$ with variance $2$. Proportion $4/6=2/3$. $\operatorname{corr}(Y_1,X_1)=\frac{(1/\sqrt2)\cdot2}{\sqrt3}=\sqrt{2/3}=0.816$.
2 The matrix is block diagonal: the $2\times2$ block gives $6$ and $2$ with $(1,1,0)/\sqrt2$ and $(1,-1,0)/\sqrt2$; the last variable gives $3$. Ordered: $Y_1=(X_1+X_2)/\sqrt2$ ($6$), $Y_2=X_3$ ($3$), $Y_3=(X_1-X_2)/\sqrt2$ ($2$). Proportions $6/11=54.5\%$ and $9/11=81.8\%$.
3 $R\mathbf 1=(1-\rho+p\rho)\mathbf 1$, so $1+(p-1)\rho$ is an eigenvalue with eigenvector $\mathbf 1/\sqrt p$; for $v\perp\mathbf 1$, $Rv=(1-\rho)v$, so $1-\rho$ has multiplicity $p-1$. $R$ is positive definite iff both are positive: $-\frac1{p-1}\lt\rho\lt1$. For $p=5$, $\rho=0.6$: eigenvalues $3.4$ and $0.4$ (four times); the first component (the average, up to scale) explains $3.4/5=68\%$. The other components are not unique (pitfall 3).
4 By Theorem 7.27(3), $\sum_k\operatorname{corr}(Y_k,X_i)^2=\frac1{\sigma_{ii}}\sum_k\lambda_ke_{ik}^2$, and $\sum_k\lambda_ke_{ik}^2$ is the $(i,i)$ entry of $\sum_k\lambda_ke_ke_k^{\mathsf T}=\Sigma$, namely $\sigma_{ii}$. (Equivalently: $X_i-\mu_i=\sum_ke_{ik}Y_k$ is an exact linear function of the uncorrelated $Y_k$, so its squared multiple correlation with them is $1$.)
5 $(\Sigma+cI)e_k=(\lambda_k+c)e_k$: same eigenvectors, eigenvalues shifted by $c$, same order. The first proportion is $g(c)=\frac{\lambda_1+c}{\operatorname{tr}\Sigma+pc}$, and $g'(c)=\frac{\operatorname{tr}\Sigma-p\lambda_1}{(\operatorname{tr}\Sigma+pc)^2}\le0$ because $\lambda_1\ge\operatorname{tr}\Sigma/p$; it tends to $1/p$. $\Sigma+cI$ is the covariance of $X+\varepsilon$ with independent measurement noise of variance $c$ in every variable: noise does not rotate the axes but dilutes the structure.
6 $\operatorname{tr}S=12$, $\det S=34.7456-14.7456=20$, so $\hat\lambda=10,2$. $(S-10I)e=0$: $-5.12e_1+3.84e_2=0$, $\hat e_1=(3,4)^{\mathsf T}/5$, $\hat e_2=(4,-3)^{\mathsf T}/5$. For $x_0-\bar x=(3,4)$: scores $\hat y_1=(9+16)/5=5$, $\hat y_2=(12-12)/5=0$ — the point lies exactly on the first axis. With $z_{0.025}\sqrt{2/200}=0.196$: $10/1.196\le\lambda_1\le10/0.804$, i.e. $(8.36,\ 12.44)$.
7 In metres: $Y_1=(X_1+X_2)/\sqrt2$, share $1.6/2=80\%$. In centimetres $X_2'=100X_2$: $\Sigma'=\begin{pmatrix}1&60\\60&10000\end{pmatrix}$, $\lambda_1'=10000.36$, $\hat e_1'\approx(0.0060,\ 1.0000)$, an angle of $\arctan(0.0060)=0.34^\circ$ with the $X_2$-axis, and share $10000.36/10001=99.994\%$. The "structure" is now just the change of units.
8 $\|w-(a^{\mathsf T}w)a\|^2=\|w\|^2-(a^{\mathsf T}w)^2$ for unit $a$; sum over $w=x_i-\bar x$: $(n-1)\operatorname{tr}S-(n-1)a^{\mathsf T}Sa$. Slope: write an eigenvector as $(1,m)$. The two rows of $S(1,m)^{\mathsf T}=\lambda(1,m)^{\mathsf T}$ give $\lambda=s_{11}+s_{12}m$ and $s_{12}+s_{22}m=\lambda m$; eliminating $\lambda$, $q(m)=0$ with $q(t)=s_{12}t^2+(s_{11}-s_{22})t-s_{12}$. The product of the roots is $-1$, so there is one positive root $m_+$, and it belongs to the larger eigenvalue because $\lambda=s_{11}+s_{12}m$ increases with $m$. Now $q(s_{12}/s_{11})=\frac{s_{12}}{s_{11}^2}(s_{12}^2-s_{11}s_{22})\lt0$ and $q(s_{22}/s_{12})=\frac{s_{11}s_{22}-s_{12}^2}{s_{12}}\gt0$ when $|r|\lt1$; since $q$ is an upward parabola with $q(0)=-s_{12}\lt0$, it is negative on $(0,m_+)$ and positive on $(m_+,\infty)$, so $\frac{s_{12}}{s_{11}}\lt m_+\lt\frac{s_{22}}{s_{12}}$. For $S=\begin{pmatrix}5&2\\2&2\end{pmatrix}$: $0.4\lt\tfrac12\lt1$ ✓ ($\hat e_1\propto(2,1)$).
9 Cumulative: $48.3\%,\ 71.7\%,\ 85.0\%,\ 93.3\%,\ 98.3\%,\ 100\%$ (the eigenvalues sum to $6=p$ ✓). Kaiser keeps $2$ (eigenvalues $\gt1$); the $80\%$ rule keeps $3$. The scree drops sharply after $2$; report two components if they are interpretable, mentioning that the third adds $13\%$. Neither rule is a test; parallel analysis (see the Nexus) is a better-founded check.
II
Discriminant analysis and classification.
  • 1 $\mathcal P_1=N(0,1)$ and $\mathcal P_2=N(2,1)$, equal costs. Find the optimal rule and its total probability of misclassification (a) with equal priors, (b) with $\pi_1=0.8$, $\pi_2=0.2$. In case (b), what is the TPM of the equal-prior rule?
  • 2 $\mathcal P_1=N_2(\mu_1,\Sigma)$, $\mathcal P_2=N_2(\mu_2,\Sigma)$ with $\mu_1=(2,1)^{\mathsf T}$, $\mu_2=(0,0)^{\mathsf T}$, $\Sigma=\begin{pmatrix}1&0.5\\0.5&1\end{pmatrix}$, equal priors and costs. Find the optimal rule and its error rate. Explain why the rule ignores $x_2$ although the means differ in $x_2$.
  • 3 $\mathcal P_1=N(0,1)$, $\mathcal P_2=N(0,4)$, equal priors and costs. Find the optimal rule, $P(2\mid1)$, $P(1\mid2)$ and the TPM.
  • 4 Training samples of $n_1=n_2=10$ give $\bar x_1=(6,4)^{\mathsf T}$, $\bar x_2=(4,3)^{\mathsf T}$, $S_{\text{pl}}=\begin{pmatrix}4&1\\1&1\end{pmatrix}$. Find Fisher's rule, allocate $x_0=(5,\ 3.8)^{\mathsf T}$, estimate the error rate, and test equality of the mean vectors at the $5\%$ level. Comment.
  • 5 Derive the formulas for $P(2\mid1)$ and $P(1\mid2)$ in Theorem 7.30 for a general threshold $k$, and check them against part 1(b).
  • 6 (Regression and discrimination) Code the group membership as $z_i=1$ for the $n_1$ cases of $\mathcal P_1$ and $z_i=0$ for the $n_2$ cases of $\mathcal P_2$, and regress $z$ on $x$ by least squares with an intercept. Prove that the vector of slopes is proportional to $S_{\text{pl}}^{-1}(\bar x_1-\bar x_2)$.
  • 7 Three populations $N_2(\mu_k,I)$ with $\mu_1=(0,0)$, $\mu_2=(4,0)$, $\mu_3=(0,4)$ and equal priors. Describe the optimal regions and allocate $x_0=(2.5,\ 2)$.
  • 8 One-dimensional training data: group 1: $1,\ 2,\ 3,\ 4.3$; group 2: $4.6,\ 6,\ 7,\ 8$. The rule allocates to group 1 iff $x$ is below the midpoint of the two group means. Find the apparent error rate and the leave-one-out error rate.
1 $\log\frac{f_1}{f_2}=-\frac{x^2}2+\frac{(x-2)^2}2=2-2x$. (a) Allocate to $\mathcal P_1$ iff $x\le1$; TPM $=\Phi(-1)=0.1587$. (b) $k=\pi_2/\pi_1=0.25$: $2-2x\ge\log0.25=-1.386$ iff $x\le1.693$; TPM $=0.8(1-\Phi(1.693))+0.2\,\Phi(-0.307)$ $=0.8(0.0452)+0.2(0.3795)$ $=0.1121$. The rule $x\le1$ still has TPM $0.8(0.1587)+0.2(0.1587)=0.1587$, so using the priors saves about $30\%$ of the errors.
2 $\Sigma^{-1}=\frac1{0.75}\begin{pmatrix}1&-0.5\\-0.5&1\end{pmatrix}$, $a=\Sigma^{-1}(\mu_1-\mu_2)$ $=\frac1{0.75}(2-0.5,\ -1+1)=(2,0)$. $W(x)=2x_1-2$: allocate to $\mathcal P_1$ iff $x_1\ge1$. $\Delta^2=(2,1)\cdot(2,0)=4$, error $\Phi(-1)=0.1587$. Reason: $E[X_2\mid X_1=x_1]=\mu_{2}+0.5(x_1-\mu_{1})$ equals $1+0.5(x_1-2)=0.5x_1$ under $\mathcal P_1$ and $0+0.5x_1$ under $\mathcal P_2$, with the same conditional variance: once $x_1$ is known, $x_2$ has the same distribution in both populations.
3 $\log\frac{f_1}{f_2}=-\frac{x^2}{2}+\frac{x^2}{8}+\log2=\log2-\frac{3x^2}8\ge0$ iff $x^2\le\frac83\log2=1.8484$, i.e. $|x|\le c=1.3596$. $P(2\mid1)=2(1-\Phi(1.3596))=0.1740$; $P(1\mid2)=P(|N(0,4)|\le1.3596)$ $=2\Phi(0.6798)-1=0.5034$; TPM $=\frac12(0.1740+0.5034)=0.3387$. A quadratic rule with equal means.
4 $d=(2,1)$, $S_{\text{pl}}^{-1}=\frac13\begin{pmatrix}1&-1\\-1&4\end{pmatrix}$, $\hat a=\frac13(1,2)$; use $\hat y=x_1+2x_2$, with group means $14$ and $10$, so $\hat m=12$. $x_0$: $5+7.6=12.6\ge12$ → $\mathcal P_1$. $D^2=\frac13(2+2)=\frac43$, $\Phi(-D/2)=\Phi(-0.577)=0.282$. $T^2=5\times\frac43=6.67$, $F=\frac{17}{36}T^2=3.15\lt F_{2,17,0.05}=3.59$ ($p=0.069$): the mean vectors are not significantly different at $5\%$, so the rule may be little better than guessing; more data are needed before using it.
5 $W(X)\sim N(\frac12\Delta^2,\Delta^2)$ under $\mathcal P_1$: $P(2\mid1)=P(W\lt\log k)=\Phi\big(\frac{\log k-\Delta^2/2}{\Delta}\big)$. Under $\mathcal P_2$, $W\sim N(-\frac12\Delta^2,\Delta^2)$: $P(1\mid2)=1-\Phi\big(\frac{\log k+\Delta^2/2}{\Delta}\big)=\Phi\big(\frac{-\log k-\Delta^2/2}{\Delta}\big)$. In 1(b), $\Delta=2$, $\log k=-1.386$: $\Phi(-1.693)=0.0452$ and $\Phi(-0.307)=0.3795$ ✓.
6 With an intercept the slopes are $b=T^{-1}\sum_i(x_i-\bar x)z_i$, where $T=\sum_i(x_i-\bar x)(x_i-\bar x)^{\mathsf T}$. Now $\sum_i(x_i-\bar x)z_i=n_1(\bar x_1-\bar x)=\frac{n_1n_2}{n}d=:c\,d$. The matrix form of $T=W+B$ (same proof as Theorem 7.35(2), with outer products in place of squared norms) and $B=c\,dd^{\mathsf T}$ (proof of Theorem 7.32) give $T=W+c\,dd^{\mathsf T}$ with $W=(n-2)S_{\text{pl}}$. The Sherman–Morrison formula gives $T^{-1}d=\frac{W^{-1}d}{1+c\,d^{\mathsf T}W^{-1}d}$, so $b=\frac{c}{1+c\,d^{\mathsf T}W^{-1}d}\,W^{-1}d\propto S_{\text{pl}}^{-1}d$. Least squares on a $0/1$ response reproduces Fisher's direction (but not, in general, the right cut-off).
7 With $\Sigma=I$ and equal priors, allocate to the nearest mean (Theorem 7.32(1)). The boundaries are the perpendicular bisectors: $x_1=2$ (between $\mu_1,\mu_2$), $x_2=2$ (between $\mu_1,\mu_3$) and $x_1=x_2$ (between $\mu_2,\mu_3$). $R_1=\{x_1\lt2,x_2\lt2\}$, $R_2=\{x_1\ge2,x_1\gt x_2\}$, $R_3=\{x_2\ge2,x_2\ge x_1\}$ (boundaries assigned arbitrarily). For $x_0$: squared distances $10.25$, $6.25$, $10.25$ → $\mathcal P_2$.
8 Means $2.575$ and $6.4$, midpoint $4.4875$: all eight training points are correctly classified, apparent error $0$. Leave-one-out: dropping $4.3$ gives group-1 mean $2$ and midpoint $4.2$, and $4.3\gt4.2$ is misclassified; dropping $4.6$ gives group-2 mean $7$, midpoint $4.7875$, and $4.6$ is misclassified; the other six stay correct. LOO error $2/8=25\%$: the two boundary points were "classifying themselves".
III
Cluster analysis.
  • 1 Cluster the six numbers $1,2,4,7,11,16$ with Euclidean distance by single, complete and average linkage. Give the merge heights and the two-cluster partitions.
  • 2 Prove that for points on a line the single-linkage merge heights are exactly the $n-1$ gaps between consecutive ordered points, in increasing order.
  • 3 Three points form an equilateral triangle of side $1$. Find the merge heights under single, complete, average and centroid linkage, and under Ward's method (heights = increase in $W$). Which are monotone?
  • 4 Run Lloyd's algorithm with $K=2$ on $(0,0),(1,0),(0,1),(5,5),(6,5),(5,6)$ starting from the centres $(0,0)$ and $(1,0)$. Give each step, the final $W$, $T$ and $B/T$.
  • 5 Prove $T=W(\mathcal C)+B(\mathcal C)$ directly for a partition into two clusters, and express $B$ in terms of the two cluster means only.
  • 6 Let $W^*(K)$ be the minimum of $W$ over partitions into $K$ nonempty clusters ($1\le K\le n$, distinct points). Prove that $W^*(K+1)\lt W^*(K)$ for $K\lt n$ and $W^*(n)=0$. What does this imply for choosing $K$?
  • 7 Two plant specimens are scored for presence (1) or absence (0) of eight rare traits: $(1,0,0,1,1,0,0,0)$ and $(1,0,0,0,1,0,0,1)$. Compute the simple matching and Jaccard similarities. Which is more sensible here?
  • 8 (Ward) Prove that merging clusters $A$ and $B$ increases $W$ by $\frac{|A||B|}{|A|+|B|}\|\bar x_A-\bar x_B\|^2$. Evaluate it for $A=\{(0,0),(2,0)\}$, $B=\{(5,4)\}$ and check directly.
1 Single: the gaps are $1,2,3,4,5$, so $\{1,2\}$ at $1$, then $4$ joins at $2$, $7$ at $3$, $11$ at $4$, $16$ at $5$ — pure chaining; two clusters $\{1,2,4,7,11\},\{16\}$. Complete: $\{1,2\}$ at $1$; then $D(\{1,2\},4)=3=d(4,7)$, a tie. Merging $\{1,2,4\}$ at $3$ gives $\{7,11\}$ at $4$, $\{7,11,16\}$ at $9$, all at $15$, and two clusters $\{1,2,4\},\{7,11,16\}$. Merging $\{4,7\}$ at $3$ instead gives $\{11,16\}$ at $5$, $\{1,2,4,7\}$ at $6$, all at $15$, and two clusters $\{1,2,4,7\},\{11,16\}$. Ties can change the tree, so a careful report says how they were broken. Average: $\{1,2\}$ at $1$, $\{1,2,4\}$ at $2.5$, $\{7,11\}$ at $4$, $\{1,2,4,7,11\}$ at $40/6=6.67$ (versus $D(\{7,11\},16)=7$), all at $55/5=11$; two clusters $\{1,2,4,7,11\},\{16\}$.
2 Order the points $x_{(1)}\lt\dots\lt x_{(n)}$ with gaps $g_j=x_{(j+1)}-x_{(j)}$. By Theorem 7.34 the clusters at level $h$ are the components of $G_h$. If $x_{(i)}$ and $x_{(j)}$ ($i\lt j$) are joined by an edge, every gap between them is at most $x_{(j)}-x_{(i)}\le h$; and each gap $g_l\le h$ is itself an edge. So the components of $G_h$ are the maximal runs of consecutive points whose gaps are all $\le h$, and their number is $1+\#\{l:g_l\gt h\}$. As $h$ increases this number drops by one exactly when $h$ passes a gap value, so the merge heights are $g_1,\dots,g_{n-1}$ in increasing order (with repetitions for equal gaps).
3 Single, complete, average: first merge at $1$, then the third point is at distance $1$ from both, so the second merge is at $1$ (monotone, a tie). Centroid: second merge at $\sqrt3/2=0.866\lt1$ — an inversion. Ward: first merge increases $W$ by $\frac{1\cdot1}{2}\cdot1=0.5$; second by $\frac{2\cdot1}{3}\cdot\frac34=0.5$; monotone. Only centroid fails.
4 Assignment: $(0,0)$ and $(0,1)$ go to $c_1=(0,0)$; the rest to $c_2=(1,0)$. Update: $c_1=(0,0.5)$, $c_2=(4.25,4)$, $W=37.25$. Assignment: $(1,0)$ is now nearer $c_1$ ($1.25$ vs $26.6$); clusters $\{(0,0),(1,0),(0,1)\}$ and $\{(5,5),(6,5),(5,6)\}$. Update: $c_1=(\frac13,\frac13)$, $c_2=(\frac{16}3,\frac{16}3)$, $W=\frac43+\frac43=\frac83=2.667$. The next assignment changes nothing: stop. $\bar x=(\frac{17}6,\frac{17}6)$, $T=\frac{233}3=77.67$, $B=75$, $B/T=0.966$.
5 For clusters $C_1,C_2$ of sizes $n_1,n_2$: $\sum_{i\in C_k}\|x_i-\bar x\|^2$ $=\sum_{i\in C_k}\|x_i-\bar x_k\|^2+n_k\|\bar x_k-\bar x\|^2$ (cross term $0$); add. Since $\bar x=\frac{n_1\bar x_1+n_2\bar x_2}{n}$, $\bar x_1-\bar x=\frac{n_2}{n}(\bar x_1-\bar x_2)$ and $\bar x_2-\bar x=-\frac{n_1}{n}(\bar x_1-\bar x_2)$, so $B=\frac{n_1n_2^2+n_2n_1^2}{n^2}\|\bar x_1-\bar x_2\|^2=\frac{n_1n_2}{n}\|\bar x_1-\bar x_2\|^2$.
6 Take an optimal $K$-partition; since $K\lt n$ some cluster $C$ has two distinct points. Split off one point $x_j\ne\bar x_C$ (one exists since the points of $C$ are distinct): by Exercise 8 the split reduces $W$ by $\frac{(|C|-1)\cdot1}{|C|}\|x_j-\bar x_{C\setminus j}\|^2\gt0$. Hence $W^*(K+1)\lt W^*(K)$, and with singletons $W=0$. Minimising $W$ always chooses $K=n$; one needs a penalty or a comparison with a reference (elbow, gap statistic, silhouette).
7 Both present: traits $1,5$ ($a=2$); only one: traits $4$ and $8$ ($b=c=1$); both absent: $e=4$. Simple matching $6/8=0.75$; Jaccard $2/4=0.5$. For rare traits, joint absence says little about similarity (most specimens lack most rare traits), so Jaccard is the better choice.
8 By Theorem 7.35(1) with $C=A\cup B$ and $c=\bar x_{A\cup B}$, $W(A\cup B)=W(A)+W(B)$ $+|A|\|\bar x_A-\bar x_{AB}\|^2+|B|\|\bar x_B-\bar x_{AB}\|^2$, and the last two terms are the $B$ of Exercise 5: $\frac{|A||B|}{|A|+|B|}\|\bar x_A-\bar x_B\|^2$. Here $\frac{2}{3}\|(1,0)-(5,4)\|^2=\frac23\cdot32=21.33$. Directly: $W(A)=2$; the merged mean is $(\frac73,\frac43)$ and $W(A\cup B)=\frac{65+17+128}{9}=\frac{210}9=23.33$; the increase is $21.33$ ✓.
IV
Canonical correlation analysis.
  • 1 Show that for $p=q=1$ the canonical correlation is $|\rho_{XY}|$, and that for $p=1$ (one $X$, several $Y$'s) $\rho_1^{*2}=\sigma_{12}\Sigma_{22}^{-1}\sigma_{21}/\sigma_{11}$, the squared multiple correlation of $X$ on $Y$.
  • 2 $\operatorname{corr}(X,Y_1)=\operatorname{corr}(X,Y_2)=0.6$ and $\operatorname{corr}(Y_1,Y_2)=0.5$. Find the canonical correlation between $X$ and $(Y_1,Y_2)$ and the canonical variate $V_1$.
  • 3 Prove Theorem 7.37(1) directly from the eigenvalue form of Theorem 7.36: show that $\Sigma_{11}^{-1}\Sigma_{12}\Sigma_{22}^{-1}\Sigma_{21}$ changes to a similar matrix under $X\mapsto AX$, $Y\mapsto BY$.
  • 4 Standardised $X=(X_1,X_2)$ and $Y=(Y_1,Y_2)$ have $R_{11}=R_{22}=I$ and $R_{12}=\begin{pmatrix}0.4&0.2\\0.2&0.4\end{pmatrix}$. Find the canonical correlations and variates, and check that the joint correlation matrix is positive definite.
  • 5 $\operatorname{corr}(X_1,X_2)=0.8$, $\operatorname{corr}(Y,X_1)=0.3$, $\operatorname{corr}(Y,X_2)=-0.3$. Find the canonical correlation between $(X_1,X_2)$ and $Y$ and the canonical variate $U_1$. Comment.
  • 6 With $n=60$ observations on $p=3$ and $q=2$ variables, the sample canonical correlations are $0.55$ and $0.20$. Test $H_0:\Sigma_{12}=0$ and then the significance of the second canonical correlation at the $5\%$ level.
  • 7 Prove Theorem 7.37(2) and (4) in detail, and give an example of a singular joint covariance matrix with $\rho_1^*=1$ although no $|\operatorname{corr}(X_i,Y_j)|$ equals $1$.
1 For $p=q=1$, $\operatorname{corr}(aX,bY)=\operatorname{sign}(ab)\rho_{XY}$, maximised at $|\rho_{XY}|$. For $p=1$: $\Sigma_{11}^{-1}\Sigma_{12}\Sigma_{22}^{-1}\Sigma_{21}$ is the $1\times1$ matrix $\sigma_{12}\Sigma_{22}^{-1}\sigma_{21}/\sigma_{11}$, whose only eigenvalue is itself; this is $R^2_{X\cdot Y}$ (§7.2).
2 $\rho^{*2}=r^{\mathsf T}R_{22}^{-1}r$ with $r=(0.6,0.6)$: $R_{22}^{-1}r=\frac1{0.75}(0.6-0.3,\ 0.6-0.3)=(0.4,0.4)$, so $\rho^{*2}=0.48$, $\rho^*=0.693$. $b\propto R_{22}^{-1}r\propto(1,1)$: $V_1=(Y_1+Y_2)/\sqrt3$ (variance $3$ before scaling). Check: $\operatorname{corr}(X,Y_1+Y_2)=1.2/\sqrt3=0.693$ ✓.
3 $\Sigma_{11}\mapsto A\Sigma_{11}A^{\mathsf T}$, $\Sigma_{12}\mapsto A\Sigma_{12}B^{\mathsf T}$, $\Sigma_{22}\mapsto B\Sigma_{22}B^{\mathsf T}$. The new matrix is $(A^{\mathsf T})^{-1}\Sigma_{11}^{-1}A^{-1}\cdot A\Sigma_{12}B^{\mathsf T}$ $\cdot(B^{\mathsf T})^{-1}\Sigma_{22}^{-1}B^{-1}\cdot B\Sigma_{21}A^{\mathsf T}$ $=(A^{\mathsf T})^{-1}M A^{\mathsf T}$ with $M=\Sigma_{11}^{-1}\Sigma_{12}\Sigma_{22}^{-1}\Sigma_{21}$: similar to $M$, hence the same eigenvalues $\rho_k^{*2}$. The loadings change to $(A^{\mathsf T})^{-1}a_k$, so the canonical variates themselves are unchanged.
4 $K=R_{12}$ is symmetric with eigenvalues $0.6$ and $0.2$ (eigenvectors $(1,1)/\sqrt2$, $(1,-1)/\sqrt2$), which are its singular values: $\rho_1^*=0.6$, $U_1=(X_1+X_2)/\sqrt2$, $V_1=(Y_1+Y_2)/\sqrt2$; $\rho_2^*=0.2$, $U_2=(X_1-X_2)/\sqrt2$, $V_2=(Y_1-Y_2)/\sqrt2$. The joint matrix $\begin{pmatrix}I&K\\K&I\end{pmatrix}$ has eigenvalues $1\pm0.6$, $1\pm0.2$, i.e. $0.4,0.8,1.2,1.6$, all positive.
5 $\rho^{*2}=r^{\mathsf T}R_{11}^{-1}r$ with $r=(0.3,-0.3)$: $R_{11}^{-1}r$ $=\frac1{0.36}(0.3+0.24,\ -0.24-0.3)=(1.5,-1.5)$, so $\rho^{*2}=0.45+0.45=0.9$ and $\rho^*=0.949$. $U_1\propto X_1-X_2$ (variance $0.4$), $U_1=(X_1-X_2)/\sqrt{0.4}$. Each $X_i$ alone correlates only $0.3$ with $Y$, but their difference, which removes the large shared component, correlates $0.6/\sqrt{0.4}=0.949$. (The joint matrix has eigenvalues $0.017,1.183,1.8$ — valid.)
6 Factor $n-1-\frac12(p+q+1)=59-3=56$. $\Lambda=(1-0.3025)(1-0.04)=0.6696$; $-56\log\Lambda=22.46\gt\chi^2_{6,0.05}=12.59$ ($p=0.001$): reject independence. Second: $-56\log0.96=2.29\lt\chi^2_{2,0.05}=5.99$ ($p=0.32$): not significant. Report one canonical pair.
7 (2) and (4) as in the proof of Theorem 7.37: $\rho_1^*$ is a maximum over a set containing $(e_i,\pm e_j)$ and the pairs $(a,e_j)$; a correlation is $\pm1$ iff the variables are a.s. affinely related. Example: $X_1,X_2$ with variance $1$ and correlation $0.9$, and $Y=(X_1-X_2)/\sqrt{0.2}$. Then $\operatorname{corr}(Y,X_1)=\frac{1-0.9}{\sqrt{0.2}}=0.224$, $\operatorname{corr}(Y,X_2)=-0.224$, but $U=(X_1-X_2)/\sqrt{0.2}=Y$ gives $\rho_1^*=1$; the joint covariance matrix is singular.
🎯 Exam corner CSIR Part BCSIR Part CGATE ST

E1. CSIR Part B GATE ST A random vector $X=(X_1,X_2,X_3)^{\mathsf T}$ has covariance matrix $\Sigma=\begin{pmatrix}6&2&0\\2&3&0\\0&0&4\end{pmatrix}$. The proportion of the total variance explained by the first two principal components is (A) $53.8\%$; (B) $76.9\%$; (C) $84.6\%$; (D) $69.2\%$.

Idea The matrix is block diagonal; the eigenvalues of $\begin{pmatrix}6&2\\2&3\end{pmatrix}$ solve $\lambda^2-9\lambda+14=0$: $7$ and $2$. With the third variable: $\lambda=7,4,2$, total $13=\operatorname{tr}\Sigma$.
Compute $(7+4)/13=11/13=84.6\%$.
Distractors (A) is $7/13$, the first component alone; (B) is $(6+4)/13$, the two largest variances, not eigenvalues; (D) is $(7+2)/13$, forgetting the third variable's eigenvalue $4$ is larger than $2$.
Answer (C).

E2. CSIR Part B Two populations are $N_2(\mu_1,\Sigma)$ and $N_2(\mu_2,\Sigma)$ with $\mu_1-\mu_2=(2,2)^{\mathsf T}$ and $\Sigma=\begin{pmatrix}2&1\\1&1\end{pmatrix}$. With equal priors and equal costs, the probability that the optimal rule misclassifies an observation from the first population is (A) $\Phi(-1)$; (B) $\Phi(-\sqrt2)$; (C) $\Phi(-2)$; (D) $\Phi(-4)$.

Idea Theorem 7.30: $P(2\mid1)=\Phi(-\Delta/2)$ with $\Delta^2=(\mu_1-\mu_2)^{\mathsf T}\Sigma^{-1}(\mu_1-\mu_2)$.
Compute $\Sigma^{-1}=\begin{pmatrix}1&-1\\-1&2\end{pmatrix}$ ($\det\Sigma=1$), $\Sigma^{-1}(2,2)^{\mathsf T}=(0,2)^{\mathsf T}$, $\Delta^2=4$, $\Delta=2$, so the error is $\Phi(-1)=0.159$.
Distractors (B) uses the Euclidean distance $\|\mu_1-\mu_2\|=2\sqrt2$ in place of $\Delta$; (C) forgets the factor $\frac12$; (D) uses $\Delta^2$ in place of $\Delta/2$.
Answer (A).

E3. CSIR Part B The five numbers $0,1,4,6,12$ are clustered by agglomerative hierarchical clustering with complete linkage and Euclidean distance. The height of the final merge in the dendrogram is (A) $6$; (B) $8$; (C) $9.25$; (D) $12$.

Merges $\{0,1\}$ at $1$; $\{4,6\}$ at $2$. Then $D(\{0,1\},\{4,6\})=\max(4,6,3,5)=6$, $D(\{4,6\},12)=8$, $D(\{0,1\},12)=12$: merge $\{0,1,4,6\}$ at $6$. Finally $D(\{0,1,4,6\},12)=\max(12,11,8,6)=12$.
Distractors (A) is the single-linkage final height ($\min=6$); (C) is the average-linkage final height $\frac{12+11+8+6}{4}=9.25$; (B) is $D(\{4,6\},12)$.
Answer (D). For complete linkage the final height is always the diameter of the whole data set.

E4. CSIR Part C Let $\Sigma$ be a $p\times p$ positive definite covariance matrix with diagonal entries $\sigma_{11},\dots,\sigma_{pp}$ and eigenvalues $\lambda_1\ge\dots\ge\lambda_p$. Which of the following are true? (One or more options may be correct.) (A) $\lambda_1\ge\max_i\sigma_{ii}$. (B) If $D=\operatorname{diag}(\sigma_{11},\dots,\sigma_{pp})$ and $e$ is an eigenvector of $\Sigma$, then $D^{1/2}e$ is an eigenvector of the correlation matrix $D^{-1/2}\Sigma D^{-1/2}$. (C) $\lambda_1\lambda_2\cdots\lambda_p=\det\Sigma$. (D) $\lambda_p\ge\min_i\sigma_{ii}$.

(A) True $\lambda_1=\max_{\|a\|=1}a^{\mathsf T}\Sigma a\ge u_i^{\mathsf T}\Sigma u_i=\sigma_{ii}$ for each standard basis vector $u_i$ (Theorem 7.27(4)).
(B) False For $\Sigma=\begin{pmatrix}5&2\\2&2\end{pmatrix}$ (Example 1), $e=(2,1)/\sqrt5$, and $D^{1/2}e\propto(2\sqrt5,\sqrt2)$, which is not proportional to $(1,1)$; but the correlation matrix has eigenvectors $(1,\pm1)/\sqrt2$. Rescaling does not map eigenvectors to eigenvectors.
(C) True $\det\Sigma=\det(E\Lambda E^{\mathsf T})=\det\Lambda$ (Theorem 7.27(1)).
(D) False In fact $\lambda_p\le\min_i\sigma_{ii}$; in Example 1, $\lambda_2=1\lt2=\min\sigma_{ii}$.
Answer (A) and (C).

E5. CSIR Part C GATE ST Observations come from $N_p(\mu_1,\Sigma)$ or $N_p(\mu_2,\Sigma)$ with $\mu_1\ne\mu_2$, $\Sigma$ positive definite, equal priors and equal costs. Let $\Delta^2=(\mu_1-\mu_2)^{\mathsf T}\Sigma^{-1}(\mu_1-\mu_2)$. Which of the following are true? (One or more options may be correct.) (A) The rule minimising the total probability of misclassification has a linear boundary. (B) Its total probability of misclassification is $\Phi(-\Delta/2)$. (C) The optimal rule depends on $x$ only through $(\mu_1-\mu_2)^{\mathsf T}x$. (D) Adding a further variable whose mean is the same in both populations can never reduce the minimal total probability of misclassification.

(A) True The log likelihood ratio $W(x)=a^{\mathsf T}(x-\frac{\mu_1+\mu_2}2)$ is linear; the boundary $W=0$ is a hyperplane (Theorem 7.30).
(B) True $P(2\mid1)=P(1\mid2)=\Phi(-\Delta/2)$, so $\frac12P(2\mid1)+\frac12P(1\mid2)=\Phi(-\Delta/2)$.
(C) False The rule depends on $a^{\mathsf T}x$ with $a=\Sigma^{-1}(\mu_1-\mu_2)$, which is not parallel to $\mu_1-\mu_2$ in general. In Exercise II.2, $\mu_1-\mu_2=(2,1)$ but $a=(2,0)$: the rule "$x_1\ge1$" is not a function of $2x_1+x_2$.
(D) False Take $p=1$: $X_1\sim N(0,1)$ versus $N(1,1)$, so $\Delta^2=1$ and the error is $\Phi(-0.5)=0.309$. Add $X_2$ with mean $0$ in both populations, variance $1$ and $\operatorname{corr}(X_1,X_2)=0.8$. Then $\Delta^2=(1,0)\Sigma^{-1}(1,0)^{\mathsf T}=\frac1{1-0.64}=2.78$ and the error falls to $\Phi(-0.833)=0.202$: $X_2$ helps by measuring the noise in $X_1$.
Answer (A) and (B).

E6. CSIR Part C Let $X=(X_1,X_2)^{\mathsf T}$ and $Y=(Y_1,Y_2)^{\mathsf T}$ have a positive definite joint covariance matrix, with canonical correlations $\rho_1^*\ge\rho_2^*$. Which of the following are true? (One or more options may be correct.) (A) $\rho_1^*\ge|\operatorname{corr}(X_i,Y_j)|$ for all $i,j$. (B) The canonical correlations are unchanged if $(X_1,X_2)$ is replaced by $(X_1+X_2,\ X_1-X_2)$. (C) If $|\operatorname{corr}(X_i,Y_j)|\le0.3$ for all $i,j$, then $\rho_1^*\le0.6$. (D) $\rho_1^{*2}+\rho_2^{*2}\le1$.

(A) True $\rho_1^*$ is the maximum of $\operatorname{corr}(a^{\mathsf T}X,b^{\mathsf T}Y)$, and $a=u_i$, $b=\pm u_j$ are admissible (Theorem 7.37(2)).
(B) True $(X_1+X_2,X_1-X_2)=AX$ with $A=\begin{pmatrix}1&1\\1&-1\end{pmatrix}$ nonsingular; Theorem 7.37(1).
(C) False Take $\operatorname{corr}(X_1,X_2)=0.8$, $\operatorname{corr}(Y_1,X_1)=0.3$, $\operatorname{corr}(Y_1,X_2)=-0.3$, and $Y_2$ uncorrelated with everything. The joint correlation matrix is positive definite (eigenvalues $0.017,1,1.183,1.8$), all cross-correlations are at most $0.3$ in absolute value, yet $\rho_1^*=\sqrt{0.9}=0.949$ (Exercise IV.5).
(D) False With standardised variables, $R_{11}=R_{22}=I$ and $R_{12}=0.9I$, the joint matrix has eigenvalues $0.1,0.1,1.9,1.9$ (positive definite) and $\rho_1^*=\rho_2^*=0.9$, so $\rho_1^{*2}+\rho_2^{*2}=1.62$. Each canonical correlation is at most $1$, but there is no constraint on their sum of squares.
Answer (A) and (B).
🧑‍🏫 For the teacher

Suggested plan — 3 lectures × 60 min.

  1. Principal components. Motivate with a two-variable scatter; Definition 7.10 and Theorem 7.26 with the full proof (the expansion $a=\sum c_je_j$ is the key idea of the whole section). Theorem 7.27 quickly; Example 1 on the board, including the correlation-matrix version. Project Interactive 1: rotate the trial direction, then switch to $R$ and ask the class why the axes jump to $45^\circ$. Finish with Theorem 7.28 (the $w_j$ argument fits in five minutes) and Example 2.
  2. Discrimination. Definition 7.12 and Theorem 7.29 (the proof is two lines — let students find it). Theorem 7.30 with the error rates; Example 4(d) as a surprise. Fisher's criterion via Cauchy–Schwarz (Theorem 7.31), Example 3, and a short discussion of apparent versus leave-one-out error (Exercise II.8). Mention Theorem 7.32 for several groups.
  3. Clustering and canonical correlation. Definition 7.15, Example 5 with the dendrograms drawn live; Theorem 7.33 and the equilateral-triangle inversion; single linkage as a minimum spanning tree. $k$-means: Theorem 7.35 and Example 6, then Interactive 2 (round clusters, then long thin ones, then uniform noise). Last 20 minutes: canonical correlations — Theorem 7.36 via the SVD, Example 7, Bartlett's test.

Discussion questions. (1) A PCA of ten exam marks has a first component with all loadings positive. Is that a discovery about the students or a consequence of something else? (Think of the equicorrelation matrix.) (2) A screening rule built on 40 patients misclassifies none of them. What would you report to the clinic, and what extra computation would you do? (3) Why can clustering never be "wrong" in the way a hypothesis test can be wrong, and what does that mean for how clusters should be reported?

Misconceptions to watch for. Computing proportions of variance from diagonal entries rather than eigenvalues; forgetting that PCA depends on scale; believing that components with large variance are the important ones; taking $\mu_1-\mu_2$ as the discriminant direction; believing that a variable with equal means is useless for discrimination; trusting the apparent error rate; reading a single-linkage dendrogram as compact groups; expecting $k$-means to find the global optimum or the "true" $K$; thinking that canonical correlations cannot exceed the largest pairwise correlation.

Suggested homework. I(1, 2, 3, 6, 7, 8), II(1, 2, 4, 6, 8), III(1, 3, 4, 6, 8), IV(2, 4, 5, 6); Exam corner E2, E4, E5.

🔬 Research–Teaching NexusResearch-tutored · optional, about 60 minutes

Research question. How many principal components does a data set really have? When the variables are pure noise, how many components does Kaiser's "eigenvalue greater than one" rule keep, and does Horn's parallel analysis — comparing each eigenvalue with the same eigenvalue of simulated noise — do better?

Why it matters. The number of components or factors decides how questionnaires in psychology and education are scored, how many "modes" of climate variability are reported from sea-surface temperature fields, and how many population-structure axes are used to correct genetic association studies. Over-extraction produces spurious structure; under-extraction hides real effects.

What to do.

  1. Simulate $n=100$ observations of $p=10$ independent $N(0,1)$ variables, compute the eigenvalues of the sample correlation matrix, and repeat $1000$ times. Record the average of the largest eigenvalue and the distribution of the number of eigenvalues above $1$.
  2. Compare the largest eigenvalue with the Marchenko–Pastur edge $(1+\sqrt{p/n})^2$, the limit of the largest eigenvalue of a pure-noise correlation matrix as $n,p\to\infty$ with $p/n$ fixed.
  3. Now simulate a two-factor model: variables $1$–$5$ load $0.7$ on one factor, variables $6$–$10$ load $0.5$ on another, with unique variances making each variable's variance $1$. Find the population eigenvalues, then apply Kaiser's rule and parallel analysis (keep component $k$ while $\hat\lambda_k$ exceeds the $95$th percentile of the $k$-th noise eigenvalue from step 1) to $1000$ samples.
  4. Vary $n$ (50, 100, 500) and the loadings, and summarise when each rule recovers the true number of factors.

Tools: Python (numpy) or R; the check lab under Exercise card I for single matrices.

Hand in: A two-page note with a table of the number of components chosen by each rule in each scenario and a recommendation for practitioners.

Going further. Read about the "spiked covariance" model and the phase transition (Baik–Ben Arous–Péché): a population eigenvalue $1+\ell$ produces a sample eigenvalue that separates from the noise bulk only when $\ell\gt\sqrt{p/n}$.

Instructor note (from a simulation with $1000$–$2000$ replicates): for pure noise with $n=100$, $p=10$, the largest sample eigenvalue averages about $1.53$ (the $95$th percentile is about $1.68$, below the asymptotic edge $1.73$), and Kaiser's rule keeps on average about $4.75$ components — usually $4$, $5$ or $6$ — of pure noise. In the two-factor model the population eigenvalues are $2.96$, $2.00$ and then $0.75$ (four times) and $0.51$ (four times); Kaiser keeps $2$ in about $60\%$ of samples and $3$ in most of the rest, while parallel analysis keeps exactly $2$ in essentially every sample. Students usually conclude that Kaiser's rule over-extracts when $p/n$ is not small, and that the sampling spread of eigenvalues, not only their size, must be taken into account.

🧪 Self-check quiz

0/5 correct

Q1. A PCA of the correlation matrix of four variables gives eigenvalues $2.4,\ 0.9,\ 0.5,\ 0.2$. The first component explains

Q2. With group means $\bar x_1,\bar x_2$ and pooled covariance $S_{\text{pl}}$, Fisher's linear discriminant direction is

Q3. Which linkage can produce a dendrogram in which a later merge occurs at a smaller height than an earlier one?

Q4. Lloyd's algorithm for $k$-means is guaranteed to

Q5. When the second set consists of a single variable $Y$ ($q=1$), the first canonical correlation between $X$ and $Y$ equals