Forum:  Rätsel und Knobeleien (Knobelecke)
Thema: * Ganzzahlmatrix
Themen-Übersicht
Goswin
Senior
Dabei seit: 18.09.2008
Mitteilungen: 1563
Herkunft: Chile, Ulm
Themenstart: 2020-10-27 20:46

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)


PrinzessinEinhorn
Senior
Dabei seit: 23.01.2017
Mitteilungen: 2625
Beitrag No.1, eingetragen 2020-10-27 20:55

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.


Goswin
Senior
Dabei seit: 18.09.2008
Mitteilungen: 1563
Herkunft: Chile, Ulm
Beitrag No.2, vom Themenstarter, eingetragen 2020-10-27 21:12

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


ochen
Senior
Dabei seit: 09.03.2015
Mitteilungen: 3046
Herkunft: der Nähe von Schwerin
Beitrag No.3, eingetragen 2020-10-28 07:46

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.


gonz
Senior
Dabei seit: 16.02.2013
Mitteilungen: 3728
Herkunft: Harz
Beitrag No.4, eingetragen 2020-10-28 09:03

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


Goswin
Senior
Dabei seit: 18.09.2008
Mitteilungen: 1563
Herkunft: Chile, Ulm
Beitrag No.5, vom Themenstarter, eingetragen 2020-10-28 15:49

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


ochen
Senior
Dabei seit: 09.03.2015
Mitteilungen: 3046
Herkunft: der Nähe von Schwerin
Beitrag No.6, eingetragen 2020-10-28 17:02

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.


Goswin
Senior
Dabei seit: 18.09.2008
Mitteilungen: 1563
Herkunft: Chile, Ulm
Beitrag No.7, vom Themenstarter, eingetragen 2020-10-29 19:47

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?


ochen
Senior
Dabei seit: 09.03.2015
Mitteilungen: 3046
Herkunft: der Nähe von Schwerin
Beitrag No.8, eingetragen 2020-10-29 19:58

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.


Goswin
Senior
Dabei seit: 18.09.2008
Mitteilungen: 1563
Herkunft: Chile, Ulm
Beitrag No.9, vom Themenstarter, eingetragen 2020-11-01 19:53

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.


Nuramon
Senior
Dabei seit: 23.01.2008
Mitteilungen: 2506
Beitrag No.10, eingetragen 2020-11-01 21:11
\(\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\)



Dieses Forumbeitrag kommt von Matroids Matheplanet
https://https://matheplanet.de

Die URL für dieses Forum-Thema ist:
https://https://matheplanet.de/default3.html?topic=250022=6
Druckdatum: 2021-01-21 05:07