Eigen-decomposition of a Matrix

Building upon the concept that eigenvectors maintain their direction under a linear transformation $A$, scaled only by an eigenvalue $\lambda$ (i.e., $Ax = \lambda x$), we can now examine how these special vectors and scalars allow us to factorize, or decompose, the matrix $A$ itself. This process, known as eigen-decomposition or sometimes spectral decomposition, provides a powerful way to understand the structure and behavior of the linear transformation represented by $A$.

The Formula for Eigen-decomposition

For a specific category of matrices, namely square matrices that are diagonalizable, we can express the matrix $A$ as a product involving its eigenvalues and eigenvectors:

$A = PDP^{-1}$

Let's clarify what each matrix in this equation represents:

• P: This is an invertible matrix whose columns are the linearly independent eigenvectors of $A$. If $A$ is an $n \times n$ matrix possessing $n$ linearly independent eigenvectors $v_1, v_2, \dots, v_n$, then $P$ is constructed by placing these eigenvectors as its columns: $P = [v_1 | v_2 | \dots | v_n]$.
• D: This is a diagonal matrix containing the eigenvalues of $A$ along its main diagonal. The position of each eigenvalue $\lambda_i$ in $D$ corresponds to the position of its associated eigenvector $v_i$ in $P$. All non-diagonal entries of $D$ are zero. $$D = \begin{bmatrix} \lambda_1 & 0 & \dots & 0 \\ 0 & \lambda_2 & \dots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \dots & \lambda_n \end{bmatrix}$$
• P⁻¹: This represents the inverse of the matrix $P$. Since the columns of $P$ are the eigenvectors, the requirement for $P$ to be invertible is equivalent to requiring that the eigenvectors of $A$ form a basis for the vector space $\mathbb{R}^n$. This means the eigenvectors must be linearly independent.

When is Eigen-decomposition Possible?

It's important to note that not every square matrix can be decomposed in the form $A = PDP^{-1}$. This factorization is only possible if the matrix $A$ is diagonalizable, which means it must possess a complete set of $n$ linearly independent eigenvectors (where $A$ is $n \times n$). Fortunately, this condition holds true for several types of matrices frequently encountered in machine learning:

1. Real Symmetric Matrices: If a matrix $A$ is symmetric ($A = A^T$) and has real-valued entries, it is always diagonalizable. A significant bonus is that its eigenvectors can be chosen to form an orthonormal basis. In this case, the matrix $P$ becomes an orthogonal matrix, meaning its inverse is simply its transpose ($P^{-1} = P^T$). The decomposition simplifies beautifully to $A = PDP^T$. Covariance matrices, which are central to techniques like PCA, are symmetric, making this property highly relevant.
2. Matrices with Distinct Eigenvalues: If an $n \times n$ matrix $A$ has $n$ distinct eigenvalues, then its corresponding eigenvectors are guaranteed to be linearly independent. Consequently, any matrix with distinct eigenvalues is diagonalizable.

Matrices that do not have a full set of linearly independent eigenvectors are termed defective. Such matrices cannot be diagonalized using the $PDP^{-1}$ form. While alternative decompositions exist (like the Jordan Normal Form), they are generally more complex and less frequently required for standard machine learning algorithms.

Geometric and Computational Significance

The eigen-decomposition $A = PDP^{-1}$ is more than just an algebraic manipulation. It offers substantial geometric insight and computational advantages:

1. Understanding Transformations Geometrically: The decomposition clarifies the action of $A$ as a sequence of three fundamental steps:

   • $P^{-1}$: This matrix transforms vectors from the standard coordinate system into a coordinate system defined by the eigenvectors of $A$. Think of it as a "change of basis" to a perspective where the transformation is simpler.
   • $D$: In this eigenvector basis, the transformation is just a scaling along each eigenvector axis. The $i$-th axis (corresponding to eigenvector $v_i$) is scaled by the factor $\lambda_i$.
   • $P$: This matrix transforms the scaled vectors back from the eigenvector basis to the standard coordinate system.

   In essence, $A = PDP^{-1}$ tells us that any linear transformation represented by a diagonalizable matrix $A$ is equivalent to scaling along its eigenvector directions.

   Applying matrix $A$ to a vector is equivalent to changing to the eigenvector basis ($P^{-1}$), scaling along those axes ($D$), and changing back to the standard basis ($P$).

2. Simplifying Matrix Computations: Eigen-decomposition dramatically simplifies calculating powers of a matrix. Consider computing $A^2$: $A^2 = (PDP^{-1})(PDP^{-1}) = PD(P^{-1}P)DP^{-1} = PDIDP^{-1} = PD^2P^{-1}$ Where $I$ is the identity matrix. Extending this pattern, for any positive integer $k$: $A^k = PD^kP^{-1}$ Calculating $D^k$ is computationally very efficient because $D$ is diagonal. We simply raise each diagonal eigenvalue to the power of $k$:

   $$D^k = \begin{bmatrix} \lambda_1^k & 0 & \dots & 0 \\ 0 & \lambda_2^k & \dots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \dots & \lambda_n^k \end{bmatrix}$$

   This avoids the repeated, and often costly, matrix multiplications required to compute $A^k$ directly. This technique finds use in analyzing systems that evolve over time, such as Markov chains or population models.

3. Foundation for Machine Learning Techniques: Understanding eigen-decomposition is fundamental for grasping several important machine learning algorithms. As we'll explore further, Principal Component Analysis (PCA) relies directly on the eigen-decomposition of the data's covariance matrix. The eigenvectors indicate the directions of maximum variance (the principal components), and the eigenvalues quantify this variance. By understanding how $A = PDP^{-1}$ breaks down a transformation (like the one represented by the covariance matrix), you gain a solid foundation for understanding how PCA achieves dimensionality reduction.

Later sections will explore the practical application of these concepts, particularly the role of eigenvalues and eigenvectors in PCA, and demonstrate how to compute these decompositions efficiently using Python libraries like NumPy.