Module: Eigenvalues, Multiplicities, and Diagonalization

Review of Previous Concepts

Eigenvalues and Eigenvectors Calculation:
- To find all eigenvalues for a given matrix, calculate the roots of its characteristic polynomial.
- For each eigenvalue, calculate its corresponding eigenvectors by finding the null space of the matrix $(A - ext{lambda} I)$ .
- The basis of this null space forms the eigenspace for that eigenvalue.
Characteristic Equation and Polynomial:
- For an $(n \times n)$ matrix, the characteristic polynomial involves calculating the determinant of $(A - ext{lambda} I)$ where $\text{lambda}$ is the unknown.
- Finding roots of high-degree polynomials can be computationally challenging, especially for large matrices (e.g., $100,000 \times 100,000 $).</li><li>In practical applications, numerical or approximative algorithms are often used to compute eigenvalues for large matrices, but these algorithms are built on the theoretical foundations learned in this course.</li></ul></li><li>Triangular Matrices:<ul><li>Triangular matrices are convenient for finding eigenvalues because the eigenvalues are simply the entries on the main diagonal.</li><li>This is due to the determinant of a triangular matrix being the product of its diagonal entries, which means the characteristic polynomial comes "pre-factored," revealing the roots immediately.</li></ul></li><li>Distinguishing Matrices with Same Eigenvalues:<ul><li>Two different matrices can have the same set of eigenvalues but still possess distinct properties.</li><li>For example, their characteristic polynomials might not be identical if the multiplicities of the eigenvalues differ.</li><li>Example: Matrix with eigenvalue$ -1 $(multiplicity of$ 2 $) and$ 4 $(multiplicity of$ 1 $) versus another matrix with eigenvalue$ -1 $(multiplicity of$ 1 $) and$ 4 $(multiplicity of$ 2 $). This difference highlights the concept of algebraic multiplicity.</li></ul></li></ul><h4 id="4a56c229-4e1d-411d-8482-96f290c6c7aa" data-toc-id="4a56c229-4e1d-411d-8482-96f290c6c7aa" collapsed="false" seolevelmigrated="true">Algebraic Multiplicity (AM)</h4><ul><li>Definition: For an eigenvalue$ \text{lambda}\text{bar} $of a matrix$ A $, its algebraic multiplicity (denoted$ AM(\text{lambda}\text{bar}) $) is the number of times that$ ( \text{lambda} - \text{lambda}\text{bar} ) $is a factor in the characteristic polynomial$ (PA(\text{lambda})) $.<ul><li>Here,$ \text{lambda} $is the unknown in the polynomial, and$ \text{lambda}_\text{bar} $is a specific eigenvalue.</li></ul></li><li>Example (from slides): If$ (P_A(\text{lambda})) = (\text{lambda} + 1)^2 (\text{lambda} - 4) $(or equivalently$ ( \text{lambda} - (-1) )^2 (\text{lambda} - 4) $),<ul><li>$ AM(-1) = 2 $</li><li>$ AM(4) = 1 $</li></ul></li><li>Example with a high-degree polynomial: Given a characteristic polynomial$ \text{lambda}^4 (\text{lambda}^2 - 2\text{lambda} + 1) $:<ul><li>This can be factored as$ \text{lambda}^4 (\text{lambda} - 1)^2 $(or$ ( \text{lambda} - 0 )^4 (\text{lambda} - 1)^2 $).</li><li>Eigenvalue$ 0 $has$ AM(0) = 4 $.</li><li>Eigenvalue$ 1 $has$ AM(1) = 2 $.</li></ul></li><li>Rotation Matrix Example:<ul><li>The characteristic polynomial for a rotation matrix (e.g.,$ \begin{pmatrix} 0 & -1 \ 1 & 0 \end{pmatrix} $) is$ \text{lambda}^2 + 1 $.</li><li>The characteristic equation$ \text{lambda}^2 + 1 = 0 $has no real solutions.</li><li>It has complex solutions:$ i $and$ -i $.</li><li>Therefore, this matrix has no real eigenvalues but has complex eigenvalues$ \text{i} $and$ -i $, each with$ AM(i) = 1 $and$ AM(-i) = 1 $.</li></ul></li><li>Fundamental Theorem of Algebra:<ul><li>If a polynomial has degree$ n $and complex roots are allowed, then there are exactly$ n $roots, counted with their multiplicities.</li><li>An$ (n \times n) $matrix will always have exactly$ n $complex eigenvalues when each is counted according to its algebraic multiplicity.</li></ul></li></ul><h4 id="eab2bc6d-dcbb-4cba-a36e-6a1bcc4c4307" data-toc-id="eab2bc6d-dcbb-4cba-a36e-6a1bcc4c4307" collapsed="false" seolevelmigrated="true">Geometric Multiplicity (GM)</h4><ul><li>Motivation: Even if two matrices have the same eigenvalues with the same algebraic multiplicities (i.e., the same characteristic polynomial), their eigenproperties might still differ. This difference is related to the dimension of their corresponding eigenspaces.</li><li>Definition: For an eigenvalue$ \text{lambda}\text{bar} $of a matrix$ A $, its geometric multiplicity (denoted$ GM(\text{lambda}\text{bar}) $) is the dimension of its eigenspace (which is the dimension of the null space of$ (A - \text{lambda}_\text{bar} I) $).</li><li>Example (Matrices A and B):<ul><li>Consider matrices$ A = \begin{pmatrix} -2 & 1 \ 0 & -2 \end{pmatrix} $and$ B = \begin{pmatrix} -2 & 0 \ 0 & -2 \end{pmatrix} $.</li><li>Both have characteristic polynomial$ ( -2 - \text{lambda} )^2 $(or$ ( \text{lambda} + 2 )^2 $).</li><li>Both have eigenvalue$ -2 $with$ AM(-2) = 2 $.</li><li>However, their geometric multiplicities differ:<ul><li>For matrix$ A $: The null space of$ (A - (-2)I) = A + 2I = \begin{pmatrix} 0 & 1 \ 0 & 0 \end{pmatrix} $has dimension$ 1 $(one free variable). So,$ GM_A(-2) = 1 $.</li><li>For matrix$ B $: The null space of$ (B - (-2)I) = B + 2I = \begin{pmatrix} 0 & 0 \ 0 & 0 \end{pmatrix} $has dimension$ 2 $(two free variables). So,$ GM_B(-2) = 2 $.</li></ul></li></ul></li><li>Theorem: For an$ (n \times n) $matrix$ A $and an eigenvalue$ \text{lambda} $:$ 1 \le GM(\text{lambda}) \le AM(\text{lambda}) \le n $<ul><li>This means the geometric multiplicity is always less than or equal to the algebraic multiplicity, and both are at most$ n $.</li></ul></li></ul><h4 id="47588c85-4b11-45ca-8849-eb46bc6fcfff" data-toc-id="47588c85-4b11-45ca-8849-eb46bc6fcfff" collapsed="false" seolevelmigrated="true">Diagonalization and Markov Chains</h4><ul><li>Goal: Construct a basis of$ R^n $(or$ R^2 $for the example) that consists entirely of eigenvectors of a given matrix.</li><li>Markov Chain Application: Using eigenvalues and eigenvectors can simplify the analysis of system evolution, such as Markov chains.<ul><li>Problem: Calculate$ Xk = T^k X0 $for a large$ k $(e.g.,$ k=100 $), where$ T $is a transition matrix and$ X_0 $is an initial distribution vector.</li><li>Steady State: For regular stochastic matrices, the system tends towards a unique steady state$ q $, where$ Tq = q $. This implies$ \text{lambda} = 1 $is always an eigenvalue, and$ q $is its corresponding eigenvector (rescaled to be a probability vector).</li><li>Simplified Calculation using Eigenvectors:<ol><li>Find all eigenvalues and their corresponding eigenvectors for the matrix$ T $.</li><li>If the eigenvectors form a basis for the space (e.g.,$ R^2 $), express the initial distribution vector$ X0 $as a linear combination of these eigenvectors:$ \text{X}0 = c1 \text{v}1 + c2 \text{v}2 $</li><li>Then,$ \text{X}k = T^k \text{X}0 = T^k ( c1 \text{v}1 + c2 \text{v}2 ) $.</li><li>Due to the eigenvector property, this simplifies to:$ \text{X}k = c1 T^k \text{v}1 + c2 T^k \text{v}2 = c1 \text{lambda}1^k \text{v}1 + c2 \text{lambda}2^k \text{v}_2 $</li><li>For Markov chains,$ \text{lambda}1 = 1 $(corresponding to the steady state eigenvector$ \text{v}1 $). Other eigenvalues (e.g.,$ \text{lambda}_2 $) will have magnitude less than$ 1 $(e.g.,$ 0.92 $).</li><li>The expression becomes:$ \text{X}k = c1 \text{v}1 + c2 (0.92)^k \text{v}_2 $.</li><li>As$ k \to \infty $,$ (0.92)^k \to 0 $. Thus,$ \text{X}k \to c1 \text{v}_1 $.</li><li>The term$ c1 \text{v}1 $represents the steady state$ q $. This provides a closed-form solution for$ X_k $and clarifies the long-term behavior: the largest eigenvalue (magnitudinally) dominates the calculation.</li></ol></li></ul></li></ul><h4 id="f92f06b9-f209-4853-a523-973043a5f550" data-toc-id="f92f06b9-f209-4853-a523-973043a5f550" collapsed="false" seolevelmigrated="true">The Diagonalization Theorem</h4><ul><li>Purpose: Provides a way to factor a matrix$ A $if it admits an eigenvector basis.</li><li>Assumptions:<ol><li>$ A $is an$ (n \times n) $matrix.</li><li>Let$ \text{lambda}1, \dots, \text{lambda}n $be the eigenvalues of$ A $, where each eigenvalue is repeated according to its algebraic multiplicity.</li><li>Let$ \text{v}1, \dots, \text{v}n $be corresponding eigenvectors that form a basis of$ R^n $</li></ol></li><li>Conclusion: If these assumptions hold, then$ A $can be expressed as:$ A = P D P^{-1} $where:<ul><li>$ P $is an invertible matrix whose columns are the eigenvectors$ \text{v}1, \dots, \text{v}n $</li><li>$ D $is a diagonal matrix with the eigenvalues$ \text{lambda}1, \dots, \text{lambda}n $on its main diagonal (in the same order as their corresponding eigenvectors in$ P $).</li></ul></li><li>Significance Later: While this theorem shows how to construct$ A $from its eigen-elements, a more powerful aspect (discussed later) is that if$ A $can be written in this form, one can immediately identify its eigenvectors and eigenvalues from$ P $and$ D$$.