Πίνακας Χάιζενμπεργκ

Στη γραμμική άλγεβρα, ένας πίνακας Χάιζενμπεργκ είναι ένα ειδικό είδος τετραγωνικού πίνακα, ο οποίος είναι «σχεδόν» τριγωνικός. Για την ακρίβεια, ένας άνω πίνακας Χάιζενμπεργκ είναι μηδενικός κάτω από την πρώτη υποδιαγώνιο, και ένας κάτω πίνακας Χάιζενμπεργκ είναι μηδενικός πάνω από την πρώτη υπερδιαγώνιο. Πήραν το όνομά τους από τον Καρλ Χάιζενμπεργκ.

Μια παραγοντοποίηση Χάιζενμπεργκ είναι μια παραγοντοποίηση ενός πίνακα $A$ σε έναν μοναδιαίο πίνακα $P$ και έναν πίνακα Χάιζενμπεργκ $H$ έτσι ώστε $PHP^{*}=A$ όπου $P^{*}$

είναι ο συζυγής ανάστροφος πίνακας.

Ορισμοί

Ανώτερος πίνακας Χάιζενμπεργκ

Ένας τετραγωνικός $n\times n$ πίνακας $A$ λέγεται ότι είναι σε ανώτερη μορφή Χάιζενμπεργκ ή ότι είναι ανώτερος πίνακας Χάιζενμπεργκ αν $a_{i,j}=0$ για όλα τα $i,j$ με $i>j+1$.

Ένας ανώτερος πίνακας Χάιζενμπεργκ ονομάζεται μη αναγωγικός αν όλες οι υποδιαγώνιες είναι μη μηδενικές, δηλαδή αν $a_{i+1,i}\neq 0$ για όλα τα $i\in \{1,\ldots ,n-1\}$.

Κατώτερος πίνακας Χάιζενμπεργκ

Ένας τετραγωνικός $n\times n$ πίνακας $A$ λέγεται ότι είναι σε κατώτερη μορφή Χάιζενμπεργκ ή ότι είναι κατώτερος πίνακας Χάιζενμπεργκ αν ο μεταθέτης του ${\displaystyle }$ είναι ένας ανώτερος πίνακας Χάιζενμπεργκ ή ισοδύναμα αν $a_{i,j}=0$ για όλα τα $i,j$ με $j>i+1$.

Ένας κατώτερος πίνακας Χάιζενμπεργκ ονομάζεται μη αναγωγικός αν όλες οι υπερδιαγώνιες είναι μη μηδενικές, δηλαδή αν $a_{i,i+1}\neq 0$ για όλα τα $i\in \{1,\ldots ,n-1\}$.

Παραδείγματα

Ας εξετάσουμε τους ακόλουθους πίνακες.

$A={\begin{bmatrix}1&4&2&3\\3&4&1&7\\0&2&3&4\\0&0&1&3\\\end{bmatrix}}$

$B={\begin{bmatrix}1&2&0&0\\5&2&3&0\\3&4&3&7\\5&6&1&1\\\end{bmatrix}}$

$C={\begin{bmatrix}1&2&0&0\\5&2&0&0\\3&4&3&7\\5&6&1&1\\\end{bmatrix}}$

Ο πίνακας $A$ είναι ένας ανώτερος μη μειωμένος πίνακας Χάιζενμπεργκ, ο $B$ είναι ένας κατώτερος μη μειωμένος πίνακας Χάιζενμπεργκ και ο $C$ είναι ένας κατώτερος πίνακας Χάιζενμπεργκ αλλά δεν είναι μη μειωμένος.

Προγραμματισμός υπολογιστών

Πολλοί αλγόριθμοι γραμμικής άλγεβρας απαιτούν σημαντικά λιγότερη υπολογιστική προσπάθεια όταν εφαρμόζονται σε τριγωνικούς πίνακες, και αυτή η βελτίωση συχνά μεταφέρεται και στους πίνακες Χάιζενμπεργκ. Εάν οι περιορισμοί ενός προβλήματος γραμμικής άλγεβρας δεν επιτρέπουν την εύκολη αναγωγή ενός γενικού πίνακα σε τριγωνικό, η αναγωγή σε μορφή Χάιζενμπεργκ είναι συχνά η αμέσως καλύτερη λύση. Στην πραγματικότητα, η αναγωγή οποιουδήποτε πίνακα σε μορφή Χάιζενμπεργκ μπορεί να επιτευχθεί σε πεπερασμένο αριθμό βημάτων (Παραδείγματος χάριν, μέσω του μετασχηματισμού Χάουσχόλντερ (Householder) των μοναδιαίων μετασχηματισμών ομοιότητας). Η επακόλουθη αναγωγή του πίνακα Χάιζενμπεργκ σε τριγωνικό πίνακα μπορεί να επιτευχθεί μέσω επαναληπτικών διαδικασιών, όπως η μετατοπισμένη QR-παραγοντοποίηση. Σε αλγορίθμους ιδιοτιμών, ο πίνακας Χάιζενμπεργκ μπορεί να αναχθεί περαιτέρω σε τριγωνικό πίνακα μέσω μετατοπισμένη QR-παραγοντοποίηση (Shifted QR-factorization) σε συνδυασμό με βήματα αποπληθωρισμού. Η αναγωγή ενός γενικού πίνακα σε πίνακα Χάιζενμπεργκ και στη συνέχεια η περαιτέρω αναγωγή σε τριγωνικό πίνακα, αντί της απευθείας αναγωγής ενός γενικού πίνακα σε τριγωνικό πίνακα, συχνά εξοικονομεί την αριθμητική που εμπλέκεται στον αλγόριθμο QR για προβλήματα ιδιοτιμών.

Αναγωγή στον πίνακα Χάιζενμπεργκ

Μετασχηματισμοί Χάουσχόλντερ

Κάθε $n\times n$ πίνακας μπορεί να μετασχηματιστεί σε πίνακα Χάιζενμπεργκ μέσω ενός μετασχηματισμού ομοιότητας χρησιμοποιώντας μετασχηματισμούς Χάουσχόλντερ. Η ακόλουθη διαδικασία για έναν τέτοιο μετασχηματισμό είναι προσαρμοσμένη από το Δεύτερο μάθημα γραμμικής άλγεβρας από Γκαρσία & Ρότζερ.

Έστω $A$ οποιοσδήποτε πραγματικός ή μιγαδικός $n\times n$ πίνακας, τότε έστω $A^{\prime }$ ο $(n-1)\times n$ υποπίνακας του $A$ που κατασκευάζεται αφαιρώντας την πρώτη γραμμή του $A$ και έστω $\mathbf {a} _{1}^{\prime }$ η πρώτη στήλη του $A'$. Κατασκευάζουμε τον $(n-1)\times (n-1)$ πίνακα των νοικοκυριών $V_{1}=I_{(n-1)}-2{\frac {ww^{*}}{\|w\|^{2}}}$ όπου

$w={\begin{cases}\|\mathbf {a} _{1}^{\prime }\|_{2}\mathbf {e} _{1}-\mathbf {a} _{1}^{\prime }\;\;\;\;\;\;\;\;,\;\;\;a_{11}^{\prime }=0\\\|\mathbf {a} _{1}^{\prime }\|_{2}\mathbf {e} _{1}+{\frac {\overline {a_{11}^{\prime }}}{|a_{11}^{\prime }|}}\mathbf {a} _{1}^{\prime }\;\;\;,\;\;\;a_{11}^{\prime }\neq 0\\\end{cases}}$

Αυτός ο πίνακας Χάουσχόλντερ αντιστοιχεί $\mathbf {a} _{1}^{\prime }$ σε $\|\mathbf {a} _{1}^{\prime }\|\mathbf {e} _{1}$ και ως εκ τούτου, ο πίνακας μπλοκ $U_{1}={\begin{bmatrix}1&\mathbf {0} \\\mathbf {0} &V_{1}\end{bmatrix}}$ θα αντιστοιχίσει τον πίνακα $A$ στον πίνακα $U_{1}A$ ο οποίος έχει μόνο μηδενικά κάτω από τη δεύτερη εγγραφή της πρώτης στήλης. Τώρα κατασκευάστε $(n-2)\times (n-2)$ πίνακα οικονόμων $V_{2}$ με παρόμοιο τρόπο όπως ο $V_{1}$ έτσι ώστε ο $V_{2}$ να αντιστοιχίζει την πρώτη στήλη του $A^{\prime \prime }$ στον $\|\mathbf {a} _{1}^{\prime \prime }\|\mathbf {e} _{1}$, όπου $A^{\prime \prime }$ είναι ο υποπίνακας του $A^{\prime }$ που κατασκευάζεται αφαιρώντας την πρώτη γραμμή και την πρώτη στήλη του $A^{\prime }$, τότε έστω $U_{2}={\begin{bmatrix}1&0&0\\0&1&0\\0&0&V_{2}\end{bmatrix}}$ που αντιστοιχίζει τον $U_{1}A$ στον πίνακα $U_{2}U_{1}A$ που έχει μόνο μηδενικά κάτω από την πρώτη και τη δεύτερη είσοδο της υποδιαγωνίου. Τώρα κατασκευάζουμε τον $V_{3}$ και στη συνέχεια τον $U_{3}$ με παρόμοιο τρόπο, αλλά για τον πίνακα $A^{\prime \prime \prime }$ που κατασκευάζεται αφαιρώντας την πρώτη γραμμή και την πρώτη στήλη του $A^{\prime \prime }$ και προχωρούμε όπως στα προηγούμενα βήματα. Συνεχίστε έτσι για συνολικά $n-2$ βήματα.

Από την κατασκευή του $U_{k}$, οι πρώτες στήλες $k$ οποιουδήποτε $n\times n$ πίνακα είναι αναλλοίωτες υπό τον πολλαπλασιασμό με $U_{k}^{*}$ από τα δεξιά. Επομένως, κάθε πίνακας μπορεί να μετασχηματιστεί σε έναν ανώτερο πίνακα Χάιζενμπεργκ μέσω ενός μετασχηματισμού ομοιότητας της μορφής $U_{(n-2)}(\dots (U_{2}(U_{1}AU_{1}^{*})U_{2}^{*})\dots )U_{(n-2)}^{*}=U_{(n-2)}\dots U_{2}U_{1}A(U_{(n-2)}\dots U_{2}U_{1})^{*}=UAU^{*}$.

Περιστροφές του Ιακομπί (Γκίβενς)

Μια περιστροφή Ιακομπί (που ονομάζεται επίσης περιστροφή Γκίβενς) είναι ένας ορθογώνιος μετασχηματισμός πίνακα της μορφής

$A\to A'=J(p,q,\theta )^{T}AJ(p,q,\theta )\;,$

όπου $J(p,q,\theta )$, $p<q$, είναι ο πίνακας περιστροφής Ιακομπί με όλα τα στοιχεία του πίνακα ίσα με μηδέν εκτός από το

$\left\{{\begin{aligned}J(p,q,\theta )_{ii}&{}=1\;\forall i\neq p,q\\J(p,q,\theta )_{pp}&{}=\cos(\theta )\\J(p,q,\theta )_{qq}&{}=\cos(\theta )\\J(p,q,\theta )_{pq}&{}=\sin(\theta )\\J(p,q,\theta )_{qp}&{}=-\sin(\theta )\;.\end{aligned}}\right.$

Μπορούμε να μηδενίσουμε το στοιχείο του πίνακα $A'_{p-1,q}$ επιλέγοντας τη γωνία περιστροφής $\theta$ ώστε να ικανοποιεί την εξίσωση

$A_{p-1,p}\sin \theta +A_{p-1,q}\cos \theta =0\;,$

Τώρα, η ακολουθία τέτοιων περιστροφών Ιακομπί με την ακόλουθη $(p,q)$

$(p,q)=(2,3),(2,4),\dots ,(2,n),(3,4),\dots ,(3,n),\dots ,(n-1,n)$

ανάγει τον πίνακα $A$ στην κατώτερη μορφή Χάιζενμπεργκ.

Ιδιότητες

Για $n\in \{1,2\}$, είναι κενή αλήθεια ότι κάθε $n\times n$ πίνακας είναι τόσο ανώτερος Χάιζενμπεργκ, όσο και κατώτερος Χάιζενμπεργκ.

Το γινόμενο ενός πίνακα Χάιζενμπεργκ με έναν τριγωνικό πίνακα είναι και πάλι Χάιζενμπεργκ. Πιο συγκεκριμένα, αν ο $A$ είναι άνω Χάιζενμπεργκ και ο $T$ είναι άνω τριγωνικός, τότε οι $AT$ και $TA$ είναι άνω Χάιζενμπεργκ.

Ένας πίνακας που είναι τόσο ανώτερος όσο και κατώτερος Χάιζενμπεργκ είναι ένας τριδιαγώνιος πίνακας, του οποίου ο πίνακας Ιακομπί είναι ένα σημαντικό παράδειγμα. Αυτό περιλαμβάνει τους συμμετρικούς ή ερμητικούς πίνακες Χάιζενμπεργκ. Ένας ερμιτιανός πίνακας μπορεί να αναχθεί σε τριδιαγώνιους πραγματικούς συμμετρικούς πίνακες.

Ο τελεστής Χάιζενμπεργκ

Ο τελεστής Χάιζενμπεργκ είναι ένας άπειρης διάστασης πίνακας Χάιζενμπεργκ. Συνήθως εμφανίζεται ως η γενίκευση του τελεστή Ιακομπί σε ένα σύστημα ορθογώνιων πολυωνύμων για τον χώρο των τετραγωνικά ολοκληρώσιμων ολομορφικών συναρτήσεων πάνω σε κάποιο πεδίο - δηλαδή, έναν χώρο Μπέργκμαν. Στην περίπτωση αυτή, ο τελεστής Χάιζενμπεργκ είναι ο τελεστής δεξιάς μετατόπισης $S$, που δίνεται από τη σχέση

$[Sf](z)=zf(z).$

Οι ιδιοτιμές κάθε κύριου υποπίνακα του τελεστή Χάιζενμπεργκ δίνονται από το χαρακτηριστικό πολυώνυμο για τον εν λόγω υποπίνακα. Αυτά τα πολυώνυμα ονομάζονται πολυώνυμα Μπέργκμαν και παρέχουν μια ορθογώνια πολυωνυμική βάση για τον χώρο Μπέργκμαν.

Δείτε επίσης

• Field Arithmetic
• Πραγματικό προβολικό επίπεδο
• Εσωτερικό γινόμενο
• Φυσικός αριθμός
• Πίνακας (μαθηματικά)
• Τριγωνικός πίνακας
• Διάνυσμα
• Προβολή (γραμμική άλγεβρα)
• Συζυγής ανάστροφος πίνακας
• Hessenberg matrix at MathWorld.
• High performance algorithms for reduction to condensed (Hessenberg, tridiagonal, bidiagonal) form
• Algorithm overview

Εξωτερικοί σύνδεσμοι

• English - Greek Dictionary of Pure and Applied Mathematics Εθνικό Μετσόβιο Πολυτεχνείο
• Αγγλοελληνικό Λεξικό Μαθηματικής Ορολογίας - Πανεπιστήμιο Κύπρου
• Matrix Analysis
• Complex-Valued Matrix Derivatives: With Applications in Signal Processing ...
• Symmetries, Lie Algebras and Representations: A Graduate Course for Physicists
• An Introduction to Computational Physics
• Matrix Algebra: Theory, Computations and Applications in Statistics
• Matrix Computations and Semiseparable Matrices: Eigenvalue and ..., Τόμος 2
• Fundamentals of Matrix Computations

Δημοσιεύσεις

• Μαυρογιάννης, Ν. Σ. (Μαΐου 2016). «Μία εισαγωγή στους μιγαδικούς αριθμούς». Εκθέτης Φύλλα Μαθηματικής Παιδείας (16): 1-8. http://ekthetis.gr/Ekthetis016.pdf. 
• Bronshtein, I. N.· Semendyayev, K. A. (29 Ιουνίου 2013). Handbook of Mathematics. Springer Science & Business Media. ISBN 978-3-662-21982-9. 
• Gray, Lawrence F.; Flanigan, Francis J.; Kazdan, Jerry L.; Frank, David H.; Fristedt, Bert (1990), Calculus two: linear and nonlinear functions, Berlin: Springer-Verlag, σελ. 375, ISBN 0-387-97388-5, https://archive.org/details/calculustwolinea00flan/page/375 
• Sylvester, J. (1884). «Sur l'equations en matrices $px=xq$». :C. R. Acad. Sci. Paris 99 (2): 67–71, 115–116. 
• Bartels, R. H.; Stewart, G. W. (1972). «Solution of the matrix equation $AX+XB=C$». Comm. ACM 15 (9): 820–826. doi:10.1145/361573.361582. 
• Bhatia, R.; Rosenthal, P. (1997). «How and why to solve the operator equation $AX-XB=Y$ ?». Bull. London Math. Soc. 29 (1): 1–21. doi:10.1112/S0024609396001828. 
• Horn, Roger A.; Johnson, Charles R. (1985), Matrix Analysis, Cambridge University Press, ISBN 978-0-521-38632-6 .
• Stoer, Josef; Bulirsch, Roland (2002), Introduction to Numerical Analysis (3rd έκδοση), Berlin, New York: Springer-Verlag, ISBN 978-0-387-95452-3 .
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), «Section 11.6.2. Reduction to Hessenberg Form», Numerical Recipes: The Art of Scientific Computing (3rd έκδοση), New York: Cambridge University Press, ISBN 978-0-521-88068-8, http://apps.nrbook.com/empanel/index.html#pg=594 

Παραπομπές

• Janko Bračič, Kolobar aritmetičnih funkcij (Ring of arithmetical functions), (Obzornik mat, fiz. 49 (2002) 4, pp. 97–108) (MSC (2000) 11A25)
• Iwaniec and Kowalski, Analytic number theory, AMS (2004).