An Encoder-Transformer Architecture for Recognition of the Jordan Structure of a Matrix

Technical Summary: An Encoder-Transformer Architecture for Recognition of the Jordan Structure of a Matrix

Problem Formulation
The paper addresses the challenge of determining the size of the largest Jordan block in a matrix $A \in \mathbb{C}^{d \times d}$ (or $\mathbb{R}^{d \times d}$) that is close to being defective, specifically under finite precision constraints. In numerical linear algebra, round-off errors often render defective matrices (those with non-trivial Jordan blocks) diagonalizable, obscuring their true structural properties. The authors formalize the problem as finding the largest integer $m$ such that there exists a Jordan matrix $J$ (with a single eigenvalue of zero and a maximal block of size $m$) and an invertible matrix $S$ satisfying:

1. $\kappa(S) \leq \kappa_{\max}$ (a bound on the condition number of the similarity transformation, set to $200d$).
2. $\|S^{-1}AS - J\| \leq \epsilon_{\max}$ (a bound on the perturbation magnitude).

This formulation seeks the "attainable" Jordan block size under a specific noise level and conditioning constraint, rather than the nearest defective matrix in an unconstrained sense. The problem is motivated by the need to understand structural stability in dynamical systems ($x' = Ax$), where large Jordan blocks can induce transient growth even if eigenvalues suggest stability, and by the difficulty of recognizing these structures visually or via standard numerical methods.

Methodology
The authors propose a machine learning framework utilizing an Encoder-Transformer architecture to predict the maximal attainable Jordan block size $m$.

• Data Representation: Instead of processing a single matrix, the model takes a sequence of matrix powers $(A, A^2, \dots, A^d)$ as input. This leverages the property that for a nilpotent matrix (zero eigenvalue), the rank of successive powers $A^k$ uniquely determines the Jordan block sizes. The input matrices are real-valued, generated as $A = S(J + \epsilon E)S^{-1}$, where $J$ is a Jordan matrix with eigenvalue 0, $S$ is a random similarity matrix with bounded condition number, and $E$ is a normalized Ginibre noise matrix.
• Architecture:
  • Encoders: For each dimension $d$, a dedicated Multilayer Perceptron (MLP) encoder processes the input matrices $A^k$. These encoders map the $d \times d$ matrices into a shared latent space of dimension $d_{latent}=32$. The encoders act as feature extractors and implicit denoisers.
  • Transformer: The sequence of latent embeddings is processed by a dimension-independent Transformer (2 layers, 4 attention heads). This component learns the global structural relationships between the powers of the matrix, focusing on the "vanishing" behavior of the sequence rather than local entry-wise correlations.
  • Classifier: A dimension-specific MLP head performs mean pooling on the Transformer output and classifies the maximal block size $m \in \{1, \dots, d\}$.
• Training Strategy:
  • Soft Targets: To handle numerical uncertainty, the training targets are not one-hot encodings but soft distributions. For negligible perturbation ($\epsilon \leq \epsilon_0$), the target is the true class. For larger $\epsilon$, the target follows a discrete Gaussian-like kernel centered at the true class, with variance scaling logarithmically with $\epsilon$. This allows the model to learn the uncertainty inherent in the problem.
  • Two-Phase Training: Phase 1 trains encoders, classifiers, and the Transformer simultaneously on dimensions $d \in \{4, 6, 9, 12, 15, 28\}$. Phase 2 freezes the Transformer and trains new encoders/classifiers for unseen dimensions (e.g., $d=33, 35$) to test generalization.
  • Loss Function: The model is optimized using the Kullback-Leibler (KL) divergence between the predicted distribution and the soft-target distribution.

Key Results

• Accuracy: The model achieves high classification accuracy on synthetically generated data. For small perturbations, accuracy approaches 1.0. Even under significant perturbations ($\epsilon$ up to $0.1$) and varying spectral radii, the "relaxed accuracy" (predicting within $\pm 1$ of the true size) remains above 0.9 for most cases.
• Generalization: The model demonstrates strong generalization to matrix dimensions ($d=33, 35$) not seen during the Transformer's initial training phase. It also performs well on matrices with different Segre characteristics (different Jordan block configurations) than those in the training set.
• Comparison to Baselines: The proposed architecture significantly outperforms a classical numerical baseline based on computing the rank of matrix powers via Singular Value Decomposition (SVD). The baseline fails rapidly as perturbation magnitude increases, whereas the neural network maintains robustness, effectively mitigating heavy noise.
• Internal Analysis: Inspection of the model reveals that the encoders successfully map the magnitude of matrix powers to the latent space (reflecting the theoretical nullity). The Transformer's attention mechanism focuses heavily on the tokens corresponding to the first vanishing (or near-vanishing) matrix powers, which aligns with the theoretical rank-difference formula for Jordan blocks.

Significance and Claims
The paper claims that this work introduces a novel approach to a longstanding numerical linear algebra problem by leveraging deep learning. The primary significance lies in the architecture's ability to:

1. Capture Structural Properties: The model learns dimension-agnostic algebraic rules regarding nilpotency and Jordan structure, rather than memorizing specific matrix patterns.
2. Handle Numerical Noise: By training with soft targets and utilizing an encoder-decoder structure, the model is more robust to the round-off errors and perturbations that typically defeat classical numerical algorithms.
3. Overcome Lack of Spatial Structure: Unlike Vision Transformers (ViTs) which rely on spatial locality, this architecture adapts the Transformer to process algebraic sequences, successfully identifying global structural properties in matrices that lack local correlations.

The authors modestly note limitations: the current implementation is restricted to real-valued matrices with a single eigenvalue cluster (handled via Riesz projection in theory, though training used single clusters) and does not yet extend to matrix pencils. However, the results suggest that learned models can generalize to classes of matrices not seen during training, offering a promising alternative to purely numerical methods for detecting matrix defectiveness.