🔢 mathematics

Computing Left Eigenvalues of Quaternion Matrices

This paper introduces a practical Newton-based method using standard real and complex linear algebra kernels to compute left eigenvalues of quaternion matrices of any size, demonstrating its effectiveness through extensive testing and a MATLAB implementation that handles complex spectral phenomena up to 64x64 dimensions.

Original authors: Michael Sebek

Published 2026-03-03

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Michael Sebek

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to find the "secret keys" that unlock a complex machine. In the world of standard math (using regular numbers or complex numbers), finding these keys is like solving a puzzle with a known number of solutions. You know exactly how many keys to look for, and they are usually distinct, separate points.

But this paper deals with Quaternions. Think of quaternions as a "super-number" system used to describe 3D and 4D rotations (like how a drone or a video game character spins in space). They are powerful, but they have a weird quirk: order matters. If you multiply Quaternion A by B, you get a different result than if you multiply B by A.

Because of this weirdness, finding the "keys" (called Left Eigenvalues) for a matrix of quaternions is like trying to find the keys to a machine that keeps changing its shape.

Here is the breakdown of what this paper does, using some everyday analogies:

1. The Problem: A Moving Target

In normal math, if you have a 3x3 grid of numbers, you expect to find exactly 3 "keys" (eigenvalues).

The Quaternion Twist: With quaternions, the rules are messy. Sometimes you find 3 keys. Sometimes you find 5! Sometimes you find infinite keys that form a perfect sphere (like the surface of a ball).
The "Gauge" Issue: Imagine you are trying to measure a spinning top. If you don't hold it steady, your measurement keeps spinning with it. In math terms, the "eigenvector" (the direction the key points) can be rotated freely without changing the key itself. To do the math, you have to "pin" the spinning top in place so you can measure it. This paper figures out exactly how to pin it down without breaking the math.

2. The Solution: A Smart "Newton" Tracker

The author, Michael Sebek, built a new tool to find these keys. He calls it a Newton-based method.

The Analogy: Imagine you are in a dark room trying to find a specific light switch. You take a step, feel the wall, and realize, "Oh, I'm too far left." You adjust, take another step, and get closer. You keep doing this until you hit the switch. This is the "Newton method"—a step-by-step process of getting closer to the answer.
The Innovation: Previous methods tried to solve the whole puzzle at once by writing out a giant, messy equation (like trying to solve a Rubik's cube by writing down every possible move). This new method is smarter. It takes small, direct steps, fixing the "spinning top" (the gauge) at every step to keep the math stable.

3. The Magic Trick: Translation

The hardest part of quaternion math is that computers don't natively understand them well.

The Analogy: Imagine you are an English speaker trying to talk to a French speaker. You could try to learn French, or you could use a translator.
The Paper's Trick: This method acts as a translator. It takes the quaternion problem, translates it into standard "Real" numbers (the kind your computer loves), solves the puzzle using standard, fast tools, and then translates the answer back into quaternions. It does this so efficiently that it can handle huge matrices (up to 64x64) that would have crashed older methods.

4. Handling the Weird Cases (The "Zoo")

The paper doesn't just find the "normal" keys; it also handles the weird, rare cases that usually break math software.

The Sphere: Sometimes the keys aren't points; they are a whole sphere. The method doesn't panic. It finds a few sample points on that sphere and says, "Aha! This looks like a ball-shaped solution!"
The Shortage: Sometimes there are fewer keys than expected. The method detects this and says, "This machine is broken (or special), it's missing keys," rather than crashing.
The Overload: Sometimes there are more keys than expected. The method finds them all and sorts them out.

5. The Result: A Reliable Toolbox

The author didn't just write theory; he built a MATLAB toolbox (a software package) that anyone can use.

The Certificate: Every time the software finds a key, it gives you a "certificate of authenticity." It's like a receipt that says, "We are 99.999% sure this is the correct key, and here is the proof."
Reproducibility: If you run the code on your computer, you get the exact same result as the author. This is crucial for science, ensuring that the "keys" found are real and not just computer glitches.

Summary

Think of this paper as building a GPS for a 4D maze.

Old Way: You tried to draw the whole map on paper, but the map kept shifting, and you got lost.
New Way: You have a GPS (the Newton method) that translates the 4D maze into a 2D map your car can read, guides you step-by-step to the destination, and tells you if the destination is a single point, a whole island, or a missing location.

This makes it possible for engineers and scientists to use these powerful quaternion tools for robotics, signal processing, and control systems without getting stuck in the mathematical weeds.

1. Problem Statement

The paper addresses the computational challenge of finding left eigenvalues of quaternion matrices ( $A \in \mathbb{H}^{n \times n}$ ). A quaternion $\lambda$ is a left eigenvalue if there exists a non-zero vector $v$ such that $Av = \lambda v$ .

Unlike the complex case, computing left eigenvalues in quaternions presents unique difficulties:

Non-commutativity: The left spectrum is not invariant under quaternionic similarity, and eigenvectors are only defined up to right scaling ( $v \to vq$ ).
Spectral Geometry: The left spectrum can contain not only isolated points but also continuous components (specifically, 2-spheres).
Non-generic Phenomena: The number of isolated eigenvalues can be less than $n$ (spectrum deficiency) or greater than $n$ .
Computational Complexity: Traditional approaches involving determinantal elimination lead to high-degree nonlinear polynomial systems in $\mathbb{R}^4$ that are numerically unstable and computationally expensive for moderate $n$ .

The goal is to develop a practical, robust, and reproducible method that handles these complexities without requiring specialized quaternionic linear algebra kernels, relying instead on standard real/complex linear algebra.

2. Methodology

The author proposes a Newton-based iterative method formulated directly on the eigenpair defect equation, augmented with a gauge constraint to handle the non-uniqueness of eigenvectors.

A. Gauge Constraint and Formulation

To make the system well-posed for Newton's method, the right-scaling freedom of the eigenvector $x$ must be fixed. The paper introduces a smooth gauge map $g(x)$ that enforces:

Normalization: $\|x\|_2 = 1$ .
Real Pivot: A specific component $x_j$ is real and positive ( $x_j \in \mathbb{R}_{>0}$ ).

This transforms the problem into finding a root of the augmented system $F(\lambda, x) = (Ax - \lambda x, g(x)) = (0, 0)$ .

B. Real Embedding Strategy

Instead of developing quaternion-specific solvers, the method utilizes a real embedding $\rho(\cdot)$ .

Every quaternion matrix $A$ is mapped to a real matrix $\rho(A) \in \mathbb{R}^{4n \times 4n}$ using the left-multiplication matrix $L(q)$ .
The Newton correction step, which solves for increments $(\Delta \lambda, \Delta x)$ , is converted into a square real linear system of size $(4n+4) \times (4n+4)$ .
This allows the use of standard, highly optimized real linear algebra kernels (e.g., LU decomposition, SVD) available in libraries like LAPACK, ensuring numerical stability and efficiency.

C. Algorithmic Pipeline

Multi-Start Strategy: Since the spectrum may contain multiple isolated points or continuous components, the algorithm runs multiple trials with random initial guesses.
Newton Iteration: For each trial, it performs damped Newton steps to reduce the defect $\|Ax - \lambda x\|$ .
Regauging: After each step, the eigenvector is re-scaled to satisfy the gauge constraint.
Acceptance & Deduplication: Converged candidates are accepted if their residual certificates (based on the smallest singular value of the embedded matrix) are below a threshold. Duplicates are removed based on distance in $\mathbb{R}^4$ .
Spherical Detection: If multiple distinct points converge to the same manifold, a post-processing step fits a sphere model to detect continuous spectral components.
Polishing: A two-stage refinement (minimizing the minimal residual followed by a final Newton step) is applied to push residuals to machine precision.

3. Key Contributions

Direct Newton Formulation: Derivation of a Newton iteration for quaternion left eigenpairs that explicitly fixes the eigenvector gauge, resulting in a square real-analytic system with a transparent Jacobian structure.
Theoretical Convergence: Proof of local quadratic convergence for "simple" gauged left eigenpairs (where the Jacobian is invertible). The paper also analyzes the behavior in non-isolated (spherical) cases, noting that while quadratic convergence to a unique root is impossible, the method effectively samples the manifold.
Robust Solver Architecture: A complete pipeline including multi-start initialization, restart logic, de-duplication, and residual-based certification that handles ill-conditioning and degeneracy.
Comprehensive Validation: Extensive testing on literature examples (2x2 and 3x3 cases with known closed-form solutions) and large-scale benchmarks (up to $64 \times 64$ ) across various matrix families (dense, Hermitian, triangular, sparse).
Open Source Implementation: Provision of a compact, stand-alone MATLAB reference implementation that requires no third-party toolboxes, supporting reproducibility.

4. Results

Accuracy: The method achieves residuals close to machine precision ( $\approx 10^{-16}$ ) for isolated eigenvalues across all tested sizes ( $n \le 64$ ).
Handling Non-Generic Cases:
- Spectrum Deficiency: Successfully identified matrices with fewer than $n$ isolated eigenvalues.
- Excess Eigenvalues: Detected cases with more than $n$ isolated eigenvalues (e.g., a $3 \times 3$ matrix with 5 distinct eigenvalues).
- Spherical Components: Successfully detected and parameterized 2-sphere components in the spectrum by clustering converged points and fitting sphere models.
Performance: The multi-start pipeline achieved a 100% success rate in recovering $n$ distinct eigenpairs for generic random matrices up to size $64 \times 64$ . The computational cost is dominated by the embedded real linear solves, which scale efficiently.

5. Significance

This work bridges a critical gap in numerical linear algebra for quaternions. Prior to this, reliable computation of left eigenvalues for general matrices of moderate size was difficult due to the lack of robust algorithms that could handle the non-commutative nature and continuous spectral components.

Practical Utility: By relying on standard real linear algebra, the method is immediately implementable and efficient on modern hardware.
Diagnostic Power: The inclusion of residual certificates and the ability to distinguish between isolated points and spherical continua provides a level of diagnostic insight previously unavailable for general quaternion matrices.
Foundation for Future Research: The provided "Zoo" of non-generic examples and the open-source code serve as a benchmark for future theoretical and computational developments in quaternion spectral theory.

In summary, Sebek presents a rigorous, practical, and reproducible framework that transforms the difficult problem of quaternion left eigenvalue computation into a manageable sequence of real linear algebra problems, effectively handling both generic and pathological spectral structures.