🔢 mathematics

A Jacobi-like algorithm for normal matrices by the skew-symmetric part

This paper presents a fast Jacobi-like algorithm that leverages Paardekooper's method for skew-symmetric matrices to efficiently compute the eigenvalues and eigenvectors of real normal matrices, particularly those with predominantly complex eigenvalues, while also providing explicit formulas for nearest symmetric skew-Hamiltonian and ortho-symplectic matrices.

Original authors: Simon Mataigne, P. -A. Absil

Published 2026-05-27

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Simon Mataigne, P. -A. Absil

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 have a giant, complex puzzle made of numbers (a matrix). Your goal is to rearrange the pieces so that the puzzle reveals its hidden "secret numbers" (eigenvalues) clearly, without any of the pieces getting mixed up.

For a specific type of puzzle called a Normal Matrix, mathematicians have been trying to find the fastest way to solve it. This paper introduces a new, faster method to do exactly that. Here is how the authors explain their approach using simple concepts:

The Problem: A Noisy Room

Think of a normal matrix as a room full of people talking. Some people are speaking in pairs (complex numbers), and some are speaking alone (real numbers). The "noise" in the room is the messiness of the conversation—the parts that don't make sense yet.

Old methods for solving this puzzle were like trying to listen to every single person in the room one by one, or using a very expensive, slow microphone that converts everything into a different language (complex arithmetic) just to understand it. This is accurate but takes a long time.

The New Idea: Tuning the "Skew-Symmetric" Part

The authors realized that inside this noisy room, there is a specific type of background noise called the skew-symmetric part. It's like the echo in the room.

They discovered that if you can organize the echo first, the rest of the room falls into place much faster. They used a known technique (Paardekooper's method) that is excellent at organizing this specific "echo."

The Three-Step Dance

The new algorithm they built is like a three-step dance to clean up the room:

Step 1: The Echo Cleanup (Paardekooper's Method)
First, they ignore the main conversation and focus entirely on organizing the "echo" (the skew-symmetric part). They use a fast, specialized tool to arrange this part into neat, small blocks. Because this tool is so fast, it clears out the biggest mess in the room very quickly.

Analogy: Imagine a janitor who only sweeps the floor in a specific pattern. Once the floor is swept, the furniture (the rest of the matrix) is easier to see.

Step 2: Sorting the Groups
Once the echo is organized, the authors look at the remaining conversation. They realized the room naturally splits into three types of groups:

The "Symmetric" Group: People who are speaking in perfect harmony (real eigenvalues).
The "Skew-Hamiltonian" Group: People speaking in a special, mirrored pattern (eigenvalues with repeated imaginary parts).
The "Close Call" Group: People whose voices are so similar they are hard to distinguish (eigenvalues that are very close together).

The algorithm uses different, specialized tools for each group:

For the Symmetric Group, it uses a classic, reliable method (Jacobi's algorithm) to separate them.
For the Skew-Hamiltonian Group, it uses a specialized "mirror" method to untangle them.
For the Close Call Group, it applies a gentle, final polish.

Step 3: The Final Polish
After the first two steps, the room is 99% clean. There might be tiny specks of dust left (tiny errors). The algorithm runs a very quick, final sweep to make sure everything is perfectly aligned. Because the heavy lifting was done in Step 1, this final step is incredibly fast.

Why is this better?

The paper claims this method is 5 to 10 times faster than other similar methods, especially for matrices where most numbers are complex (like random matrices used in statistics).

The Analogy: Imagine you are trying to sort a pile of mixed-up socks. Old methods might try to match every sock to every other sock one by one. This new method first separates all the socks by color (the "echo" step), which is fast. Then, it quickly matches the pairs within those color groups. It saves a massive amount of time.

The Results

The authors tested their method on thousands of random puzzles. They found that:

Speed: It finished the job much faster than the competition.
Accuracy: It was just as accurate as the slower methods, finding the "secret numbers" with high precision.
Robustness: It worked well even when the puzzles were tricky or had repeating patterns.

A Bonus Discovery

While building this algorithm, the authors also figured out how to find the "nearest" version of two very specific, rare types of mathematical shapes (symmetric skew-Hamiltonian and ortho-symplectic matrices). Think of this as finding the closest perfect circle to a slightly squashed one. They provided the exact formulas to do this, which helps explain why their main algorithm works so well.

In short: The authors found a shortcut. Instead of attacking the whole complex problem at once, they used a fast trick to organize a specific part of the problem first, which made the rest of the solution fall into place almost instantly.

Technical Summary: A Jacobi-Like Algorithm for Normal Matrices by the Skew-Symmetric Part

Problem Statement
The paper addresses the real normal eigenvalue problem (EVP), which involves computing the eigenvalues and optionally the eigenvectors of a real normal matrix $A$ . While Jacobi's algorithm is a classical method for symmetric matrices, extending it to normal matrices is challenging. Existing generalizations, such as the method by Goldstine and Horwitz, often rely on complex arithmetic, which is computationally more expensive and ignores the inherent structure of real matrices. Other real-arithmetic approaches, such as those by Zhou and Brent or Bunse-Gerstner et al., rely on subroutines for the real Schur decomposition of arbitrary $4 \times 4$ matrices, which can be computationally intensive. The authors note that while Jacobi-like algorithms have regained popularity due to their parallelizability, they often suffer from slower convergence or higher operation counts compared to competitors like the QR algorithm, particularly for matrices with complex eigenvalues.

Methodology
The proposed method is a Jacobi-like algorithm that exploits the commutativity of the symmetric and skew-symmetric parts of a real normal matrix. The core innovation is utilizing Paardekooper's method—a fast, quadratically convergent algorithm for skew-symmetric matrices—as a primary driver for the decomposition.

The algorithm (Algorithm 5.1) proceeds in three distinct steps:

Step I: Implicit Paardekooper's Method.
The algorithm first applies Paardekooper's method implicitly to the skew-symmetric part $\Omega = \text{skew}(A)$ . Instead of transforming $\Omega$ directly, the rotations derived from $\Omega$ are applied to the full matrix $A$ . This step continues until the off-diagonal blocks of $\Omega$ are reduced below a prescribed threshold $\rho$ . Theoretically, this block-diagonalizes the skew-symmetric part, which, for normal matrices, reveals the structure of the eigenvalues.
Step II: Block Identification and Specialized Diagonalization.
After Step I, the matrix $A$ is not yet fully block-diagonal. The algorithm identifies connected components (non-zero submatrices) in $A$ based on the threshold $\sqrt{\rho}\|A\|_F$ . These components are categorized into three types based on perturbation analysis:
- Symmetric Skew-Hamiltonian (SSkH) Blocks: If a block corresponds to eigenvalues with repeated nonzero imaginary parts, it is treated as a perturbed SSkH matrix. The algorithm computes the nearest SSkH matrix and diagonalizes it using a specialized Jacobi-like method (Algorithm 5.3) adapted from techniques for symmetric skew-Hamiltonian matrices.
- Symmetric Blocks: If a block corresponds to real eigenvalues, it is treated as a perturbed symmetric matrix. The algorithm applies the standard Jacobi method for symmetric matrices (Algorithm 5.4) to the symmetric part of the block.
- General Blocks: If the perturbation is too large for the specialized methods (e.g., eigenvalues with close but distinct imaginary parts), the block is passed to a general normal matrix solver.
Step III: Accuracy Refinement.
A final step applies a standard Jacobi-like algorithm for normal matrices (specifically, the method by Zhou and Brent) to the entire matrix. Because Steps I and II have already reduced the off-diagonal elements significantly, this final step benefits from quadratic local convergence, requiring very few sweeps (typically one or two) to achieve the target accuracy $\rho$ .

Key Contributions

Algorithmic Design: The paper introduces a hybrid Jacobi-like algorithm that leverages the speed of Paardekooper's method for skew-symmetric matrices to accelerate the solution of the real normal EVP.
Implicit Transformation: The method applies transformations derived from the skew-symmetric part directly to the normal matrix, preserving real arithmetic and avoiding complex number operations.
Perturbation Analysis: The authors provide a rigorous perturbation analysis (Section 6) that quantifies how inexactness in the Schur decomposition of the skew-symmetric part affects the structure of the normal matrix. This analysis justifies the specific branching logic in Step II, determining when to use specialized SSkH or symmetric solvers versus a general solver.
Nearest Matrix Formulas: The paper derives explicit formulas for the nearest symmetric skew-Hamiltonian matrix and the nearest ortho-symplectic matrix (Section 8), which are critical for the perturbation bounds and the design of the specialized diagonalization steps.

Results
Numerical experiments (Section 7) compare Algorithm 5.1 against four other Jacobi-like algorithms: Bunse-Gerstner et al., Goldstine and Horwitz, Zhou and Brent, and a randomized method (RandDiag).

Accuracy: Algorithm 5.1 consistently achieves the target accuracy ( $\text{offschur}(A) \leq \rho \|A\|_F$ ) across various distributions of normal matrices, including those with real eigenvalues, repeated imaginary parts, and random orthogonal matrices. It performs comparably to the most accurate competitors.
Efficiency: The proposed method demonstrates a significant speed advantage, being 5 to 10 times faster than the other Jacobi-like algorithms in terms of running time. This gain is attributed to the rapid convergence of Paardekooper's method in the initial steps, which reduces the workload for the final refinement step.
Robustness: The method remains robust even when eigenvalues have repeated or closely spaced imaginary parts, scenarios where other methods might struggle or require more iterations.

Significance
The paper claims that the proposed algorithm offers a computationally superior alternative for solving the real normal eigenvalue problem, particularly for matrices where most eigenvalues are complex, such as random orthogonal matrices arising in statistics on manifolds. By combining the structural properties of normal matrices with the efficiency of Paardekooper's method, the algorithm achieves high parallelizability and speed without sacrificing accuracy. The authors position this work as a practical improvement over existing Jacobi-like variants, noting that the method is most efficient in contexts where the skew-symmetric part provides a strong structural guide for the decomposition. The paper concludes by highlighting the availability of an open-source implementation for reproducibility.