Matroids Matheplanet Forum Index
Moderiert von viertel
Matroids Matheplanet Forum Index » Rätsel und Knobeleien (Knobelecke) » * Ganzzahlmatrix
Autor
Kein bestimmter Bereich * Ganzzahlmatrix
Goswin
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.09.2008
Mitteilungen: 1755
Wohnort: Chile, Ulm
  Themenstart: 2020-10-27

Finde von Hand eine ganzzahlige \(2\times2\)-Matrix mit Einträgen \(2\le |a_{ij}|\le9\) und \(A^3=I\). Beweise (kurz und bündig), dass sie von trivialen Symmetrien abgesehen für diesen Betragsintervall einzig ist. (Lösungen bitte verdeckt)


   Profil
Dies ist eine Knobelaufgabe!
Der Themensteller hat bestimmt, dass Du Lösungen oder Beiträge zur Lösung direkt im Forum posten darfst.
Bei dieser Aufgabe kann ein öffentlicher Austausch über Lösungen, Lösungswege und Ansätze erfolgen. Hier musst Du keine private Nachricht schreiben!
PrinzessinEinhorn
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 23.01.2017
Mitteilungen: 2625
  Beitrag No.1, eingetragen 2020-10-27

Hallo, bist du dir sicher, dass in der Aufgabenstellung kein Fehler ist. Mit der angegebenen Eigenschaft sollte doch niemals die Einheitsmatrix entstehen. Wenn alle Einträge positiv sind, dann gibt es doch keine Chance jemals eine Null zu erzeugen.


   Profil
Goswin
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.09.2008
Mitteilungen: 1755
Wohnort: Chile, Ulm
  Beitrag No.2, vom Themenstarter, eingetragen 2020-10-27

\quoteon(2020-10-27 20:55 - PrinzessinEinhorn in Beitrag No. 1) Mit der angegebenen Eigenschaft sollte doch niemals die Einheitsmatrix entstehen. \quoteoff Danke, hatte den Betrag vergessen, gemeint ist \(2\le|a_{ij}|\le9\).


   Profil
ochen
Senior Letzter Besuch: im letzten Quartal
Dabei seit: 09.03.2015
Mitteilungen: 3421
Wohnort: der Nähe von Schwerin
  Beitrag No.3, eingetragen 2020-10-28

Hallo, die Aufgabe ist sehr schön. Kommt sie aus einem Problem, mit dem du dich beschäftigst? \showon Lösungsvorschlag Habe $A\in\mathbb Z^2$ die Eigenschaften aus der Aufgabe, so ist $A$ diagonalisierbar und ihre Eigenwerte $x$ sind Nullstellen des Polynoms $x^3-1$. Da dieses Polynom nur die reelle Nullstelle 1 hat, müsste dies entweder der doppelte Eigenwert sein oder sie müsste nur nicht-reelle Eigenwerte haben. Wenn 1 der doppelte Eigenwert ist, folgt mit der Diagonalisierbarkeit bereits, dass $A$ die Einheitsmatrix ist. Dies widerspricht aber unseren Eigenschaften. Also hat $x$ nur nicht reelle Eigenwerte. Das charakteristische Polynom ist entsprechend $x^2+x+1$. Es lässt sich leicht einsehen, dass alle Matrizen mit diesem charakteristischen Polynom die Gleichung $A^3=I$ erfüllen. Somit folgt \[ \mathrm{tr}(A)=-1,\quad \det(A)=1. \] Seien $a,d$ die Diagonaleinträge und $b,c$ die Nicht-Diagonaleinträge, so folgt mit der Spur $d=-a-1$ und mit der Determinante \[ bc=ad-1=a(-a-1)-1=-(a^2+a+1) \] Durch händisches Ausprobieren ("sorry") bekommen wir für $a=4$ auf der linken Seite $-21$, was zu $(b,c)\in\{(-3,7),(3,-7),(-7,3),(7,-3)\}$ führt. Eine Lösung ist also \[ A= \begin{bmatrix} 4 & -3\\ 7 & -5 \end{bmatrix} \] Die Diagonaleinträge dürfen vertauscht werden, die Nicht-Diagonaleinträge dürfen vertauscht werden, auf der Diagonalen dürfen die Vorzeichen getauscht werden, auf der Nicht-Diagonalen dürfen die Vorzeichen getauscht werden. Ohne Ausprobieren hätte es nicht geklappt. Wir konnten aber o.B.d.A. annehmen, dass $a>0$ ist und mussten somit auch "nur" den Ausdruck $a^2+a+1$ für $a\in\{2,3,4,5,6,7,8,9\}$ ausrechnen. Das ist noch händisch machbar. \showoff


   Profil
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 4280
Wohnort: Harz
  Beitrag No.4, eingetragen 2020-10-28

Schöne Aufgabe! Mit etwas weniger Ideen und mehr platt durchgerechnet, findet man die Lösung auch so (Ausmultiplizieren mit Papier und Bleistift, der Rest "im Kopf"), nur ein paar Schritte skizziert: \showon Ich benenne die Felder in der Matrix als \ A = (a,b;c,d) Durch Ausmultiplizieren kommt man auf vier Gleichungen, in denen die Variablen b und c immer nur als Produkt vorkommen, und ich setze entsprechend \lamda = bc. Umformen der "ersten Gleichung" ergibt dann: a^3 - 1 = \lambda*(a2+d) Sicher kein Zufall, dass einem Teile der Gleichungen von der Struktur her hier mit denen von ochen bekannt vorkommen :) Es sind damit a und \lamda (also b und c) teilerfremd, und genauso a und d. Damit lässt sich der "Lösungsraum" schon etwas einschränken. a^3-1 muss außerdem in Faktoren zerfallen, die sich in der Form der rechten Seite darstellen lassen. Nun kommt auch ein bisschen durchprobieren, oBdA sei a>0 und damit: a=2 => a^3-1=7 besitzt nicht genug Faktoren a=3 => a^3-1=26 Die Faktoren 2*13 passen nicht zur rechten Seite, a=4 => a^3-1=63 Here we go. Es ist also entweder bc=9 und 2a-d=7, was nicht sein kann wegen 2a=8. Stattdessen also bc=21 und 2a+d=3, damit d=-5 a=5 => a^3-1=124 beinhaltet den nicht darstellbaren Faktor 31 a=6 => a^3-1=215 beinhaltet Faktor 43 a=7 => a^3-1=342 und Faktor 19, das würde zu bc=18 und lambda=19 führen, damit d=5 a=8 => a^3-1=511 mit Primfaktor 73 a=9 => a^3-1=728 mit einzig passender Zerlegung \lambda=8*7 und 2a+d=13, damit d=-5 Von den drei verbliebenen Fällen können die für a=7 und a=9 durch die restlichen Gleichungen ausgeschlossen werden (dies wieder heute morgen auf dem Papier). Damit - kommen wir zu der aus ochens Post bekannten Lösung. \showoff ochen war also nicht nur schneller, die Lösung ist auch wesentlich eleganter. Grüße aus dem Harz und einen schönen Mittwoch Gerhard/Gonz


   Profil
Goswin
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.09.2008
Mitteilungen: 1755
Wohnort: Chile, Ulm
  Beitrag No.5, vom Themenstarter, eingetragen 2020-10-28

\quoteon(2020-10-28 07:46 - ochen in Beitrag No. 3) Die Aufgabe ist sehr schön. Kommt sie aus einem Problem, mit dem du dich beschäftigst? \quoteoff In der Tat, und zwar aus der linearen Optimierung. Beim Testen von Pivotverfahren sind mir diese Matrizen nützlich, um Strategien zu verwerfen die unter Umständen in eine Endlosschleife geraten. Die Einschränkung \(|a_{ij}|\le9\) ist für mich irrelevant; ich habe sie nur hier hinzugefügt, damit die Lösung einzig ist. Übrigens: Deine Lösung ist prima, aber deine Aufzählung der Symmetrien enthält einen Fehler, der für dich ziemlich offenbar sein sollte! ;-)


   Profil
ochen
Senior Letzter Besuch: im letzten Quartal
Dabei seit: 09.03.2015
Mitteilungen: 3421
Wohnort: der Nähe von Schwerin
  Beitrag No.6, eingetragen 2020-10-28

\quoteon(2020-10-28 15:49 - Goswin in Beitrag No. 5) Übrigens: Deine Lösung ist prima, aber deine Aufzählung der Symmetrien enthält einen Fehler, der für dich ziemlich offenbar sein sollte! ;-) \quoteoff \showon Korrektur Ja, ich darf natürlich nicht die Vorzeichen von $a$ und $d$ tauschen. Auf der Diagonalen stehen also tatsächlich die Zahlen 4 und -5. \showoff


   Profil
Goswin
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.09.2008
Mitteilungen: 1755
Wohnort: Chile, Ulm
  Beitrag No.7, vom Themenstarter, eingetragen 2020-10-29

Anmerkung: Wenn die ganzzahlige Matrix $A^3=I$ erfüllt, dann erfüllt natürlich auch $B=A^2$ die Gleichung $B^3=I$. Ich konnte diese Eigenschaft aber nicht verwerten, um $A$ zu finden. Da die bisherigen Beweise sämtliche symmetrische Lösungsmöglichkeiten aufzählen, war zu erwarten, dass $B$ nichts weiter als eine dieser Symmetrien ist, was dann auch zutrifft (sie hätte die Bedingung $2\le|b_{ij}|\le9$ verletzen können, was nicht der Fall war). Ob das wohl immer so ist? @ochen: Du sagst: "Hat \(A\in\mathbb Z^{2\times2}\) die Eigenschaften aus der Aufgabe, so ist \(A\) diagonalisierbar und ihre Eigenwerte \(x\) sind Nullstellen des Polynoms \(x^3-1\)" Warum?? Das Polynom \(x^3-1\) ist nicht das charakteristische Polynom von \(A\), schon der Grad stimmt nicht, wie kommst du dann auf Diagonalisierbarkeit und Eigenschaften der Eigenwerte?


   Profil
ochen
Senior Letzter Besuch: im letzten Quartal
Dabei seit: 09.03.2015
Mitteilungen: 3421
Wohnort: der Nähe von Schwerin
  Beitrag No.8, eingetragen 2020-10-29

\quoteon(2020-10-29 19:47 - Goswin in Beitrag No. 7) @ochen: Du sagst: "Hat \(A\in\mathbb Z^{2\times2}\) die Eigenschaften aus der Aufgabe, so ist \(A\) diagonalisierbar und ihre Eigenwerte \(x\) sind Nullstellen des Polynoms \(x^3-1\)" Warum?? Das Polynom \(x^3-1\) ist nicht das charakteristische Polynom von \(A\), schon der Grad stimmt nicht, wie kommst du dann auf Diagonalisierbarkeit und Eigenschaften der Eigenwerte? \quoteoff \showon Antwort Das stimmt, so ausführlich habe ich es nicht geschrieben. Für jeden Eigenwert $x$ und den dazugehörigen Eigenvektor $v$ muss \[ v=A^3v=A^2(Av)=A^2(xv)=x\,A^2v=\cdots=x^3 v \] gelten. Da $v\neq 0$ wenigstens einen von Null verschiedenen Eintrag $v_i$ hat, muss $v_i=x^3v_i$ oder eben $x^3-1=0$ gelten. Dies gilt für jeden Eigenwert $x$ von $A$. Desweiteren muss $A$ diagonalisierbar sein, weil $A^3=I\neq 0$ diagonalisierbar ist. Wäre $A$ nicht diagonalisierbar, hätte $A=SJS^{-1}$ einen doppelten Eigenwert $x$ (mit $x^3=1$) und es gelte \[ \begin{bmatrix}1 & 3x^2 \\ 0 & 1\end{bmatrix}=\begin{bmatrix}x & 1 \\ 0 & x\end{bmatrix}^3=J^3=S^{-1}A^3S=I, \] was für $x\neq 0$ offenbar falsch ist. Jetzt habe ich hoffentlich nichts vergessen. \showoff


   Profil
Goswin
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.09.2008
Mitteilungen: 1755
Wohnort: Chile, Ulm
  Beitrag No.9, vom Themenstarter, eingetragen 2020-11-01

Ich habe gerade (hoffentlich korrekt) bewiesen, dass \[ A\in\mathbb{Z}^{2\times2},\quad A^4=I \quad\Longrightarrow\quad A^2\in\{I,-I\} \] was ich auch ganz interessant finde. Und anscheinend sind Matrizen mit \[ A\in\mathbb{Z}^{2\times2}\setminus\{I\},\quad A^k=I,\quad k~\text{prim} \] nur für sehr wenige \(k>3\) (wenn überhaupt) vorhanden.


   Profil
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 3613
  Beitrag No.10, eingetragen 2020-11-01

\(\begingroup\)\(\newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}} \newcommand{\rg}{\operatorname{rg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\tr}{\operatorname{tr}}\) \quoteon(2020-11-01 19:53 - Goswin in Beitrag No. 9) Ich habe gerade (hoffentlich korrekt) bewiesen, dass \[ A\in\mathbb{Z}^{2\times2},\quad A^4=I \quad\Longrightarrow\quad A^2\in\{I,-I\} \] was ich auch ganz interessant finde. \quoteoff Das ist falsch: Betrachte z.B. die Matrix zur Permutation $1\mapsto 2, 2\mapsto 1$. Sollte stimmen, habe nur zu ungenau gelesen. \quoteon Und anscheinend sind Matrizen mit \[ A\in\mathbb{Z}^{2\times2}\setminus\{I\},\quad A^k=I,\quad k~\text{prim} \] nur für sehr wenige \(k>3\) (wenn überhaupt) vorhanden. \quoteoff Sei $A$ eine ganzzahlige $2\times 2$-Matrix mit $A^k=I$, wobei $k\in \IN$ beliebig. Falls $A$ nur reelle Eigenwerte hat, dann muss $A$ ähnlich sein zu einer der folgenden Matrizen: \[I, -I, \begin{pmatrix}1&0\\ 0&-1\end{pmatrix}, \begin{pmatrix}1&1\\ 0&1\end{pmatrix}, -\begin{pmatrix}1&1\\ 0&1\end{pmatrix}\] Die letzten beiden Matrizen scheiden aus, weil keine ihrer Potenzen die Einheitsmatrix ist. Matrizen mit Eigenwert $-1$ sind nur für gerades $k$ möglich. Falls $A$ einen echt komplexen Eigenwert $x$ hat, dann muss auch $\overline x$ ein Eigenwert von $A$ sein. Insbesondere ist dann $A$ diagonalisierbar, $\tr A= 2\operatorname{Re} x $ und $\det A = x\overline x =1$. Außerdem ist $x$ eine $k$-te Einheitswurzel und daher $-1\leq \operatorname{Re} x \leq 1$. Das charakteristische Polynom von $A$ hat also die Form $x^2-sx +1$, wobei $-2\leq s \leq 2$. Jeder dieser Werte für $s$ ist prinzipiell möglich: Für $s=\pm 2$ folgt $A=\pm I$. Für $s=-1$ sind die Eigenwerte von $A$ die primitiven dritten Einheitswurzeln $\omega, \overline \omega$. Für $s=1$ sind die Eigenwerte von $A$ die primitiven sechsten Einheitswurzeln. Für $s=0$ sind $\pm i$ die Eigenwerte von $A$. Zusammenfassend bleiben also folgende Möglichkeiten für $A$: - immer: $A=I$ zusätzlich noch: - für gerades $k$: $A=-I$ und alle ganzzahligen Matrizen mit Spur $0$ und Determinante $-1$ (letzteres sind genau die ganzzahligen Matrizen, die zu $\begin{pmatrix}1&0\\ 0&-1\end{pmatrix}$ ähnlich sind) - für durch drei teilbares $k$: alle ganzzahligen Matrizen mit Determinante $1$ und Spur $-1$. - für durch vier teilbares $k$: alle ganzzahligen Matrizen mit Determinante $1$ und Spur $0$. - für durch sechs teilbares $k$: alle ganzzahligen Matrizen mit Determinante $1$ und Spur $1$. Die ganzzahligen Matrizen mit fester Determinante $d\in \IZ$ und Spur $s\in \IZ$ sind genau die Matrizen $$ \begin{pmatrix} a& b \\ c & s-a \end{pmatrix},$$ wobei $a\in \IZ$ beliebig ist, und $b,c\in \IZ$ beliebige zu einander komplementäre Teiler von $a(s-a)-d$ sind (also $bc= a(s-a)-d$ gilt). Für primes $k>3$ gibt es also tatsächlich nur den trivialen Fall $A=I$.\(\endgroup\)


   Profil
Goswin hat die Antworten auf ihre/seine Frage gesehen.
Dies ist eine Knobelaufgabe!
Der Themensteller hat bestimmt, dass Du Lösungen oder Beiträge zur Lösung direkt im Forum posten darfst.
Bei dieser Aufgabe kann ein öffentlicher Austausch über Lösungen, Lösungswege und Ansätze erfolgen. Hier musst Du keine private Nachricht schreiben!

Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2022 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]