Antworte auf:  * Ganzzahlmatrix von Goswin
Forum:  Rätsel und Knobeleien (Knobelecke), moderiert von: viertel

[Zur Forum-Gliederung] [Wie man Fragen beantwortet] [Themenstart einblenden]

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!
Benutzername:
Passwort:
Nachricht-Icon:                   
                  
              
Nachricht:


 
 


Input assistance tools (JavaScript): [Link extern intern] [MathML?] [$$?]
[fed-area] [LaTeX-inline] [LaTeX-display] [Tikz] [hide-area][show-area] [Source code [num.]][?]
 Show Preview      Write using fedgeo formula editor or Latex.

Smilies for your message:
😃 😄 😁 🙂 🙃 😉 🤗 🤫 🤔 🙄 😴 🤒 😎 😮 😲 😂
🙁 😖 😒 😐 😡 👌 👍 👎 🤢 🤧 🥵 🥶 😵 🤯 😛 😷
Optionen: Deaktiviere HTML in dieser Nachricht
Deaktiviere MATHML in dieser Nachricht. Wenn Dein Text $-Zeichen enthält, die nicht LaTeX-Formeln begrenzen.
Deaktiviere Smilies in dieser Nachricht
Zeige die Signatur (Kann in 'Mein Profil' editiert werden.)
    [Abbrechen]
 
Beachte bitte die [Forumregeln]


Themenübersicht
Nuramon
Senior
Dabei seit: 23.01.2008
Mitteilungen: 2502
 Beitrag No.10, eingetragen 2020-11-01 21:11    [Diesen Beitrag zitieren]
\(\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\)

Goswin
Senior
Dabei seit: 18.09.2008
Mitteilungen: 1559
Herkunft: Chile, Ulm

 Beitrag No.9, eingetragen 2020-11-01 19:53    [Diesen Beitrag zitieren]

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.


ochen
Senior
Dabei seit: 09.03.2015
Mitteilungen: 3039
Herkunft: der Nähe von Schwerin

 Beitrag No.8, eingetragen 2020-10-29 19:58    [Diesen Beitrag zitieren]

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: 1559
Herkunft: Chile, Ulm

 Beitrag No.7, eingetragen 2020-10-29 19:47    [Diesen Beitrag zitieren]

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: 3039
Herkunft: der Nähe von Schwerin

 Beitrag No.6, eingetragen 2020-10-28 17:02    [Diesen Beitrag zitieren]

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: 1559
Herkunft: Chile, Ulm

 Beitrag No.5, eingetragen 2020-10-28 15:49    [Diesen Beitrag zitieren]

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


gonz
Senior
Dabei seit: 16.02.2013
Mitteilungen: 3726
Herkunft: Harz

 Beitrag No.4, eingetragen 2020-10-28 09:03    [Diesen Beitrag zitieren]

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


ochen
Senior
Dabei seit: 09.03.2015
Mitteilungen: 3039
Herkunft: der Nähe von Schwerin

 Beitrag No.3, eingetragen 2020-10-28 07:46    [Diesen Beitrag zitieren]

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.


Goswin
Senior
Dabei seit: 18.09.2008
Mitteilungen: 1559
Herkunft: Chile, Ulm

 Beitrag No.2, eingetragen 2020-10-27 21:12    [Diesen Beitrag zitieren]

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


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

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: 1559
Herkunft: Chile, Ulm

 Themenstart: 2020-10-27 20:46    [Diesen Beitrag zitieren]

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)


 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 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]