Matroids Matheplanet Forum Index
Forumbereich moderiert von: viertel
Alle Foren » Rätsel und Knobeleien (Knobelecke) » * Ganzzahlmatrix
Druckversion
Druckversion
Antworten
Antworten
Kein bestimmter Bereich * Ganzzahlmatrix
Goswin Senior Letzter Besuch: in der letzten Woche
Mitglied seit: 18.09.2008, Mitteilungen: 1527, aus: Chile, Ulm
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
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)


-----------------
/Kyristo meu kimgei kom nhi cumgen ta Gendmogen.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
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: in der letzten Woche
Mitglied seit: 23.01.2017, Mitteilungen: 2619
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
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.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Goswin Senior Letzter Besuch: in der letzten Woche
Mitglied seit: 18.09.2008, Mitteilungen: 1527, aus: Chile, Ulm
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.2, vom Themenstarter, eingetragen 2020-10-27

2020-10-27 20:55 - PrinzessinEinhorn in Beitrag No. 1 schreibt:
Mit der angegebenen Eigenschaft sollte doch niemals die Einheitsmatrix entstehen.

Danke, hatte den Betrag vergessen, gemeint ist  \(2\le|a_{ij}|\le9\).



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
ochen Senior Letzter Besuch: in der letzten Woche
Mitglied seit: 09.03.2015, Mitteilungen: 2991, aus: der Nähe von Schwerin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
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?

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.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
gonz Senior Letzter Besuch: in der letzten Woche
Mitglied seit: 16.02.2013, Mitteilungen: 3685, aus: Harz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
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:


Ich benenne die Felder in der Matrix als
fed-Code einblenden

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



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Goswin Senior Letzter Besuch: in der letzten Woche
Mitglied seit: 18.09.2008, Mitteilungen: 1527, aus: Chile, Ulm
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.5, vom Themenstarter, eingetragen 2020-10-28

2020-10-28 07:46 - ochen in Beitrag No. 3 schreibt:
Die Aufgabe ist sehr schön. Kommt sie aus einem Problem, mit dem du dich beschäftigst?

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! ;-)



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
ochen Senior Letzter Besuch: in der letzten Woche
Mitglied seit: 09.03.2015, Mitteilungen: 2991, aus: der Nähe von Schwerin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.6, eingetragen 2020-10-28

2020-10-28 15:49 - Goswin in Beitrag No. 5 schreibt:
Übrigens: Deine Lösung ist prima, aber deine Aufzählung der Symmetrien enthält einen Fehler, der für dich ziemlich offenbar sein sollte! ;-)

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.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Goswin Senior Letzter Besuch: in der letzten Woche
Mitglied seit: 18.09.2008, Mitteilungen: 1527, aus: Chile, Ulm
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.7, vom Themenstarter, eingetragen 2020-10-29

Anmerkung:
Wenn die ganzzahlige Matrix <math>A^3=I</math> erfüllt, dann erfüllt natürlich auch <math>B=A^2</math> die Gleichung <math>B^3=I</math>. Ich konnte diese Eigenschaft aber nicht verwerten, um <math>A</math> zu finden. Da die bisherigen Beweise sämtliche symmetrische Lösungsmöglichkeiten aufzählen, war zu erwarten, dass <math>B</math> nichts weiter als eine dieser Symmetrien ist, was dann auch zutrifft (sie hätte die Bedingung <math>2\le|b_{ij}|\le9</math> 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?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
ochen Senior Letzter Besuch: in der letzten Woche
Mitglied seit: 09.03.2015, Mitteilungen: 2991, aus: der Nähe von Schwerin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.8, eingetragen 2020-10-29

2020-10-29 19:47 - Goswin in Beitrag No. 7 schreibt:
@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?

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.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Goswin Senior Letzter Besuch: in der letzten Woche
Mitglied seit: 18.09.2008, Mitteilungen: 1527, aus: Chile, Ulm
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
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.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Nuramon Senior Letzter Besuch: in der letzten Woche
Mitglied seit: 23.01.2008, Mitteilungen: 2415
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
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}}\)
2020-11-01 19:53 - Goswin in Beitrag No. 9 schreibt:
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.
Das ist falsch: Betrachte z.B. die Matrix zur Permutation $1\mapsto 2, 2\mapsto 1$.
Sollte stimmen, habe nur zu ungenau gelesen.

 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.
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\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
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!
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


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-2020 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]