Eigenvalues and Eigenvectors

For a square matrix A, a non-zero vector x is an eigenvector with eigenvalue λ if

Ax = λx

A only stretches x by the factor λ, without changing its direction. Eigenvalues appear in GATE every year, usually through their properties rather than long computations.

Finding eigenvalues and eigenvectors

Ax = λx means (A − λI)x = 0, which has a non-zero solution only when A − λI is singular:

det(A − λI) = 0, the characteristic equation.

Example: A = [[4, 1], [2, 3]].

• det(A − λI) = (4 − λ)(3 − λ) − 2 = λ² − 7λ + 10 = (λ − 5)(λ − 2), so λ = 5 and λ = 2.
• For λ = 5: (A − 5I)x = 0 gives −x₁ + x₂ = 0, so x = (1, 1).
• For λ = 2: 2x₁ + x₂ = 0, so x = (1, −2).

Any non-zero multiple of an eigenvector is also an eigenvector. A program can compute the characteristic polynomial exactly (here with the Faddeev–LeVerrier recurrence) and find its integer roots:

from fractions import Fraction

def characteristic_polynomial(A):
    """Coefficients of det(xI - A) = x^n + c1 x^(n-1) + ... + cn."""
    n = len(A)
    A = [[Fraction(v) for v in row] for row in A]
    mul = lambda X, Y: [[sum(X[i][k] * Y[k][j] for k in range(n)) for j in range(n)] for i in range(n)]
    M, coeffs = [[Fraction(0)] * n for _ in range(n)], [Fraction(1)]
    for k in range(1, n + 1):
        AM = mul(A, M)
        M = [[AM[i][j] + (coeffs[-1] if i == j else 0) for j in range(n)] for i in range(n)]
        coeffs.append(-sum(mul(A, M)[i][i] for i in range(n)) / k)
    return coeffs

def integer_roots(coeffs):
    n = len(coeffs) - 1
    return [r for r in range(-50, 51) if sum(c * r ** (n - i) for i, c in enumerate(coeffs)) == 0]

for A in ([[4, 1], [2, 3]], [[2, 0, 0], [1, 3, 0], [4, 5, 6]], [[2, 1, 1], [1, 2, 1], [1, 1, 2]]):
    c = characteristic_polynomial(A)
    print(A, "coefficients", [int(x) for x in c], "integer eigenvalues", integer_roots(c))

[[4, 1], [2, 3]] coefficients [1, -7, 10] integer eigenvalues [2, 5]
[[2, 0, 0], [1, 3, 0], [4, 5, 6]] coefficients [1, -11, 36, -36] integer eigenvalues [2, 3, 6]
[[2, 1, 1], [1, 2, 1], [1, 1, 2]] coefficients [1, -6, 9, -4] integer eigenvalues [1, 4]

For [[2, 1, 1], [1, 2, 1], [1, 1, 2]] the polynomial is λ³ − 6λ² + 9λ − 4 = (λ − 1)²(λ − 4): the eigenvalue 1 is repeated (algebraic multiplicity 2).

Properties

For an n × n matrix A with eigenvalues λ₁, …, λₙ (counted with multiplicity):

Check with the 3 × 3 example: trace = 2 + 2 + 2 = 6 = 1 + 1 + 4, and det = 4 = 1 × 1 × 4.

Eigenvectors belonging to distinct eigenvalues are linearly independent.

Cayley–Hamilton theorem

For A = [[4, 1], [2, 3]]: A² − 7A + 10I = 0. This gives A⁻¹ without row reduction: multiply by A⁻¹ to get A − 7I + 10A⁻¹ = 0, so A⁻¹ = (7I − A)/10. It also reduces high powers: A² = 7A − 10I, so A³ = 7A² − 10A = 39A − 70I.

Diagonalization

A is diagonalizable if A = PDP⁻¹, with D diagonal (the eigenvalues) and P's columns the eigenvectors. This happens exactly when A has n linearly independent eigenvectors, which is guaranteed if all eigenvalues are distinct, or if A is real symmetric. Then Aᵏ = PDᵏP⁻¹, which makes powers easy to compute.

Practice questions