Why QDA Boundaries Have Different Shapes
With class-specific covariance matrices, Gaussian discriminant scores contain different quadratic terms. Equality between two such scores therefore need not define a line or hyperplane: it can define an ellipsoid, a hyperboloid, a parabolic form, or a degenerate set. The shape is determined not just by whether the quadratic term is present, but by its signs, rank, and interaction with the linear term.
The aim here is to classify a pairwise score-tie set. In a problem with more than two classes, some points where two scores tie may still be assigned to a third class. Thus a pairwise tie set is not necessarily all of the actual multiclass decision boundary.
From Gaussian Scores to a Quadratic Equation
For two classes \(i\) and \(j\), let their Gaussian means be \(\mu_i,\mu_j\), their positive-definite covariance matrices be \(\Sigma_i,\Sigma_j\), and their positive prior probabilities be \(\pi_i,\pi_j\). Write \(P_i=\Sigma_i^{-1}\) and \(P_j=\Sigma_j^{-1}\). The log discriminant score for class \(k\), up to a common additive constant, is \(g_k(x)=\log\pi_k-\frac12\log|\Sigma_k|-\frac12(x-\mu_k)^\mathsf{T}\Sigma_k^{-1}(x-\mu_k)\).
Expanding \(h(x)=g_i(x)-g_j(x)\) gives a quadratic polynomial. Its zero set is the pairwise tie set, and its sign determines which of the two scores is larger.
The matrix \(A\) is symmetric, so its eigenvalues describe the signs and rank of the quadratic part. The vector \(b\) matters as well: a component of \(b\) in the null space of \(A\) cannot be removed by completing the square.
Worked Example: An Ellipsoidal Tie Set
Take two classes in two dimensions with \(\mu_i=\mu_j=(0,0)^\mathsf{T}\), equal priors, \(\Sigma_i=I\), and \(\Sigma_j=2I\). Then \(P_i=I\), \(P_j=\frac12 I\), and both covariance determinants are positive, with \(|\Sigma_i|=1\) and \(|\Sigma_j|=4\).
The quadratic coefficient is \(A=\frac12(\frac12I-I)=-\frac14I\). The linear term is zero, and the constant is \(c=-\frac12\log(1/4)=\log 2\). Hence the tie equation is \(-\frac14(x_1^2+x_2^2)+\log 2=0\).
Rearranging gives \(x_1^2+x_2^2=4\log 2\). Since \(\log 2>0\), this is a circle of radius \(2\sqrt{\log 2}\), hence an ellipsoid in two dimensions. The sign check matters: if the right-hand side had been negative, the tie set would have been empty.
Canonical Form and the Role of the Null Space
An orthogonal change of coordinates diagonalizes \(A\). Let its rank be \(r\), and choose orthonormal eigenvectors so the first \(r\) coordinates correspond to its nonzero eigenvalues. Write the coordinates as \(y=(u,w)\), where \(u\in\mathbb R^r\) and \(w\in\mathbb R^{p-r}\). In these coordinates the quadratic part is \(\sum_{k=1}^r\lambda_k u_k^2\), with every \(\lambda_k\ne0\). Split the transformed linear coefficient into \(d_R\) and \(d_N\), corresponding to \(u\) and \(w\).
Proof. The spectral theorem for real symmetric matrices gives an orthogonal matrix \(Q\) with \(Q^\mathsf{T}AQ\) diagonal. In \(y=Q^\mathsf{T}x\), the first \(r\) diagonal entries are the nonzero eigenvalues and the remaining entries are zero. Transforming the linear term gives \(d=Q^\mathsf{T}b=(d_R,d_N)\), which proves the displayed form before any translation. For \(k\le r\), the identity \(\lambda_k u_k^2+(d_R)_k u_k=\lambda_k(u_k+(d_R)_k/(2\lambda_k))^2-(d_R)_k^2/(4\lambda_k)\) completes the square in every nonzero-eigenvalue coordinate. It does not change the term \(d_N^\mathsf{T}w\), since the quadratic form has no \(w\)-terms or cross-terms. If \(d_N\ne0\), choose the first new null coordinate in the direction \(d_N/\|d_N\|\); then \(d_N^\mathsf{T}w=\|d_N\|w_1\). Solving the equation for \(w_1\) expresses it as a quadratic function of the translated \(u\)-coordinates. The remaining null coordinates do not appear, so they are unrestricted. \(\square\)
Nonsingular Forms: Ellipsoids, Hyperboloids, and Cones
When \(A\) has full rank, there are no null coordinates. Completing the square and rescaling coordinates reduces the equation to a signed sum of squares equal to a constant. If all eigenvalues have the same sign, the form is definite. If the translated equation is \(\sum z_k^2=\rho\), it is an ellipsoid for \(\rho>0\), a single point for \(\rho=0\), and empty for \(\rho<0\). Reversing the overall sign gives the same alternatives after changing the sign of \(\rho\).
If \(A\) has both positive and negative eigenvalues, the form is indefinite. After rescaling, its equation is \(\sum_{k=1}^{s}z_k^2-\sum_{k=s+1}^{p}z_k^2=\rho\), where \(s\) is the number of positive eigenvalues. At \(\rho=0\) this is a cone (in two dimensions, a pair of intersecting lines). For nonzero \(\rho\), it is a hyperboloid-type surface. Its number of sheets depends on the sign of \(\rho\): the coordinate group on the side of \(\rho\) determines whether that side has one coordinate or several. In particular, when that group has one coordinate the surface has two sheets; when it has at least two, it has one sheet.
Justification. Orthogonally diagonalize \(A\), translate each coordinate to remove its linear term, and divide each coordinate by the square root of the absolute value of its eigenvalue. These are invertible changes of coordinates, so they preserve whether the set is empty and its basic connected shape. The resulting equations are exactly the positive-definite or signed-sum forms described above. For a definite form, a sum of squares is nonnegative and vanishes only when every coordinate is zero. For an indefinite form, both positive and negative squared terms are available; at zero they balance on a cone, and at a nonzero level they form the corresponding hyperboloid. \(\square\)
Worked Example: A Hyperbolic Tie Set
Let both means be zero, use equal covariance determinants, and set \(\Sigma_i=I\), \(\Sigma_j=\operatorname{diag}(2,\frac12)\). Both determinants are \(1\). The inverse matrices are \(P_i=I\) and \(P_j=\operatorname{diag}(\frac12,2)\), so \(A=\operatorname{diag}(-\frac14,\frac12)\).
Choose priors \(\pi_i=2/3\) and \(\pi_j=1/3\). The linear term is zero, while \(c=\log 2\). Thus the tie equation is \(-\frac14x_1^2+\frac12x_2^2+\log 2=0\), or \(x_1^2-2x_2^2=4\log 2\).
The quadratic form is indefinite because its eigenvalues have opposite signs. The level is nonzero, so the tie set is a hyperbola, not a cone. The right side is positive, and the positive-square group has one coordinate; this hyperbola has two branches.
Singular Forms: Parabolic, Cylindrical, and Degenerate Cases
If \(A\) is singular and \(d_N\ne0\), the tie equation contains a linear term along a null direction. For \(r\ge1\), solving for one such coordinate gives a quadratic graph, called a parabolic-type quadric. If the nonzero-eigenvalue part is definite, it is elliptic-paraboloid-type; if that part is indefinite, it is hyperbolic-paraboloid-type. Any additional null coordinates make it a cylinder over that graph. When \(r=0\), the equation is linear rather than parabolic: it defines a hyperplane if \(b\ne0\).
If \(d_N=0\), the completed-square equation depends only on the \(r\) nonzero-eigenvalue coordinates. The set in \(\mathbb R^p\) is the corresponding level set in those coordinates, extended freely along the \(p-r\) null directions. This gives cylinders over ellipsoids, cones, or hyperboloids when the base is nonempty. In particular, when \(1\le r<p\), a point in the base extends to a lower-dimensional affine set, not an isolated point in \(\mathbb R^p\).
The rank-zero case must be separated. If \(r=0\) and \(d_N=0\), the equation is just \(c=0\): the tie set is all of \(\mathbb R^p\) when \(c=0\), and empty when \(c\ne0\). This prevents the mistaken conclusion that every point-level base produces a lower-dimensional set, regardless of rank.
Worked Example: A Parabolic Tie Set
Take \(\mu_i=(0,0)^\mathsf{T}\), \(\mu_j=(0,1)^\mathsf{T}\), equal priors, \(\Sigma_i=I\), and \(\Sigma_j=\operatorname{diag}(2,1)\). Then \(P_i=I\), \(P_j=\operatorname{diag}(\frac12,1)\), and \(A=\operatorname{diag}(-\frac14,0)\). The linear coefficient is \(b=P_i\mu_i-P_j\mu_j=(0,-1)^\mathsf{T}\).
The determinant ratio is \(1/2\). The constant is \(c=-\frac12\log(1/2)+\frac12\mu_j^\mathsf{T}P_j\mu_j =\frac12\log 2+\frac12\). The second coordinate is a null direction of \(A\), but its linear coefficient is nonzero. Therefore the tie equation is \(-\frac14x_1^2-x_2+\frac12\log 2+\frac12=0\).
Solving for \(x_2\) gives \(x_2=\frac12\log 2+\frac12-\frac14x_1^2\), a downward-opening parabola. The conclusion follows from the nonzero null-space linear term; completing the square in \(x_1\) alone would not eliminate the \(x_2\) term.
Worked Example: Degeneracy and the Rank-Zero Exception
Use \(\mu_i=\mu_j=(0,0)^\mathsf{T}\), equal priors, \(\Sigma_i=I\), and \(\Sigma_j=\operatorname{diag}(2,1)\). As above, \(A=\operatorname{diag}(-\frac14,0)\), \(b=0\), and now \(c=\frac12\log 2\). The tie equation is \(-\frac14x_1^2+\frac12\log 2=0\), so \(x_1=\pm\sqrt{2\log 2}\). These are two parallel lines: the one-dimensional point-level set in the nonzero-eigenvalue coordinate extends along the null coordinate.
For the separate rank-zero case, let both classes have the same mean and covariance, so \(A=0\) and \(b=0\). With equal priors, \(c=0\), and every point ties: the set is all of \(\mathbb R^2\). If instead the priors differ, \(c=\log(\pi_i/\pi_j)\ne0\), and no point ties. These checks show why rank zero cannot be folded into the lower-dimensional affine-set description.
Reading the Geometry Without Overclaiming
The quadratic form describes the pairwise score equality, while the sign of \(h(x)\) indicates which of the two classes has the larger score: \(h(x)>0\) favors class \(i\), and \(h(x)<0\) favors class \(j\). In a multiclass rule, an actual boundary between these two classes consists only of tie points where their common score is also at least as large as every other class score.
A common mistake is to classify a QDA boundary only by looking at whether \(A\) is singular. Singularity alone does not imply a parabola: if the linear term has no null-space component, the result is a cylinder over a lower-dimensional level set. Conversely, a null-space linear component creates a parabolic-type graph when the quadratic rank is positive, but gives a hyperplane when the rank is zero. Another pitfall is to call every zero-level indefinite form an ordinary hyperbola; in two dimensions it is a pair of lines, and in higher dimensions it is a cone.
Check Your Understanding
For each question, state which part of the quadratic equation determines your answer.
- After completing the square, a nonsingular positive-definite form equals a negative constant. What is its real tie set?
- What geometric feature distinguishes a zero-level indefinite form from a nonzero-level indefinite form?
- If \(A\) is singular but the linear coefficient has no component in its null space, why is the tie set cylindrical?
- What is the tie set when \(A=0\), \(b=0\), and \(c=0\)? What if \(c\ne0\)?
- Why might a pairwise QDA tie set contain points that are not on the actual multiclass decision boundary?