Computing Left Eigenvalues of Quaternion Matrices

Titel: Berekening van Linker Eigenwaarden van Quaternion Matrices

Auteur: Michael Sebek (Technische Universiteit Praag)
Doel: Het presenteren van een praktische, Newton-gebaseerde methode voor het berekenen van linker eigenwaarden van quaternion-matrices, met name voor matrices van gemiddelde tot grote omvang.

1. Het Probleem

Quaternion-matrices komen van nature voor in toepassingen zoals ruimtelijke rotaties, kinematica, polarisatie en signaalverwerking. Hoewel de lineaire algebra over quaternions ($\mathbb{H}$) veel overeenkomsten heeft met die over complexe getallen ($\mathbb{C}$), introduceert de niet-commutativiteit van quaternions aanzienlijke complexiteit bij spectrale vraagstukken.

Specifiek richt dit paper zich op linker eigenwaarden: een quaternion $\lambda \in \mathbb{H}$ is een linker eigenwaarde van een matrix $A \in \mathbb{H}^{n \times n}$ als er een niet-nul vector $v \in \mathbb{H}^n$ bestaat zodanig dat:
$$Av = \lambda v$$

De uitdagingen bij het numeriek oplossen hiervan zijn:

• Niet-invariantie: In tegenstelling tot rechter eigenwaarden, is het spectrum van linker eigenwaarden niet invariant onder quaternion-similariteit.
• Complexe structuur: Het spectrum kan bestaan uit geïsoleerde punten, continue componenten (voornamelijk "sferische" families) of een mengsel van beide.
• Afwijking van de generieke verwachting: Het aantal geïsoleerde eigenwaarden kan afwijken van $n$ (er kunnen meer dan $n$ zijn, of er kan een "tekort" aan eigenwaarden zijn).
• Numerieke moeilijkheden: Standaard methoden zoals het elimineren van de eigenvector leiden tot hoge-graad niet-lineaire polynomen in $\mathbb{R}^4$, wat rekenkundig onhaalbaar wordt naarmate $n$ groeit. Bovendien zijn Jacobianen vaak singulier bij niet-geïsoleerde oplossingen.

2. Methodologie

De auteur ontwikkelt een Newton-gebaseerde methode die direct werkt op de defectvergelijking $Av - \lambda v = 0$, in plaats van te werken met determinanten of karakteristieke polynomen.

Kerncomponenten van de methode:

1. Gauge-beperking (Normering):
   Omdat een linker eigenvector $v$ uniek is tot op een rechter-schaalingsfactor ($v \to vq$), moet deze vrijheid worden vastgezet om een goed gesteld stelsel te krijgen. De methode imposeert een "gauge-constraint":

   • Normering: $\|v\|_2 = 1$.
   • Reële pivot: Een specifiek element $v_j$ wordt reëel en positief gemaakt.
     Dit transformeert het probleem naar een vierkante, gladde stelselvergelijking in reële coördinaten.

2. Real Embedding ($\rho(\cdot)$):
   Om standaard lineaire algebra-routines te kunnen gebruiken, worden quaternion-matrices gemapt naar reële matrices van dimensie $4n \times 4n$.

   • Een quaternion $q = a + bi + cj + dk$ wordt gemapt naar een $4 \times 4$ reële matrix $L(q)$ die linkermultiplicatie representeert.
   • De quaternion-matrix $A$ wordt gemapt naar $\rho(A)$, een blok-matrix bestaande uit deze $4 \times 4$ blokken.
   • Dit maakt het mogelijk om de Newton-stap op te lossen als een enkel lineair stelsel in $\mathbb{R}^{4n+4}$.

3. Newton-iteratie:
   De methode lost het vergrote stelsel op:
   $$\begin{bmatrix} \rho(A - \lambda I) & -B(x) \\ C(x) & 0 \end{bmatrix} \begin{bmatrix} u \\ w \end{bmatrix} = -\begin{bmatrix} \text{vec}(Av - \lambda v) \\ 0 \end{bmatrix}$$
   Waarbij $u$ en $w$ de updates zijn voor de vector en de eigenwaarde, en $B(x)$ en $C(x)$ de koppeling en de lineaire gauge-beperkingen vertegenwoordigen.

4. Globale Strategie (Multi-start):
   Omdat Newton lokaal convergent is, gebruikt de solver een "trial-based multi-start" strategie:

   • Meerdere startpunten worden gegenereerd.
   • Acceptatiecriteria gebaseerd op residuen.
   • De-duplicatie van gevonden oplossingen.
   • Voor niet-geïsoleerde gevallen (sferische componenten) worden meerdere convergentiepunten verzameld en gefit met een bolmodel in $\mathbb{R}^4$.

5. Post-processing (Polishing):
   Een twee-staps verfijning verbetert de nauwkeurigheid: eerst wordt de eigenwaarde geoptimaliseerd om het minimale residu te minimaliseren, gevolgd door een lokale Newton-correctie op het eigenpaar.

3. Belangrijkste Bijdragen

• Efficiënte Newton-iteratie: Afgeleide van een Newton-iteratie voor quaternion-eigenparen die expliciet de gauge vastlegt, wat leidt tot een vierkant reëel-analytisch stelsel met een transparante Jacobiaan-structuur.
• Robuuste Solver: Een globale solver met multi-start, acceptatie, herstart en de-duplicatie logica, specifiek ontworpen voor de unieke eigenschappen van quaternion-spectra.
• Certificering en Diagnostiek: De methode levert reproduceerbare resultaten met residu-gebaseerde certificaten. Het kan onderscheid maken tussen geïsoleerde eigenwaarden en monsters van sferische componenten, en detecteert niet-generieke fenomenen (zoals spectrum-tekort of meer dan $n$ eigenwaarden).
• Referentie-implementatie: Een compacte, zelfstandige MATLAB-implementatie is beschikbaar die alleen standaard MATLAB-functies gebruikt (geen externe toolboxes nodig).

4. Resultaten en Validatie

De methode is uitgebreid getest op:

• Literatuurvoorbeelden: Bekende $2 \times 2$ en $3 \times 3$ gevallen (o.a. van Huang & So, Macías-Virgós) met bekende gesloten vormen. De methode herkent correct geïsoleerde punten, sferische families en degeneraties.
• Benchmark Ensembles: Testen op matrices tot grootte $64 \times 64$ voor diverse families (dicht i.i.d., Hermitisch, driehoekig, spaarzaam).
  • De solver bereikte een succespercentage van 100% (herstel van $n$ eigenparen) voor de meeste generieke gevallen.
  • Residuen werden vaak verlaagd tot machine-nauwkeurigheid ($\approx 10^{-16}$).
• Niet-generieke Fenomenen:
  • Meer dan $n$ eigenwaarden: Er werden voorbeelden gevonden van $3 \times 3$ matrices met 5 distincte geïsoleerde eigenwaarden.
  • Spectrum-tekort: Voorbeelden van $4 \times 4$ matrices met slechts 2 geïsoleerde eigenwaarden.
  • Sferische componenten: Detectie en parameterisatie van sferische continuums in combinatie met geïsoleerde punten.

5. Betekenis en Conclusie

Dit paper biedt een praktische en schaalbare oplossing voor een langdurig open probleem in de numerieke lineaire algebra: het betrouwbaar berekenen van linker eigenwaarden van quaternion-matrices.

• Theoretisch: Het bewijst lokale kwadratische convergentie voor eenvoudige, geïsoleerde eigenparen en biedt een kader voor het omgaan met niet-geïsoleerde gevallen (sferen).
• Praktisch: Door alleen standaard reële/complex lineaire algebra-kernen te gebruiken via embedding, is de methode efficiënt en robuust. De beschikbaarheid van een open-source MATLAB-implementatie en uitgebreide "Zoo" van voorbeelden maakt het een waardevol hulpmiddel voor onderzoek en toepassingen in controletheorie, robotica en signaalverwerking.

De methode vult een belangrijke lacune op tussen theoretische karakterisaties en praktische berekeningen, en maakt het mogelijk om complexe spectrale verschijnselen in quaternion-systemen voor het eerst systematisch te onderzoeken en te certificeren.