Why the Number of Classes Limits Discriminant Dimensions
A data set may have many measured features, but a linear classifier with \(K\) classes does not necessarily need all of them to compare its class scores. The key restriction comes from the class means: after centering them around their grand mean, their weighted deviations must sum to zero. That dependence limits how many independent directions can separate the classes.
This tutorial makes the restriction precise for between-class scatter and connects it to Fisher’s multiclass discriminant problem. The bound is an upper limit, not a promise that every problem will have \(K-1\) useful directions: feature dimension, coincident means, and other dependencies can reduce the number further.
Each term in \(B\) is an outer product of a class-mean deviation with itself. Thus \(B\) records variation among the class means, with larger classes receiving greater weight. Its rank is the number of independent feature-space directions represented by those deviations. Although there are \(K\) deviations, they are not independent: their weighted sum is zero.
The Rank Bound
The limit \(p\) is immediate because \(B\) is a \(p\times p\) matrix. To see the less obvious limit \(K-1\), put the centered class means into a matrix, scaling each column by the square root of its class size: $$ M=\begin{bmatrix} \sqrt{n_1}(\bar{x}_1-\bar{x}) & \cdots & \sqrt{n_K}(\bar{x}_K-\bar{x}) \end{bmatrix}. $$ Then \(B=MM'\). The following proof establishes the bound without relying on a geometric picture alone.
By the definition of the grand mean, \(\sum_{k=1}^K n_k(\bar{x}_k-\bar{x})=0\). Therefore \(M a=0\) for the nonzero vector \(a=(\sqrt{n_1},\ldots,\sqrt{n_K})'\).
Since \(M\) has \(K\) columns and a nonzero vector in its null space, its columns are linearly dependent. Hence \(\operatorname{rank}(M)\leq K-1\). Also, \(M\) has \(p\) rows, so \(\operatorname{rank}(M)\leq p\).
For any vector \(z\in\mathbb{R}^p\), \(z'Bz=z'MM'z=\|M'z\|^2\). Consequently, \(Bz=0\) exactly when \(M'z=0\), so \(\operatorname{rank}(B)=\operatorname{rank}(M)\). Combining the two rank limits proves the claim.
Equivalently, the centered class means have at least one dependence because they sum to zero after weighting. They can span at most a \((K-1)\)-dimensional subspace, and the scatter matrix has no variation outside that subspace. The argument also explains why using a different positive scaling for the scatter matrix does not affect the dimension bound.
Worked Example: Three Classes in Four Features
Suppose three classes have sizes \(n_1=2\), \(n_2=1\), and \(n_3=3\), with means in four-dimensional feature space \(\bar{x}_1=(0,0,0,0)'\), \(\bar{x}_2=(2,0,0,0)'\), and \(\bar{x}_3=(0,3,0,0)'\). Find the grand mean and the rank of \(B\).
The total size is \(n=6\), so $$ \bar{x}=\frac{2\bar{x}_1+\bar{x}_2+3\bar{x}_3}{6} =\left(\frac{1}{3},\frac{3}{2},0,0\right)'. $$ The centered means are $$ \bar{x}_1-\bar{x}=\left(-\frac13,-\frac32,0,0\right)',\quad \bar{x}_2-\bar{x}=\left(\frac53,-\frac32,0,0\right)',\quad \bar{x}_3-\bar{x}=\left(-\frac13,\frac32,0,0\right)'. $$
Only the first two features vary among these means, so \(B\) has zero rows and columns in positions three and four. Its upper-left \(2\times2\) block is obtained by summing the class-size-weighted outer products: $$ B_{1:2,1:2} = \begin{bmatrix} 10/3 & -3\\ -3 & 27/2 \end{bmatrix}. $$ For example, the off-diagonal entry is \(2(1/2)+1(-5/2)+3(-1/2)=-3\). The determinant of this block is \((10/3)(27/2)-(-3)^2=36>0\), so the block has rank two. Thus \(B\) has rank two, exactly \(K-1\), despite having four features.
The weighted centered deviations also check directly: \(2(\bar{x}_1-\bar{x})+(\bar{x}_2-\bar{x})+3(\bar{x}_3-\bar{x})=(0,0,0,0)'\). The dependence is present even though two independent directions remain.
From Scatter Rank to Fisher Discriminant Directions
In the multiclass Fisher discriminant eigenproblem, the between-class scatter is compared with within-class scatter. In the usual nonsingular formulation, the within-class scatter matrix \(W\) is positive definite, and the generalized eigenproblem is $$ Bv=\lambda Wv. $$ Equivalently, it is an ordinary eigenproblem for \(W^{-1/2}BW^{-1/2}\). Since \(W^{-1/2}\) is invertible, multiplication on both sides by it preserves rank. Therefore the transformed between-class matrix has rank \(\operatorname{rank}(B)\), and can have no more than \(K-1\) nonzero eigenvalues. Those nonzero eigenvalues correspond to the Fisher directions with nonzero between-class signal.
This statement is about directions that distinguish the class means, not about how many features were measured or how many coefficients might appear in an unreduced model. It also does not assert that the first \(K-1\) directions are equally useful. If the class means lie in a smaller subspace, there are fewer directions with nonzero between-class signal.
Worked Example: Four Collinear Class Means
Consider four equally sized classes in three features, with means \((0,0,0)'\), \((1,0,0)'\), \((2,0,0)'\), and \((4,0,0)'\). The rank bound gives \(\operatorname{rank}(B)\leq\min(3,3)=3\), but compute the actual rank.
The grand mean is \((7/4,0,0)'\). The four deviations are \((-7/4,0,0)'\), \((-3/4,0,0)'\), \((1/4,0,0)'\), and \((9/4,0,0)'\). If each class has size \(m>0\), then $$ B=m\sum_{k=1}^4(\bar{x}_k-\bar{x})(\bar{x}_k-\bar{x})' =m\left(\frac{49+9+1+81}{16}\right) \begin{bmatrix}1&0&0\\0&0&0\\0&0&0\end{bmatrix} =\frac{35m}{4} \begin{bmatrix}1&0&0\\0&0&0\\0&0&0\end{bmatrix}. $$ This matrix has rank one. Although \(K-1=3\), all class-mean differences point along the first feature axis, so only one direction carries between-class variation.
Why LDA Classification Needs at Most \(K-1\) Directions
The same dimension limit has a direct interpretation for shared-covariance linear discriminant analysis (LDA). Let the class means be \(\mu_1,\ldots,\mu_K\), let the common covariance matrix \(\Sigma\) be positive definite, and let \(\pi_k>0\) be the prior probability of class \(k\). The class score, up to terms common to all classes, is $$ \delta_k(x)=x'\Sigma^{-1}\mu_k-\frac12\mu_k'\Sigma^{-1}\mu_k+\log\pi_k. $$ Classification selects a class with the largest score.
Subtract the score for class 1 from each other score. For \(k=2,\ldots,K\), the result is $$ \delta_k(x)-\delta_1(x) =x'\Sigma^{-1}(\mu_k-\mu_1) -\frac12\left(\mu_k'\Sigma^{-1}\mu_k-\mu_1'\Sigma^{-1}\mu_1\right) +\log\left(\frac{\pi_k}{\pi_1}\right). $$ The terms involving \(x\) depend only on its inner products with the \(K-1\) vectors \(\Sigma^{-1}(\mu_k-\mu_1)\). Thus, even if \(x\) has many features, the score comparisons use at most \(K-1\) linear projections.
More precisely, let \(U\) be the span of those \(K-1\) vectors and let \(P_Ux\) denote the orthogonal projection of \(x\) onto \(U\). Each score difference has the form \(x'u+c\), where \(u\in U\) and \(c\) does not depend on \(x\). Since \(x'u=(P_Ux)'u\), every score comparison can be made using \(P_Ux\) alone. Because \(\dim(U)\leq K-1\), these projected coordinates preserve the LDA decisions.
The role of the covariance assumption is important. Positive definiteness makes \(\Sigma^{-1}\) well defined and maps the mean-difference vectors to discriminant score vectors. Since this map is invertible, it preserves the dimension of their span. If a regularized covariance estimate is positive definite, the same dimension argument applies. A singular, unregularized covariance requires a separate specification of how the classifier is defined; the inverse-based argument above does not apply unchanged.
Worked Example: Reducing Five-Feature LDA to Two Projections
Suppose a three-class LDA model has positive-definite covariance \(\Sigma=I_5\), where \(I_5\) is the five-dimensional identity matrix, and means \(\mu_1=(0,0,0,0,0)'\), \(\mu_2=(1,0,0,0,0)'\), and \(\mu_3=(0,1,0,0,0)'\). Let the priors be \(\pi_1=1/2\), \(\pi_2=1/3\), and \(\pi_3=1/6\). Show which coordinates are needed to compare class scores.
Because \(\Sigma^{-1}=I_5\), the two score-difference vectors are \(\mu_2-\mu_1=(1,0,0,0,0)'\) and \(\mu_3-\mu_1=(0,1,0,0,0)'\). For class 2, $$ \delta_2(x)-\delta_1(x) =x_1-\frac12+\log\left(\frac{2}{3}\right), $$ because \(\mu_2'\mu_2=1\), \(\mu_1'\mu_1=0\), and \(\pi_2/\pi_1=2/3\). For class 3, $$ \delta_3(x)-\delta_1(x) =x_2-\frac12+\log\left(\frac{1}{3}\right), $$ because \(\mu_3'\mu_3=1\) and \(\pi_3/\pi_1=1/3\). Both comparisons depend only on \(x_1\) and \(x_2\); \(x_3,x_4,x_5\) do not affect which score is largest. Here \(K-1=2\), and the two mean differences are independent, so two projections suffice and are needed for these score comparisons.
Common Pitfall: Treating the Bound as an Exact Count
A common mistake is to say that \(K\) classes always produce exactly \(K-1\) discriminant directions. The rank theorem gives an upper bound, not an equality. Equality requires enough features and sufficiently independent class-mean deviations. The collinear example had four classes but rank one; if all class means were identical, \(B\) would be the zero matrix and its rank would be zero.
A related mistake is to count all \(K\) class means as \(K\) independent directions. Centering imposes the identity \(\sum_k n_k(\bar{x}_k-\bar{x})=0\), so at least one dependence is unavoidable. Finally, the rank bound concerns between-class mean separation. It does not by itself say that within-class variation is small, that classification will be accurate, or that every feature outside the discriminant subspace is irrelevant to other scientific questions.
Check Your Understanding
Use the rank argument and score-difference representation to answer these questions.
- Why does the weighted sum of the centered class means equal zero?
- For \(K=6\) classes and \(p=4\) features, what is the largest possible rank of \(B\)?
- Can a four-class problem have between-class scatter of rank one? Give a geometric condition on the class means that would make this possible.
- Under the positive-definite shared-covariance LDA model, which vectors determine the feature directions needed to compare class \(k\) with class 1?
- Does the \(K-1\) bound guarantee that all \(K-1\) directions are useful? Explain.