Characteristic Polynomials, Eigendecomposition & the Spectral Theorem

When a linear transformation acts on a multi-dimensional space, it generally rotates, skews, and stretches vectors in complex, intertwined ways. Eigendecomposition uncovers the intrinsic geometric axes of the transformation—the privileged invariant directions where the operator acts as pure scalar stretching without rotation. In physical systems, data science, and network algorithms, eigenvalues and eigenvectors reveal resonant frequencies, dominant statistical modes, and stationary distributions.

1. The Fundamental Eigenvalue Problem & Invariant Directions#

Let A be a real square linear operator of dimension n×n, representing a linear mapping A : R^n → R^n. When A multiplies an arbitrary vector x in R^n, the output vector y = A · x typically points in a completely different spatial direction than x.

Definition of Eigenvectors and Eigenvalues#

However, for certain special non-zero vectors v in R^n, multiplying by matrix A produces a scalar multiple of the original vector. Such a vector does not rotate; it is merely stretched, compressed, or inverted along its own span:

A · v = λ · v

where:

• v is a non-zero vector (v ≠ 0) termed an eigenvector of A.
• λ is a scalar (which may be real or complex) termed the eigenvalue corresponding to eigenvector v.

Homogeneous System and the Characteristic Equation#

Rearranging the fundamental relation A · v = λ · v by introducing the n×n identity matrix I yields:

A · v - λ · I · v = 0

(A - λ · I) · v = 0

This is a homogeneous linear system of equations. By the fundamental theorems of linear systems:

• If the matrix operator (A - λ · I) is invertible, the system has only the trivial solution v = 0.
• Because an eigenvector is, by definition, strictly non-zero (v ≠ 0), the matrix (A - λ · I) must be non-invertible (singular).

A square matrix is singular if and only if its determinant vanishes. This establishes the characteristic equation:

p(λ) = det(A - λ · I) = 0

The Characteristic Polynomial#

For an n×n matrix A, the determinant det(A - λ · I) expands into an n-th degree polynomial in λ, termed the characteristic polynomial p(λ):

p(λ) = (-1)^n · λ^n + (-1)^(n-1) · tr(A) · λ^(n-1) + ... + det(A)

By the Fundamental Theorem of Algebra, any n-th degree polynomial with real or complex coefficients has exactly n roots over the complex numbers C, counting algebraic multiplicities:

p(λ) = (-1)^n · (λ - λ_1) · (λ - λ_2) · ... · (λ - λ_n)

Two Invariant Scalar Measures: Trace and Determinant#

The coefficients of the characteristic polynomial encode two fundamental invariants that remain invariant under any similarity transformation or change of basis:

1. The Trace Invariant:

The trace of matrix A, tr(A), is the sum of its main diagonal entries. It equals the sum of all n eigenvalues:

tr(A) = sum(i=1 to n, A_ii) = λ_1 + λ_2 + ... + λ_n.

1. The Determinant Invariant:

The determinant of matrix A equals the product of all n eigenvalues:

det(A) = λ_1 · λ_2 · ... · λ_n.

Immediate Deduction: A matrix is invertible if and only if det(A) ≠ 0, which holds if and only if none of its eigenvalues are equal to zero (0 is not an eigenvalue).

2. Multiplicities, Defective Matrices & Jordan Canonical Form#

When analyzing the spectral structure of an operator, we must distinguish between two critical notions of multiplicity associated with each eigenvalue.

Algebraic Multiplicity vs. Geometric Multiplicity#

For a specific eigenvalue λ_i:

1. Algebraic Multiplicity, μ_A(λ_i):

The number of times the root λ_i is repeated in the factorization of the characteristic polynomial p(λ).

p(λ) = (λ - λ_i)^(μ_A(λ_i)) · q(λ), where q(λ_i) ≠ 0.

1. Geometric Multiplicity, μ_G(λ_i):

The maximum number of linearly independent eigenvectors associated with λ_i.

Equivalently, it is the dimension of the eigenspace E_(λ_i) = Null(A - λ_i · I):

μ_G(λ_i) = dim(Null(A - λ_i · I)) = n - rank(A - λ_i · I).

The Multiplicity Inequality#

Theorem: For every eigenvalue λ_i of any square matrix A:

1 <= μ_G(λ_i) <= μ_A(λ_i)

The geometric multiplicity is always at least 1 (there is always at least one non-zero eigenvector), but it can never exceed the algebraic multiplicity.

Defective Matrices: The Collapse of Diagonalizability#

A matrix is termed defective if there exists at least one eigenvalue λ_i whose geometric multiplicity is strictly less than its algebraic multiplicity:

μ_G(λ_i) < μ_A(λ_i)

When a matrix is defective, it fails to produce n linearly independent eigenvectors, making it impossible to form an eigenvector basis for R^n.

Canonical Example of a Defective Matrix:

Consider the standard 2D shear matrix:

S = [

[ 1, 1 ],

[ 0, 1 ]

]

Calculate the characteristic polynomial:

det(S - λ · I) = det([ [ 1 - λ, 1 ], [ 0, 1 - λ ] ]) = (1 - λ)^2 = 0.

• Eigenvalue: λ = 1.
• Algebraic Multiplicity: μ_A(1) = 2.

Now find the eigenspace by solving (S - 1 · I) · v = 0:

[ [ 0, 1 ], [ 0, 0 ] ] · [ v1, v2 ]^T = [ 0, 0 ]^T

This implies v2 = 0, while v1 is a free variable.

Every eigenvector has the form v = [ c, 0 ]^T = c · [ 1, 0 ]^T.

• The eigenspace is only 1-dimensional: μ_G(1) = dim(Null(S - I)) = 1.

Because μ_G(1) = 1 < μ_A(1) = 2, matrix S is defective. It cannot be diagonalized.

                  Square Matrix A in R^(n x n)
                              |
               +--------------+--------------+
               |                             |
     mu_G(lambda_i) == mu_A(lambda_i)      mu_G(lambda_i) < mu_A(lambda_i)
            for all i                     for at least one i
               |                             |
      Non-Defective Matrix            Defective Matrix
     (Fully Diagonalizable)         (Lacks Eigenbasis;
      A = V * Lambda * V^(-1)        Requires Jordan Form)

The Jordan Canonical Form#

When a matrix is defective, it cannot be reduced to a pure diagonal matrix. However, it can always be reduced via similarity transformation to the Jordan Canonical Form:

A = M · J · M^(-1)

where J is a block-diagonal matrix composed of Jordan blocks J_k(λ_i):

J_k(λ_i) = [

[ λ_i, 1, 0, ..., 0 ],

[ 0, λ_i, 1, ..., 0 ],

[ ..., ..., ..., ..., ... ],

[ 0, 0, 0, ..., λ_i ]

]

with the eigenvalue on the diagonal and 1s on the superdiagonal.

3. Matrix Diagonalization & Similarity Transformations#

Diagonalization is one of the most powerful computational techniques in linear algebra, decoupling coupled systems of linear equations into independent scalar equations.

The Diagonalization Theorem#

Theorem: An n×n matrix A is diagonalizable if and only if it possesses n linearly independent eigenvectors { v1, v2, ..., vn }.

Sufficient Condition: If A has n distinct eigenvalues (λ_1 ≠ λ_2 ≠ ... ≠ λ_n), then A is guaranteed to have n linearly independent eigenvectors and is automatically diagonalizable.

Constructing the Diagonalization Factorization#

Let { v1, v2, ..., vn } be n linearly independent eigenvectors with corresponding eigenvalues { λ1, λ2, ..., λn }.

1. Assemble the Modal Matrix V by placing the eigenvectors as columns:

V = [ v1 | v2 | ... | vn ]

Because the eigenvectors are linearly independent, det(V) ≠ 0, meaning V is invertible.

1. Assemble the Diagonal Eigenvalue Matrix Λ:

Λ = diag(λ1, λ2, ..., λn) = [

[ λ1, 0, ..., 0 ],

[ 0, λ2, ..., 0 ],

[ ..., ..., ..., ... ],

[ 0, 0, ..., λn ]

]

Examine the product A · V:

A · V = A · [ v1 | v2 | ... | vn ] = [ A · v1 | A · v2 | ... | A · vn ]

Using A · vi = λi · vi:

A · V = [ λ1 · v1 | λ2 · v2 | ... | λn · vn ] = [ v1 | v2 | ... | vn ] · Λ = V · Λ

Multiplying both sides on the right by V^(-1) yields the similarity diagonalization:

A = V · Λ · V^(-1)

Conversely, multiplying on the left by V^(-1) extracts the diagonal matrix:

Λ = V^(-1) · A · V

Computational Power: Fast High Matrix Powers#

Computing high powers of a dense matrix A^k directly via repeated multiplication costs O(k · n^3) arithmetic operations.

With eigendecomposition:

A^2 = (V · Λ · V^(-1)) · (V · Λ · V^(-1)) = V · Λ · (V^(-1) · V) · Λ · V^(-1) = V · Λ^2 · V^(-1)

By induction, for any positive integer k:

A^k = V · Λ^k · V^(-1)

Because Λ is diagonal, raising Λ to the k-th power requires only raising its diagonal entries to the k-th power:

Λ^k = diag(λ1^k, λ2^k, ..., λn^k)

This reduces the computational complexity from O(k · n^3) to an initial O(n^3) decomposition followed by O(n) operations for any power k, enabling the simulation of discrete dynamical systems (e.g., Markov chains, population models) over thousands of time steps in milliseconds.

The Matrix Exponential and Systems of Linear Differential Equations#

In continuous dynamical systems, physical laws are modeled by coupled first-order differential equations:

dx/dt = A · x(t), with initial condition x(0) = x_0

The analytical solution is given by the matrix exponential:

x(t) = exp(A · t) · x_0

Using diagonalization A = V · Λ · V^(-1):

exp(A · t) = sum(k=0 to infinity, (A · t)^k / k!) = V · diag(e^(λ1 · t), e^(λ2 · t), ..., e^(λn · t)) · V^(-1)

The system of coupled differential equations decouples completely into n independent exponential modes e^(λi · t)!

4. The Spectral Theorem for Real Symmetric Matrices#

Real symmetric matrices (A = A^T) occupy a central place in applied mathematics, quantum mechanics, physics, and machine learning. The covariance matrices in PCA, Hessian matrices in optimization, and graph Laplacians in network science are all real symmetric matrices.

The Spectral Theorem provides three foundational guarantees:

The Three Guarantees of the Spectral Theorem#

For any real symmetric matrix A in R^(n×n) (where A = A^T):

1. Purely Real Spectrum:

All n eigenvalues of A are strictly real numbers (λ_i in R). There are no complex imaginary parts.

Proof Sketch:

Let v be a complex eigenvector with eigenvalue λ: A · v = λ · v.

Take the conjugate transpose (Hermitian inner product) with v:

v^H · A · v = v^H · (λ · v) = λ · (v^H · v) = λ · ||v||^2.

Taking the conjugate transpose of the scalar:

(v^H · A · v)^H = v^H · A^T · v = v^H · A · v = λ_conjugate · ||v||^2.

Therefore, λ · ||v||^2 = λ_conjugate · ||v||^2.

Since v ≠ 0, ||v||^2 > 0, which implies λ = λ_conjugate.

Hence, λ must be a purely real number!

1. Mutual Orthogonality of Distinct Eigenspaces:

Eigenvectors corresponding to distinct eigenvalues are strictly orthogonal under the standard inner product.

Proof:

Let A · v1 = λ1 · v1 and A · v2 = λ2 · v2 with λ1 ≠ λ2.

Evaluate the inner product <A · v1, v2>:

<A · v1, v2> = (A · v1)^T · v2 = v1^T · A^T · v2 = v1^T · A · v2 = <v1, A · v2>.

Substitute the eigenvalues:

<λ1 · v1, v2> = <v1, λ2 · v2>

λ1 · <v1, v2> = λ2 · <v1, v2>

(λ1 - λ2) · <v1, v2> = 0.

Since λ1 ≠ λ2, the term (λ1 - λ2) ≠ 0.

Therefore, <v1, v2> = 0.

The eigenvectors v1 and v2 are orthogonal!

1. Orthogonal Diagonalizability:

There exists an orthonormal basis { q1, q2, ..., qn } for R^n consisting entirely of eigenvectors of A.

In matrix form, there exists an orthogonal matrix Q (where Q^T = Q^(-1)) such that:

A = Q · Λ · Q^T

The Dyadic Spectral Decomposition#

Substituting Q = [ q1 | q2 | ... | qn ] into A = Q · Λ · Q^T produces the dyadic (outer product) spectral expansion:

A = sum(i=1 to n, λ_i · (q_i · q_i^T))

Each term P_i = q_i · q_i^T is a rank-one symmetric orthogonal projection matrix onto the 1-dimensional subspace spanned by q_i.

The Spectral Theorem establishes that:

Any real symmetric operator decomposes into a weighted sum of mutually perpendicular orthogonal projections, where the weights are the eigenvalues!

+-----------------------------------------------------------------------------+
|                  GEOMETRIC ACTION OF SPECTRAL DECOMPOSITION                 |
+-----------------------------------------------------------------------------+
| Input x  -->  [ Rotate into Eigenbasis via Q^T ]                            |
|          -->  [ Stretch coordinate axes independently by eigenvalues Lambda]|
|          -->  [ Rotate back to standard coordinates via Q ]                 |
|                                                                             |
| Formula: A · x = sum(i=1 to n, lambda_i * (q_i^T * x) * q_i)                |
+-----------------------------------------------------------------------------+

Quadratic Forms & Positive Definiteness#

For a real symmetric matrix A, the scalar function q(x) = x^T · A · x is called a quadratic form.

Substituting the spectral decomposition:

q(x) = x^T · (Q · Λ · Q^T) · x = (Q^T · x)^T · Λ · (Q^T · x)

Let y = Q^T · x = [ y1, y2, ..., yn ]^T:

q(x) = sum(i=1 to n, λ_i · y_i^2)

Taxonomy of Symmetric Matrices:

• Positive-Definite (A > 0): All λ_i > 0. Then q(x) > 0 for all x ≠ 0. In optimization, this signifies a strictly convex function with a unique global minimum.
• Positive-Semidefinite (A >= 0): All λ_i >= 0. Then q(x) >= 0 for all x.
• Negative-Definite (A < 0): All λ_i < 0. Strictly concave function with a unique maximum.
• Indefinite: A has both positive and negative eigenvalues. The surface represents a saddle point (minimax).

5. Numerical Spectral Algorithms: Power Iteration & QR Algorithm#

In software engineering, computing eigenvalues by symbolically solving det(A - λ · I) = 0 is numerically disastrous. Finding polynomial roots is notoriously ill-conditioned (Wilkinson's polynomial phenomenon), and the Abel-Ruffini theorem proves that no general algebraic solution exists for polynomials of degree n >= 5. Modern numerical libraries (BLAS/LAPACK, Eigen, SciPy) deploy iterative matrix algorithms.

Power Iteration (Dominant Eigenpair Extraction)#

Power iteration computes the dominant eigenvalue λ_1 (the eigenvalue with the largest absolute magnitude: |λ_1| > |λ_2| >= ... >= |λ_n|) and its associated eigenvector.

Algorithm:

1. Initialize a random vector b_0 with ||b_0|| = 1.
2. For iteration k = 0, 1, 2, ...:

y_{k+1} = A · b_k

b_{k+1} = y_{k+1} / ||y_{k+1}||

1. Estimate the dominant eigenvalue using the Rayleigh Quotient:

r(b_{k+1}) = (b_{k+1}^T · A · b_{k+1}) / (b_{k+1}^T · b_{k+1})

Convergence Mechanics:

Express b_0 as a linear combination of the eigenvectors: b_0 = c1 · v1 + c2 · v2 + ... + cn · vn.

Multiplying by A^k:

A^k · b_0 = c1 · λ_1^k · v1 + c2 · λ_2^k · v2 + ... + cn · λ_n^k · vn

A^k · b_0 = λ_1^k · [ c1 · v1 + c2 · (λ_2 / λ_1)^k · v2 + ... + cn · (λ_n / λ_1)^k · vn ]

Since |λ_1| > |λ_2|, the ratio (λ_2 / λ_1)^k converges geometrically to zero as k increases!

The rate of convergence is governed strictly by the spectral gap ratio |λ_2 / λ_1|.

The QR Algorithm (Full Spectrum Computation)#

To find all eigenvalues of an n×n matrix simultaneously, the Francis QR Algorithm is used:

Algorithm:

1. Initialize A_0 = A. (Usually pre-processed to tridiagonal or Hessenberg form in O(n^3)).
2. For iteration k = 0, 1, 2, ...:

- Compute the QR factorization: A_k = Q_k · R_k

- Reverse the product order: A_{k+1} = R_k · Q_k

Notice that:

A_{k+1} = R_k · Q_k = (Q_k^T · A_k) · Q_k = Q_k^T · A_k · Q_k

Each step is a similarity transformation, preserving the exact eigenvalues of A.

As k → infinity, the off-diagonal entries vanish, and A_k converges to an upper triangular Schur matrix with the eigenvalues displayed along the main diagonal!

6. Distributed Systems, Networks & Machine Learning Applications#

Spectral analysis drives algorithms across web search, graph theory, and physical simulation.

1. Web Search Indexing: Google PageRank#

In the original 1998 formulation by Larry Page and Sergey Brin, the importance of web pages is computed as the stationary probability distribution of a random surfer traversing the internet graph.

• Web Graph Matrix: Let M in R^(N×N) be the hyperlink transition probability matrix, where M_ij is the probability of navigating from page j to page i.
• The Dangling Node and Trap Problem: Web pages with no outbound links or isolated link loops trap surfers, causing the Markov chain to become reducible.
• The Google Matrix G: To ensure aperiodicity and irreducibility, a damping factor d = 0.85 is introduced:

G = d · M + ((1 - d) / N) · J

where J is the N×N all-ones matrix.

• The Perron-Frobenius Theorem: Because G is a strictly positive stochastic matrix (all entries > 0 and column sums = 1), the Perron-Frobenius theorem guarantees that:

1. The largest eigenvalue is exactly λ_1 = 1.

2. The eigenvalue λ_1 = 1 has algebraic and geometric multiplicity 1.

3. The associated eigenvector r (the PageRank vector) has strictly positive components: G · r = 1 · r.

Google computed the PageRank scores of billions of pages by running distributed power iteration over clusters of computers!

2. Spectral Graph Theory & Community Clustering#

In network analysis, social network community detection, and image segmentation, partitioning an undirected graph G = (V, E) into well-connected clusters is formulated via the Graph Laplacian matrix L:

L = D - W

where:

• D is the diagonal degree matrix: D_ii = degree of vertex i.
• W is the adjacency weight matrix.

Properties of the Graph Laplacian:

• L is symmetric and positive-semidefinite (all λ_i >= 0).
• The smallest eigenvalue is always λ_1 = 0, corresponding to the all-ones eigenvector 1 = [ 1, 1, ..., 1 ]^T, since rows sum to zero.
• The multiplicity of eigenvalue 0 equals the number of connected components in the graph.
• The Fiedler Vector: The eigenvector corresponding to the second smallest eigenvalue λ_2 (the algebraic connectivity) is known as the Fiedler vector. Sorting vertices by their value in the Fiedler vector provides an optimal partition of the graph that minimizes the Normalized Cut (Ncut) between communities.

3. Structural Resonance in Mechanical & Civil Engineering#

When designing bridges, skyscrapers, and aircraft wings, engineers model physical structures as systems of coupled mass-spring-damper elements:

M · (d^2 x / dt^2) + K · x = 0

where M is the positive-definite mass matrix and K is the stiffness matrix.

Assuming harmonic oscillation x(t) = v · cos(ω · t):

(K - ω^2 · M) · v = 0

This is a generalized eigenvalue problem:

(M^(-1) · K) · v = λ · v, with λ = ω^2

The eigenvalues λ_i give the natural resonant frequencies ω_i = sqrt(λ_i), and the eigenvectors v_i define the physical vibration mode shapes. Designing structures to ensure their natural frequencies do not align with external wind or seismic excitation prevents catastrophic failure (such as the Tacoma Narrows Bridge collapse).

7. Common Architectural Pitfalls & Misconceptions#

• Pitfall 1: Conflating Invertibility with Diagonalizability.

Invertibility is governed entirely by whether 0 is an eigenvalue (det(A) ≠ 0). Diagonalizability is governed entirely by whether there exists a complete set of n linearly independent eigenvectors.

- A matrix can be invertible but non-diagonalizable: [ [ 2, 1 ], [ 0, 2 ] ] has det = 4 ≠ 0 (invertible), but is defective (cannot be diagonalized).

- A matrix can be singular but diagonalizable: [ [ 3, 0 ], [ 0, 0 ] ] has det = 0 (non-invertible), but has 2 independent eigenvectors [ 1, 0 ]^T and [ 0, 1 ]^T (fully diagonalizable).

• Pitfall 2: Assuming Real Matrices Always Have Real Eigenvalues.

A real matrix can have complex conjugate eigenvalues. A 90-degree 2D rotation matrix R = [ [ 0, -1 ], [ 1, 0 ] ] has characteristic equation λ^2 + 1 = 0, yielding purely imaginary eigenvalues λ = ± i. This geometrically reflects that no real direction in R^2 remains invariant under a 90-degree rotation.

• Pitfall 3: Forgetting to Orthonormalize Repeated Eigenspaces in Symmetric Matrices.

While eigenvectors of a symmetric matrix corresponding to distinct eigenvalues are automatically orthogonal, eigenvectors corresponding to a repeated eigenvalue (multiplicity > 1) are not automatically orthogonal; they must be explicitly orthogonalized using Gram-Schmidt before assembling the orthogonal matrix Q.

• Pitfall 4: Symbolic Determinant Expansion in Production Software.

Never write software that computes the characteristic polynomial by symbolic determinant expansion for matrices larger than 4×4. Always use iterative numerical algorithms like the QR algorithm or Arnoldi iteration.

8. Summary & Checkpoint Exercises#

Solidify your understanding of eigenvalues, eigenvectors, diagonalizability, and the Spectral Theorem with the following four checkpoint problems. Full step-by-step solutions are provided.

Problem 1 (Eigenvalues, Eigenvectors, and Multiplicities for a 2×2 Matrix):

Given the matrix A:

A = [

[ 5, 4 ],

[ 1, 2 ]

]

1. Find the characteristic polynomial p(λ).
2. Determine all eigenvalues of A, and verify that tr(A) = λ1 + λ2 and det(A) = λ1 · λ2.
3. Find an eigenvector for each eigenvalue.
4. State the algebraic and geometric multiplicities of each eigenvalue. Is A diagonalizable?

Solution:

Part 1: Characteristic Polynomial.

p(λ) = det(A - λ · I) = det([

[ 5 - λ, 4 ],

[ 1, 2 - λ ]

])

p(λ) = (5 - λ)(2 - λ) - (4)(1)

p(λ) = 10 - 5λ - 2λ + λ^2 - 4

p(λ) = λ^2 - 7λ + 6.

Part 2: Eigenvalues and Invariants.

Solve λ^2 - 7λ + 6 = 0:

(λ - 6)(λ - 1) = 0

The eigenvalues are:

λ1 = 6, λ2 = 1.

Verify Trace and Determinant:

• Matrix Trace: tr(A) = 5 + 2 = 7.

Sum of eigenvalues: λ1 + λ2 = 6 + 1 = 7. Matches.

• Matrix Determinant: det(A) = (5)(2) - (4)(1) = 10 - 4 = 6.

Product of eigenvalues: λ1 · λ2 = (6)(1) = 6. Matches.

Part 3: Eigenvectors.

• For λ1 = 6:

Solve (A - 6 · I) · v = 0:

[

[ 5 - 6, 4 ],

[ 1, 2 - 6 ]

] · [ v1, v2 ]^T = [

[ -1, 4 ],

[ 1, -4 ]

] · [ v1, v2 ]^T = [ 0, 0 ]^T

From row 1: -v1 + 4 · v2 = 0 => v1 = 4 · v2.

Choosing v2 = 1 yields the eigenvector:

v1 = [ 4, 1 ]^T.

• For λ2 = 1:

Solve (A - 1 · I) · v = 0:

[

[ 5 - 1, 4 ],

[ 1, 2 - 1 ]

] · [ v1, v2 ]^T = [

[ 4, 4 ],

[ 1, 1 ]

] · [ v1, v2 ]^T = [ 0, 0 ]^T

From row 2: v1 + v2 = 0 => v1 = -v2.

Choosing v2 = 1 yields the eigenvector:

v2 = [ -1, 1 ]^T.

Part 4: Multiplicities and Diagonalizability.

• For λ1 = 6: Algebraic multiplicity μ_A(6) = 1, Geometric multiplicity μ_G(6) = 1.
• For λ2 = 1: Algebraic multiplicity μ_A(1) = 1, Geometric multiplicity μ_G(1) = 1.

Because A is a 2×2 matrix with 2 distinct real eigenvalues, the eigenvectors { [ 4, 1 ]^T, [ -1, 1 ]^T } are linearly independent. Matrix A is fully diagonalizable.

Problem 2 (Matrix Diagonalization and Computing A^8 Fast Power):

Using the eigendecomposition of matrix A from Problem 1:

A = [ [ 5, 4 ], [ 1, 2 ] ]

1. Construct the modal matrix V and diagonal matrix Λ such that A = V · Λ · V^(-1).
2. Compute V^(-1).
3. Derive an explicit closed-form expression for A^k for any integer k, and compute A^4.

Solution:

Part 1: Construct V and Λ.

Using eigenvectors v1 = [ 4, 1 ]^T (λ1 = 6) and v2 = [ -1, 1 ]^T (λ2 = 1):

V = [

[ 4, -1 ],

[ 1, 1 ]

]

Λ = [

[ 6, 0 ],

[ 0, 1 ]

]

Part 2: Compute V^(-1).

det(V) = (4)(1) - (-1)(1) = 4 - (-1) = 5.

V^(-1) = (1 / det(V)) · [

[ 1, 1 ],

[ -1, 4 ]

] = (1/5) · [

[ 1, 1 ],

[ -1, 4 ]

] = [

[ 0.2, 0.2 ],

[ -0.2, 0.8 ]

]

Part 3: Compute A^k and A^4.

A^k = V · Λ^k · V^(-1)

Λ^k = [

[ 6^k, 0 ],

[ 0, 1^k ]

] = [

[ 6^k, 0 ],

[ 0, 1 ]

]

Multiply V · Λ^k:

V · Λ^k = [

[ 4, -1 ],

[ 1, 1 ]

] · [

[ 6^k, 0 ],

[ 0, 1 ]

] = [

[ 4 · 6^k, -1 ],

[ 1 · 6^k, 1 ]

]

Now multiply by V^(-1) = (1/5) · [ [ 1, 1 ], [ -1, 4 ] ]:

A^k = (1/5) · [

[ 4 · 6^k, -1 ],

[ 1 · 6^k, 1 ]

] · [

[ 1, 1 ],

[ -1, 4 ]

]

• Entry (1, 1): (1/5) · [ (4 · 6^k)(1) + (-1)(-1) ] = (1/5) · [ 4 · 6^k + 1 ]
• Entry (1, 2): (1/5) · [ (4 · 6^k)(1) + (-1)(4) ] = (1/5) · [ 4 · 6^k - 4 ]
• Entry (2, 1): (1/5) · [ (1 · 6^k)(1) + (1)(-1) ] = (1/5) · [ 6^k - 1 ]
• Entry (2, 2): (1/5) · [ (1 · 6^k)(1) + (1)(4) ] = (1/5) · [ 6^k + 4 ]

For k = 4: 6^4 = 1296.

• Entry (1, 1): (4 · 1296 + 1) / 5 = (5184 + 1) / 5 = 5185 / 5 = 1037
• Entry (1, 2): (4 · 1296 - 4) / 5 = (5184 - 4) / 5 = 5180 / 5 = 1036
• Entry (2, 1): (1296 - 1) / 5 = 1295 / 5 = 259
• Entry (2, 2): (1296 + 4) / 5 = 1300 / 5 = 260

Result:

A^4 = [

[ 1037, 1036 ],

[ 259, 260 ]

]

Computing this power took zero matrix-matrix multiplications after the initial spectral factorization.

Problem 3 (Spectral Decomposition of a Real Symmetric Matrix into Dyadic Projections):

Given the real symmetric matrix:

S = [

[ 3, 2 ],

[ 2, 3 ]

]

1. Find the eigenvalues and orthonormal eigenvectors of S.
2. Formulate the orthogonal matrix Q and diagonal matrix Λ such that S = Q · Λ · Q^T.
3. Compute the rank-one projection matrices P1 = q1 · q1^T and P2 = q2 · q2^T, and explicitly verify that S = λ1 · P1 + λ2 · P2.

Solution:

Part 1: Eigenvalues and Orthonormal Eigenvectors.

Characteristic equation:

det(S - λ · I) = det([ [ 3 - λ, 2 ], [ 2, 3 - λ ] ]) = (3 - λ)^2 - 4 = 0

(3 - λ)^2 = 4 => 3 - λ = ± 2

λ1 = 5, λ2 = 1.

Find eigenvectors:

• For λ1 = 5:

(S - 5 · I) · v = [ [ -2, 2 ], [ 2, -2 ] ] · v = 0 => -2 v1 + 2 v2 = 0 => v1 = v2.

Unnormalized: [ 1, 1 ]^T.

Norm = sqrt(1^2 + 1^2) = sqrt(2).

Orthonormal unit vector: q1 = [ 1/sqrt(2), 1/sqrt(2) ]^T.

• For λ2 = 1:

(S - 1 · I) · v = [ [ 2, 2 ], [ 2, 2 ] ] · v = 0 => 2 v1 + 2 v2 = 0 => v1 = -v2.

Unnormalized: [ -1, 1 ]^T.

Norm = sqrt((-1)^2 + 1^2) = sqrt(2).

Orthonormal unit vector: q2 = [ -1/sqrt(2), 1/sqrt(2) ]^T.

Notice that <q1, q2> = (1/sqrt(2))(-1/sqrt(2)) + (1/sqrt(2))(1/sqrt(2)) = -1/2 + 1/2 = 0.

The vectors are strictly orthonormal!

Part 2: Matrices Q and Λ.

Q = [

[ 1/sqrt(2), -1/sqrt(2) ],

[ 1/sqrt(2), 1/sqrt(2) ]

]

Λ = [

[ 5, 0 ],

[ 0, 1 ]

]

Part 3: Dyadic Projection Matrices.

Compute P1 = q1 · q1^T:

P1 = [

1/sqrt(2),

1/sqrt(2)

] · [ 1/sqrt(2), 1/sqrt(2) ]

P1 = [

[ 1/2, 1/2 ],

[ 1/2, 1/2 ]

]

Compute P2 = q2 · q2^T:

P2 = [

-1/sqrt(2),

1/sqrt(2)

] · [ -1/sqrt(2), 1/sqrt(2) ]

P2 = [

[ 1/2, -1/2 ],

[ -1/2, 1/2 ]

]

Verify Properties of Projections:

• P1 + P2 = [ [ 1/2 + 1/2, 1/2 - 1/2 ], [ 1/2 - 1/2, 1/2 + 1/2 ] ] = [ [ 1, 0 ], [ 0, 1 ] ] = I (Resolution of Identity).
• P1 · P2 = 0 (Orthogonal projection subspaces).

Verify Dyadic Spectral Sum:

λ1 · P1 + λ2 · P2 = 5 · [

[ 1/2, 1/2 ],

[ 1/2, 1/2 ]

] + 1 · [

[ 1/2, -1/2 ],

[ -1/2, 1/2 ]

]

= [

[ 5/2 + 1/2, 5/2 - 1/2 ],

[ 5/2 - 1/2, 5/2 + 1/2 ]

]

= [

[ 6/2, 4/2 ],

[ 4/2, 6/2 ]

]

= [

[ 3, 2 ],

[ 2, 3 ]

] = S.

The dyadic expansion exactly reconstitutes matrix S.

Problem 4 (Stationary Distribution of a 2-State Markov Chain via Eigendecomposition):

A server cluster transitions between two states every hour: State 1 (Healthy) and State 2 (Degraded).

The transition probability matrix P is:

P = [

[ 0.8, 0.4 ],

[ 0.2, 0.6 ]

]

where P_ij represents the probability of transitioning from state j to state i (column-stochastic matrix where columns sum to 1).

1. Show that λ1 = 1 is an eigenvalue of P, and find the second eigenvalue λ2 without computing determinants.
2. Find the stationary distribution vector π satisfying P · π = π, normalized such that π_1 + π_2 = 1.
3. Compute the long-term state distribution as time t → infinity starting from an initial degraded state x_0 = [ 0, 1 ]^T.

Solution:

Part 1: Eigenvalues of the Stochastic Matrix.

Because every column of P sums to 1:

P^T · [ 1, 1 ]^T = [ [ 0.8, 0.2 ], [ 0.4, 0.6 ] ] · [ 1, 1 ]^T = [ 0.8 + 0.2, 0.4 + 0.6 ]^T = [ 1, 1 ]^T.

Thus, [ 1, 1 ]^T is an eigenvector of P^T with eigenvalue 1. Since a matrix and its transpose share identical eigenvalues, λ1 = 1 is guaranteed to be an eigenvalue of P.

Find λ2 via the Trace Invariant:

tr(P) = 0.8 + 0.6 = 1.4.

Since tr(P) = λ1 + λ2:

1.4 = 1 + λ2 => λ2 = 0.4.

Part 2: Stationary Distribution Vector π.

Solve (P - 1 · I) · π = 0:

[

[ 0.8 - 1, 0.4 ],

[ 0.2, 0.6 - 1 ]

] · [ π1, π2 ]^T = [

[ -0.2, 0.4 ],

[ 0.2, -0.4 ]

] · [ π1, π2 ]^T = [ 0, 0 ]^T

From row 1: -0.2 · π1 + 0.4 · π2 = 0 => 0.2 · π1 = 0.4 · π2 => π1 = 2 · π2.

Normalize such that π1 + π2 = 1:

2 · π2 + π2 = 1 => 3 · π2 = 1 => π2 = 1/3 ≈ 0.3333.

π1 = 2 · (1/3) = 2/3 ≈ 0.6667.

Stationary vector:

π = [ 2/3, 1/3 ]^T ≈ [ 0.6667, 0.3333 ]^T.

Part 3: Long-Term Distribution from x_0 = [ 0, 1 ]^T.

Find the eigenvector for λ2 = 0.4:

(P - 0.4 · I) · v = [ [ 0.4, 0.4 ], [ 0.2, 0.2 ] ] · v = 0 => v1 + v2 = 0 => v2 = [ 1, -1 ]^T.

Express initial state x_0 as a linear combination of eigenvectors:

x_0 = [ 0, 1 ]^T = c1 · π + c2 · v2 = c1 · [ 2/3, 1/3 ]^T + c2 · [ 1, -1 ]^T

• Row 1: (2/3) c1 + c2 = 0 => c2 = -(2/3) c1
• Row 2: (1/3) c1 - c2 = 1 => (1/3) c1 - (-(2/3) c1) = 1 => (1/3 + 2/3) c1 = 1 => c1 = 1.

Then c2 = -2/3.

State at step t:

x(t) = P^t · x_0 = 1 · (1)^t · π + (-2/3) · (0.4)^t · [ 1, -1 ]^T

x(t) = π - (2/3) · (0.4)^t · [ 1, -1 ]^T

As t → infinity, because |λ2| = 0.4 < 1:

lim_{t → infinity} (0.4)^t = 0.

The transient error vanishes exponentially:

lim_{t → infinity} x(t) = π = [ 2/3, 1/3 ]^T.

In the long-term equilibrium, the server cluster will be in the Healthy state 66.67% of the time and in the Degraded state 33.33% of the time, completely independent of the starting state.