Eigenvalue & Multiplicity Estimator

Overview

This MATLAB repository provides a numerical toolkit designed to estimate the eigenvalues of a square matrix along with their algebraic and geometric multiplicities.

The project evaluates the roots of the characteristic equation $f(z) = \det(A - zI)$ using standard and modified Newton's methods. To test and validate the algorithms, the suite includes functions to generate custom matrices with predefined spectral properties by constructing a matrix $A = Q^T J Q$, where $J$ is a custom Jordan block matrix and $Q$ is an orthonormal matrix.

Features

• Custom Matrix Generation: Build test matrices by specifying unique eigenvalues alongside their desired algebraic and geometric multiplicities.

• Newton's Method Root-Finding: Iteratively calculates eigenvalues from initial guesses using Newton's method on the matrix's characteristic polynomial.

• Algebraic Multiplicity Estimation: Employs a modified Newton's method combined with convergence heuristics to estimate the algebraic multiplicity of a found eigenvalue.

• Geometric Multiplicity Estimation: Uses LU factorization on $A - \lambda I$ to determine the geometric multiplicity by evaluating the rank deficiency based on a custom tolerance.

• Diagonalizability Check: Automatically compares the estimated algebraic and geometric multiplicities to determine if the matrix is diagonalizable.

• Visualization: Plots the convergence of $f(z)$ across iterations for different initial guesses to help visualize the Newton method's behavior.

Repository Structure

• main.m: The primary script to run the project. It sets up the test parameters (tolerances and iterations) , generates the test matrix, defines initial guesses, executes the estimation functions, plots the convergence, and prints the final diagonalizability report.

• jordan.m: Constructs a Jordan block matrix $J$ based on an array of unique eigenvalues and their corresponding algebraic and geometric multiplicities.

• multalg.m: Executes the standard Newton's method for a set number of iterations, then applies an algorithmic heuristic to estimate the algebraic multiplicity $m$, and follows up with a modified Newton's method to secure convergence.

• multgeo.m: Calculates the geometric multiplicity $k$ of a given eigenvalue $\lambda$. It performs an LU factorization of $B = A - \lambda I$ and counts the diagonal elements of $U$ that fall below a specified tolerance threshold.

• myobjective.m: Computes the objective function $f(z) = \det(A - zI)$ and its Newton step $g = -1 / \text{trace}((A - zI)^{-1})$ using LU factorization and permutation sign tracking.

• segno.m: A helper function that calculates the determinant (sign) of a permutation matrix $P$ by counting the number of row swaps required to achieve the identity matrix.

Usage

1. Open MATLAB and navigate to the repository directory.
2. Open main.m.
3. (Optional) Modify the target eigenvalues, desired multiplicities, and initial guesses (l0_candidates) in the "Parametri per i test" section to try different scenarios.
4. Run the script.
5. Observe the console output for the step-by-step estimations and the final diagonalizability check, and review the generated plot for convergence details.

Requirements

• MATLAB (No specific external toolboxes are strictly required as core functions utilize standard MATLAB linear algebra operations).