5. Eigenvalues and Eigenvectors by MIT OpenCourseWare

Summary by www.lecturesummary.com: 5. Eigenvalues and Eigenvectors by MIT OpenCourseWare

• Course Logistics - Announcements

  • A correction to a typo in homework one was posted to Stellar and sent out.
  • This kind of correction is done every now and then even though several staff members read through problems.
  • The initial problem, with a tip, proved to be more difficult than intended, and the correction brings it back to the easier version.
  • The instructors attempt to reply in a timely fashion to typos to keep the students on track.
  • Office hours are popular, and students are free to ask questions during office hours or after class.
  • The course is fast-moving, and the instructors do not wish anyone to be left behind.

  Linear Algebra Topics - Upcoming Discussions

  • The lecture covers linear algebra topics for two more sessions before they move on.
  • The emphasis is placed on matrix transformations.
  • One such transformation, employed to solve systems of equations, was discussed earlier.
  • The subject of today is the Eigenvalue Decomposition.
  • Monday's subject will be the Singular Value Decomposition.

  Reordering in Systems of Equations - Significance and Techniques

  • Reordering is required while solving certain problems through Gaussian elimination.
  • Without reordering, there could be huge numerical error (if pivoting is not performed to reduce it) or failure due to too much fill-in.
  • A problem with 40 million equations in a research problem was cited as an example, where reordering resulted in making the problem solvable by Gaussian elimination, reducing computation time and memory.
  • Reordering is a type of preconditioning.
  • Preconditioning can be made for pivoting to reduce numerical error or to reduce fill-in to render the problem computable.

  Permutation Matrices - Definition and Action

  • There is a process known as permutation employed for rearrangement.
  • A permutation matrix is a specialized type of matrix.
  • Multiplying any other matrix by a permutation matrix can interchange rows or columns.
  • A sample permutation matrix that is designed to interchange row one and two of a matrix was presented, resembling an identity matrix with the first two diagonal entries interchanged (0 1 and 1 0 rather than 1 1).
  • Multiplied by this matrix, a vector has its first two elements interchanged.
  • Multiplying a matrix A from the left with such a permutation matrix (P*A) rearranges the rows of A.
  • The result (P*A) is a matrix with the rows of A rearranged, namely row one and two interchanged in the example.
  • To exchange columns (e.g., column one with two), one multiplies matrix A from the right by the transpose of the permutation matrix (A * P^T).

  Permutation Matrices - Properties

  • Permutation matrices are unitary matrices.
  • For a unitary matrix, its transpose is also its inverse (P * P^T is identity). Interchanging rows and then interchanging them back is equivalent to the original matrix.
  • Permutation matrices are defined as perhaps the simplest class of unitary matrices, whose task is row or column interchanges.
  • If there is an intended reordering of rows as per permutation matrix P1, then one would premultiply both sides of the system of equations by P1 to reorder the rows.
  • If one wishes to reorder the columns (unknowns), one employs an analogous permutation matrix P2, by multiplying on the right by P2 and on the left by P2^T (P2^T * A * P2).
  • There is a technical system for performing this kind of switching.

  Solving Systems of Equations - Summary of Methods

  • Systems of equations are always solved through Gaussian elimination if an exact answer is to be found.
  • There are variations of Gaussian elimination, like those applied to sparse matrices or banded matrices, where elimination is performed over the sparse structure instead of a full matrix.
  • Previous discussion covered sparse matrices and reordering (including permutation).

  Diffusion Example - Plinko Model

  • An example of diffusion through the use of the Plinko game (dropping a chip on a board with pegs) was utilized to demonstrate concepts.
  • In Plinko, a chip is dropped and strikes pegs, moving left or right with equal odds, simulating diffusion.
  • • Sparse matrix: Defines how the chance of locating the chip in a given cell changes from level to level.
    • Probability distribution: If a chip is in a cell, the chance at the next level divides 50/50 between the left and right neighbors, modeled by a sparse matrix A.
    • Distribution shape: The probability distribution widens as the chip drops through increasing levels, resembling a binomial or Gaussian distribution.
    • Matrix structure: The sparse matrix contains two diagonals with a half value, reflecting the 50/50 probability distribution to neighbors.
    • Boundary conditions: May be required for chips that arrive at the board edge.
    • Local physics: Most of the physics is local, such as this diffusion problem, where interactions are largely between neighbors.
    • Uniform distribution: After many levels (multiplications by A), the probability distribution will level out and become uniform.

    Eigenvalues and Eigenvectors - Introduction

    • Special distributions: Some distributions remain unchanged when multiplied by A (or A*A).
    • Eigenvectors: A uniform distribution is one of the eigenvectors of the matrix A*A.
    • Definition: An eigenvector is a vector that, when multiplied by a matrix, results in that vector being scaled but pointing in the same direction.
    • Unstretched vector: If the vector is unstretched (scale factor is one), it means A*vector = vector.
    • Stretched eigenvectors: Eigenvectors are special vectors that are stretched on multiplication by the matrix.
    • Degree of stretch: The degree of stretch is referred to as the eigenvalue.
    • Complex numbers: In a real n x n matrix, eigenvalues and eigenvectors can be complex numbers.
    • Solving pairs: Solving for eigenvector/eigenvalue pairs requires solving n equations.

    Eigenvalues and Eigenvectors - The Eigenvalue Problem

    • Eigenvalue equation: The eigenvalue equation is given as A * w = lambda * w.
    • Rewritten form: This can be rewritten as (A - lambda * I) * w = 0.
    • Solutions: Solutions are either the trivial solution w = 0, or the eigenvector w is in the null space of the matrix (A - lambda * I).
    • Non-trivial solution: For a non-trivial solution (w != 0), the matrix (A - lambda * I) needs to be singular.
    • Singular matrix: A matrix is singular if and only if its determinant is zero.
    • Determinant condition: If there is a non-trivial eigenvector w, then the determinant of (A - lambda * I) is zero: det(A - lambda * I) = 0.

    Eigenvalues - Characteristic Polynomial

    • Characteristic polynomial: The determinant of (A - lambda * I) is the characteristic polynomial.
    • Degree: It is an n-degree polynomial for an n x n matrix.
    • Eigenvalues: The n roots of the characteristic polynomial are the eigenvalues of the matrix A.
    • Possible lambdas: There are n lambdas for which (A - lambda * I) is singular.
    • Computing eigenvalues: One can compute this determinant and solve the resulting polynomial to find the eigenvalues.
    • Factored form: The characteristic polynomial is factored into the form (lambda - lambda1)(lambda - lambda2)...(lambda - lambdan) = 0.

    Finding Eigenvalues - Examples

    • Example 1 (Diagonal Matrix): For a diagonal matrix like diag(-2, 1, 3), the eigenvalues are -2, 1, and 3.
    • Example 2 (Triangular/Diagonal Matrices): The diagonal entries of a diagonal matrix are always its eigenvalues.
    • Example 3 (2x2 Matrix): For matrix J = [[-2, 1], [0, -2]], the eigenvalue is lambda = -2.
    • Example 4 (Chemical Reaction Rate Matrix): A 4x4 rate matrix has eigenvalues including lambda = 0 and lambda = -K1.

    • Properties of Eigenvalues

      • Real-valued matrix: The characteristic polynomial is real-valued.
      • Distinct eigenvalues: A matrix can have at most n distinct eigenvalues.
      • Multiplicity: Eigenvalues may not be distinct; they may have multiplicity.
      • Algebraic multiplicity: This is the multiplicity of an eigenvalue as a root of the characteristic polynomial.
      • Complex eigenvalues: They always occur in conjugate pairs.
      • Determinant: The determinant of a matrix is the product of its eigenvalues.
      • Trace: The trace of a matrix (sum of the diagonal elements) is the sum of its eigenvalues.

      Finding Eigenvectors - Using the Null Space

      • Eigenvalue equation: For an eigenvalue lambda, the associated eigenvector(s) w are determined from the equation (A - lambda * I) * w = 0.
      • Null space: This is the same as determining the null space of the matrix (A - lambda * I).
      • Gaussian elimination: It can be solved using Gaussian elimination.
      • Rank deficiency: The matrix (A - lambda * I) will be singular and rank deficient.
      • All-zero rows: One or more of the rows will be all zeros after applying Gaussian elimination. The number of all-zero rows indicates how many of the components of the eigenvector can be freely set.

      Geometric Multiplicity - Null Space Dimension

      • Free parameters: The number of parameters in the eigenvector that can be set freely is tied to the dimension of the null space of (A - lambda * I).
      • Geometric multiplicity: This dimension is referred to as the geometric multiplicity of the eigenvalue.
      • Linearly independent eigenvectors: Geometric multiplicity is the dimension of the linearly independent eigenvectors corresponding to an eigenvalue.

      Geometric Multiplicity - Connection with Algebraic Multiplicity

      • Comparison: The geometric multiplicity of an eigenvalue is always less than or equal to its algebraic multiplicity (1 <= geometric multiplicity <= algebraic multiplicity).
      • Distinct eigenvalue: If an eigenvalue is distinct, its algebraic multiplicity is one, and there will be only one corresponding eigenvector (geometric multiplicity is one).
      • Multiplicity range: If an eigenvalue has algebraic multiplicity m, the geometric multiplicity can be anywhere from one up to m.
      • Nice problems: Problems where the geometric and algebraic multiplicities are the same for all eigenvalues are considered "nice" because the matrix has a complete set of eigenvectors.

      Finding Eigenvectors - Examples

      • Example 1 (Diagonal Matrix, Eigenvalue -2): For matrix diag(-2, 1, 3) and eigenvalue lambda = -2, the eigenvector for lambda = -2 is proportional to^T. This eigenvalue has a geometric multiplicity of one.
      • Example 2 (Diagonal Matrix, Other Eigenvalues): For lambda = 1 and lambda = 3, the eigenvectors are proportional to^T. All these eigenvectors have geometric multiplicity of one.
      • Example 3 (Chemical Reaction Rate Matrix, Eigenvalue 0): The resulting eigenvector is the steady state solution, indicating the equilibria between B, C, and D.
      • Example 4 (Zero Matrix): The geometric multiplicity is two since two components can be chosen freely and there are two linearly independent eigenvectors.
      • Example 5 (Non-Diagonal Matrix): This is an example where geometric multiplicity (1) is less than algebraic multiplicity (2).
      • Example 6 (3x3 Matrix): The geometric multiplicity is two.

      • Understanding Diagonalization

        Diagonalization allows us to reformulate relationships in linear algebra. Here are some key points:

        • This permits reformulating the relationship as Lambda = W^-1 * A * W.
        • In such a situation, the matrix A is termed diagonalizable.
        • This is useful as diagonal equations are simple to solve.
        • Alternatively, A = W * Lambda * W^-1 can be expressed.

        Usefulness of Diagonalization - Solving Linear Systems (Ax=B)

        Understanding the eigenvalue decomposition makes it easy to solve Ax=B. Here’s how:

        • Understanding the eigenvalue decomposition (A = W * Lambda * W^-1) simplifies solving Ax=B.
        • Plugging in A = W * Lambda * W^-1 into Ax=B results in (W * Lambda * W^-1) * x = B.
        • Multiply both sides by W^-1 on the left: (Lambda * W^-1) * x = W^-1 * B.
        • Let y = W^-1 * x and c = W^-1 * B, reducing the equation to Lambda * y = c.
        • This is a simple diagonal system for solving y. The solution is y = Lambda^-1 * c.
        • Lambda is diagonal, hence its inverse (Lambda^-1) is a diagonal matrix with the reciprocals of the eigenvalues on the diagonal.
        • Replacing back for c and y: W^-1 * x = Lambda^-1 * W^-1 * B.
        • Left multiplication by W provides the solution for x: x = W * Lambda^-1 * W^-1 * B.
        • If the factorization is known, numerous linear systems with the same matrix A can be solved readily by simple matrix multiplications.

        Usefulness of Diagonalization - Solving Ordinary Differential Equations (ODEs)

        Eigenvalue decomposition can be used to solve linear ODEs of the type dx/dt = A * x. Here’s the process:

        • Replacing A = W * Lambda * W^-1 and introducing a new variable y such that x = W * y.
        • Differentiating x = W * y with respect to time results in dx/dt = W * dy/dt.
        • The ODE becomes W * dy/dt = (W * Lambda * W^-1) * (W * y).
        • Multiplying on the left by W^-1 yields dy/dt = Lambda * y.
        • This is a decoupled system of ODEs, where each part of y has its own differential equation: dy_i/dt = lambda_i * y_i.
        • Each of these decoupled ODEs possesses a straightforward exponential solution: y_i(t) = y_i(0) * exp(lambda_i * t).
        • This simplifies the system and can help in learning the linearized form of non-linear differential equations.

        W Inverse and Symmetric Matrices

        The inverse of the eigenvector matrix is connected to the eigenvectors of the transpose of A. Key points include:

        • The inverse of the eigenvector matrix (W^-1) relates to the eigenvectors of A^T.
        • For symmetric matrices, if the eigenvectors are normalized, then W^-1 = W^T.
        • The eigenvector matrix W is unitary in this case.
        • The eigenvectors of a symmetric matrix can be proved to be orthogonal.

      • Matrices Without a Complete Set of Eigenvectors

        There are numerous instances in which a matrix does not possess a full set of eigenvectors (geometric multiplicity is lower than algebraic multiplicity for one or more eigenvalues).

        Key Points

        • In such instances, the matrix cannot be diagonalized as described (A = W * Lambda * W^-1).
        • Certain parts of the system cannot be separated from one another.
        • Other types of transformation are required, e.g., the Jordan normal form (near diagonal form) or the Schur decomposition (conversion to an upper triangular form).
        • The Singular Value Decomposition (SVD) is a second type of transformation when a full set of eigenvectors cannot be found. This will be covered in the next lecture.

        Conclusion - Practice

        • Eigenvalues and eigenvectors will be encountered in future homework problems.
        • Encourage students to solve example problems manually to learn how to handle steps and concepts needed to find eigenvalues and eigenvectors.