matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenLineare Algebra - Matrizenquadr. Matrix ^n Beweis
Foren für weitere Studienfächer findest Du auf www.vorhilfe.de z.B. Astronomie • Medizin • Elektrotechnik • Maschinenbau • Bauingenieurwesen • Jura • Psychologie • Geowissenschaften
Forum "Lineare Algebra - Matrizen" - quadr. Matrix ^n Beweis
quadr. Matrix ^n Beweis < Matrizen < Lineare Algebra < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Lineare Algebra - Matrizen"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

quadr. Matrix ^n Beweis: Tipp
Status: (Frage) beantwortet Status 
Datum: 16:48 Sa 05.12.2015
Autor: Ulquiorra

Aufgabe
Berechne für n [mm] \in \IN [/mm]

[mm] \pmat{ 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1 }^{n} [/mm]

Hallo MatheRaum Community,
ich hab mich dran versucht diese Aufgabe mittels vollst. Induktion zu lösen/beweisen, aber komme beim Ind.-Schluss nicht mehr weiter.

Also mittels einigem Ausprobieren habe ich diese(s) "Muster"/Regel erkannt.

[mm] \pmat{ 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1}^{n} [/mm] = [mm] \pmat{ 1 & n & n+c_{1(n-1)} \\ 0 & 1 & n \\ 0 & 0 & 1} [/mm]

das Element [mm] c_{1(n-1)} [/mm] wäre dann das Element was für n-1 an dieser Stelle stehen würde.

Also nun zur Induktion:

Induktions-Anfang : für n = 1
[mm] \pmat{ 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1}^{1} [/mm] = [mm] \pmat{ 1 & 1 & 1+c_{1(n-1)} \\ 0 & 1 & 1 \\ 0 & 0 & 1} [/mm]

und das [mm] c_{1(n-1)} [/mm] wäre bei n=1, das Element was bei n=0, also: [mm] \pmat{ 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1}^{0} [/mm] an dieser Stelle stehen würde, was 0 wäre.

Also:
[mm] \pmat{ 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1}^{1} [/mm] = [mm] \pmat{ 1 & 1 & 1+0 \\ 0 & 1 & 1 \\ 0 & 0 & 1} [/mm]

Hierbei bitte ich auch kurz um eine Erklärung warum da 0 stehen müsste für [mm] c_{1(n-1)} [/mm] . Im Internet habe ich ein bisschen recherchiert und die Cayley Hamilton Regel müsste das irgendwie erklären können, da diese Matrix quadratisch ist, aber mehr habe ich nicht verstehen können, da dies die 1. Woche mit Matrizenrechnung bei mir ist.

Induktions-Vorausetzung :

[mm] \pmat{ 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1}^{n} [/mm] = [mm] \pmat{ 1 & n & n+c_{1(n-1)} \\ 0 & 1 & n \\ 0 & 0 & 1} [/mm]

Induktions-Behauptung :

[mm] \pmat{ 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1}^{n+1} [/mm] = [mm] \pmat{ 1 & n+1 & n+1+n+c_{1(n-1)} \\ 0 & 1 & n+1 \\ 0 & 0 & 1} [/mm]

Induktions-Schluss :
[mm] \pmat{ 1 & n+1 & n+1+n+c_{1(n-1)} \\ 0 & 1 & n+1 \\ 0 & 0 & 1} [/mm]  = [mm] \pmat{ 1 & n & n+c_{1(n-1)} \\ 0 & 1 & n \\ 0 & 0 & 1} [/mm]  + [mm] \pmat{ 0 & 1 & n+1 \\ 0 & 0 & 1 \\ 0 & 0 & 0} [/mm]

Der erste Teil wäre ja die Induktions-Voraussetzung aber wie genau kann ich denn jetzt zeigen, dass es das selbe ist?

Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.

Ich danke schonmal im Voraus.

Mit freundlichen Grüßen,
Cifer

        
Bezug
quadr. Matrix ^n Beweis: Antwort
Status: (Antwort) fertig Status 
Datum: 17:41 Sa 05.12.2015
Autor: hippias


> Berechne für n [mm]\in \IN[/mm]
>  
> [mm]\pmat{ 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1 }^{n}[/mm]
>  Hallo
> MatheRaum Community,
>  ich hab mich dran versucht diese Aufgabe mittels vollst.
> Induktion zu lösen/beweisen, aber komme beim Ind.-Schluss
> nicht mehr weiter.
>  
> Also mittels einigem Ausprobieren habe ich diese(s)
> "Muster"/Regel erkannt.
>  
> [mm]\pmat{ 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1}^{n}[/mm] = [mm]\pmat{ 1 & n & n+c_{1(n-1)} \\ 0 & 1 & n \\ 0 & 0 & 1}[/mm]
>  
> das Element [mm]c_{1(n-1)}[/mm] wäre dann das Element was für n-1
> an dieser Stelle stehen würde.
>
> Also nun zur Induktion:
>  
> Induktions-Anfang : für n = 1
>  [mm]\pmat{ 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1}^{1}[/mm] = [mm]\pmat{ 1 & 1 & 1+c_{1(n-1)} \\ 0 & 1 & 1 \\ 0 & 0 & 1}[/mm]
>
> und das [mm]c_{1(n-1)}[/mm] wäre bei n=1, das Element was bei n=0,
> also: [mm]\pmat{ 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1}^{0}[/mm] an
> dieser Stelle stehen würde, was 0 wäre.
>  
> Also:
> [mm]\pmat{ 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1}^{1}[/mm] = [mm]\pmat{ 1 & 1 & 1+0 \\ 0 & 1 & 1 \\ 0 & 0 & 1}[/mm]
>
> Hierbei bitte ich auch kurz um eine Erklärung warum da 0
> stehen müsste für [mm]c_{1(n-1)}[/mm] .

Ich bin mir nicht sicher, ob ich Deine Frage richtig verstehe. Meine Antwort ist, dass eine Matrix hoch $0$ nach Definition die Einheitsmatrix ist. Daher ist der betreffende Matrixeintrag $=0$.

> Im Internet habe ich ein
> bisschen recherchiert und die Cayley Hamilton Regel müsste
> das irgendwie erklären können, da diese Matrix
> quadratisch ist, aber mehr habe ich nicht verstehen
> können, da dies die 1. Woche mit Matrizenrechnung bei mir
> ist.
>  
> Induktions-Vorausetzung :
>  
> [mm]\pmat{ 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1}^{n}[/mm] = [mm]\pmat{ 1 & n & n+c_{1(n-1)} \\ 0 & 1 & n \\ 0 & 0 & 1}[/mm]
>
> Induktions-Behauptung :
>  
> [mm]\pmat{ 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1}^{n+1}[/mm] = [mm]\pmat{ 1 & n+1 & n+1+n+c_{1(n-1)} \\ 0 & 1 & n+1 \\ 0 & 0 & 1}[/mm]
>

Nein, oben rechts müsste, in Deiner etwas wunderlichen Notation, [mm] $n+1+c_{1n}$ [/mm] stehen, da Du den Vorgängerfall zu $n+1$ benötigst.

> Induktions-Schluss :
>  [mm]\pmat{ 1 & n+1 & n+1+n+c_{1(n-1)} \\ 0 & 1 & n+1 \\ 0 & 0 & 1}[/mm]
>  = [mm]\pmat{ 1 & n & n+c_{1(n-1)} \\ 0 & 1 & n \\ 0 & 0 & 1}[/mm]  
> + [mm]\pmat{ 0 & 1 & n+1 \\ 0 & 0 & 1 \\ 0 & 0 & 0}[/mm]
>

Nein, rechne so: [mm] $\pmat{1 & 1 & 1\\ 0&1&1\\ 0&0&1}^{n+1}= \pmat{1 & 1 & 1\\ 0&1&1\\ 0&0&1}^{n}\pmat{1 & 1 & 1\\ 0&1&1\\ 0&0&1}$. [/mm] Nach Induktionsvoraussetzung ist [mm] $\pmat{1 & 1 & 1\\ 0&1&1\\ 0&0&1}^{n}= \pmat{1 & n & n+c_{1(n-1)}\\ 0&1&n\\ 0&0&1}$. [/mm]

Also ist [mm] $\pmat{1 & 1 & 1\\ 0&1&1\\ 0&0&1}^{n+1}= \pmat{1 & n &n+ c_{1(n-1)}\\ 0&1&n\\ 0&0& 1}\pmat{1 & 1 & 1\\ 0&1&1\\ 0&0&1}$. [/mm] Nun berechne das Matrixprodukt auf der rechten Seite, insbesondere den Eintrag in der rechten oberen Ecke und überprüfe, ob er die richtige Gestalt hat.

Ich würde versuchen einen expliziten Ausdruck für das [mm] $c_{1n}$ [/mm] zu finden (Tip: Arithmetische Reihe).

> Der erste Teil wäre ja die Induktions-Voraussetzung aber
> wie genau kann ich denn jetzt zeigen, dass es das selbe
> ist?
>  
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt.
>  
> Ich danke schonmal im Voraus.
>  
> Mit freundlichen Grüßen,
>  Cifer


Bezug
                
Bezug
quadr. Matrix ^n Beweis: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 21:59 Sa 05.12.2015
Autor: Ulquiorra

Erst einmal vielen Dank für die Hilfe und den hilfreichen Tipp mit der arithmetischen Reihe. Perfekt dezenter Tipp kann ich nur sagen.

Also ich hab das nochmal versucht in dem ich für [mm] c_{1(n-1)} [/mm] die Gaußsche Summenformel eingesetzt habe also [mm] \bruch{n(n+1)}{2} [/mm] und dann würde mein Induktionsbeweis so aussehen:

Induktionsanfang: für n=1

[mm] \pmat{ 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1}^{1} [/mm] = [mm] \pmat{ 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1} [/mm]

Induktionsvoraussetzung:

[mm] \pmat{ 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1}^{n} [/mm] = [mm] \pmat{ 1 & n & \bruch{n(n+1)}{2} \\ 0 & 1 & n \\ 0 & 0 & 1} [/mm]

Induktionsbehauptung:

[mm] \pmat{ 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1}^{n+1} [/mm] = [mm] \pmat{ 1 & n+1 & \bruch{(n+1)(n+2)}{2} \\ 0 & 1 & n+1 \\ 0 & 0 & 1} [/mm]

Induktionsschluss:

[mm] \pmat{ 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1}^{n+1} [/mm] = [mm] \pmat{ 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1}^{n} [/mm] * [mm] \pmat{ 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1} [/mm] = [mm] \pmat{ 1 & n & \bruch{n(n+1)}{2} \\ 0 & 1 & n \\ 0 & 0 & 1} [/mm]  * [mm] \pmat{ 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1} [/mm] = [mm] \pmat{ 1 & n+1 & \bruch{(n+1)(n+2)}{2} \\ 0 & 1 & n+1 \\ 0 & 0 & 1} [/mm]

Nebenrechnung zum Induktionsschluss:

n+1+ [mm] \bruch{n(n+1)}{2} [/mm] = [mm] \bruch{2n}{2} [/mm] + [mm] \bruch{2}{2} [/mm] + [mm] \bruch{n(n+1)}{2} [/mm] = [mm] \bruch{2n+2+n^2+n}{2} [/mm] = [mm] \bruch{3n+n^2+2}{2} [/mm] = [mm] \bruch{(n+1)(n+2)}{2} [/mm]

Eine Frage hätte ich noch und zwar bei dem Schritt wo ich [mm] 3n+n^2+2 [/mm] = (n+1)(n+2) gesetzt habe: Also diesmal habe ich das halt erkannt weil ich mir schon früher aufgeschrieben hatte, dass (n+1)(n+2) im Zähler stehen muss und ich es mal einfach so ausgeklammert hatte um zu gucken was dabei rauskommt. Ich wusste also schon im voraus, dass irgendwie entweder [mm] 3n+n^2+2 [/mm] oder (n+1)(n+2) im Zähler stehen muss, aber gibt es da irgendwie einen Trick sowas zu erkennen. Der erste Gedanke war bei mir nämlich als ich [mm] 3n+n^2+2 [/mm] rausbekommen hatte im Zähler, dass ich mich vielleicht irgendwo vertan habe, weil ich nicht (n+1)(n+2) rausbekommen habe und erst beim Überlegen mein Blick über das Blatt schweifte und ich sah, dass (n+1)(n+2) = [mm] 3n+n^2+2 [/mm] ist. Hätte ich das irgendwie früher erkennen können? Eine binomische Formel ist das ja nicht wirklich und wenn ich versuche n auszuklammern kommt bei mir ja n(n+3)+2 raus, welches auf den ersten Blick auch nicht so aussieht wie (n+1)(n+2).

Und dann natürlich noch die Frage ob der Beweis nun beendet ist oder ob da noch was fehlt.

Vielen Dank noch einmal.

Mit freundlichen Grüßen,
Baran Calisci

Bezug
                        
Bezug
quadr. Matrix ^n Beweis: Antwort
Status: (Antwort) fertig Status 
Datum: 10:49 So 06.12.2015
Autor: hippias

Ich finde Dein Beweis sieht gut so aus. Zu Deiner Frage: Ich schätze, jeder findet es nicht leicht die Gleichheit der Terme zu erkennen; insbesondere, wenn mehr als $2$ Faktoren involviert sind. Da hilft nur Klammern auszumultiplizieren, um zu sehen, ob die Terme gleich oder ungleich sind.
Ich möchte aber an den Satz von Vieta erinnern, der einem z.B. bei $2$ Faktoren schnell erkennen lässt wie die Faktoren vor den Potenzen aussehen.

Richie1401s Idee mit der binomischen Formel ist natürlich sehr elegant. Wenn ich keine Fehler oder unnötig sehr viel Mehraufwand sehe, dann halte ich mich mit Alternativbeweisen meist zurück, damit der Lernende seine eigenen Ideen entwickeln kann.



Bezug
                        
Bezug
quadr. Matrix ^n Beweis: Antwort
Status: (Antwort) fertig Status 
Datum: 12:26 So 06.12.2015
Autor: DieAcht

Hallo Ulquiorra!


[willkommenmr]


> Eine Frage hätte ich noch und zwar bei dem Schritt wo ich
> [mm]3n+n^2+2[/mm] = (n+1)(n+2) gesetzt habe: Also diesmal habe ich
> das halt erkannt weil ich mir schon früher aufgeschrieben
> hatte, dass (n+1)(n+2) im Zähler stehen muss und ich es
> mal einfach so ausgeklammert hatte um zu gucken was dabei
> rauskommt. Ich wusste also schon im voraus, dass irgendwie
> entweder [mm]3n+n^2+2[/mm] oder (n+1)(n+2) im Zähler stehen muss,
> aber gibt es da irgendwie einen Trick sowas zu erkennen.

Das Aufschreiben der Induktionsbehauptung ist bereits ein "Trick", weil man damit das "Ziel" im Blick behält.

> Der erste Gedanke war bei mir nämlich als ich [mm]3n+n^2+2[/mm]
> rausbekommen hatte im Zähler, dass ich mich vielleicht
> irgendwo vertan habe, weil ich nicht (n+1)(n+2)
> rausbekommen habe und erst beim Überlegen mein Blick über
> das Blatt schweifte und ich sah, dass (n+1)(n+2) = [mm]3n+n^2+2[/mm]
> ist. Hätte ich das irgendwie früher erkennen können?
> Eine binomische Formel ist das ja nicht wirklich und wenn
> ich versuche n auszuklammern kommt bei mir ja n(n+3)+2
> raus, welches auf den ersten Blick auch nicht so aussieht
> wie (n+1)(n+2).

In der Regel ist bei solchen Aufgaben das Ausmultiplizieren das falsche Mittel.

Es gilt

      [mm] $n+1+\frac{n*(n+1)}{2}=\frac{2*(n+1)}{2}+\frac{n*(n+1)}{2}=\frac{2*(n+1)+n*(n+1)}{2}=\frac{(n+1)(n+2)}{2}$. [/mm]


Gruß
DieAcht

Bezug
        
Bezug
quadr. Matrix ^n Beweis: Antwort
Status: (Antwort) fertig Status 
Datum: 18:38 Sa 05.12.2015
Autor: Richie1401

Hallo,

es geht auch einfacher:
Ich nehme an, dass ihr den Binomischen Lehrsatz hattet, sodass ihr ihn verwenden dürft.

Zerlege deine Matrix wie folgt

   [mm] \pmat{ 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1 }=\pmat{ 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 }+\pmat{ 0 & 1 & 1 \\ 0 & 0 & 1 \\ 0 & 0 & 0 }=E_3+B [/mm]

Nutze nun den Binomischen Lehrsatz (das ist möglich da die Identische Matrix natürlich mit der Matrix B kommutiert):

   [mm] (E_3+B)^n=\sum_{k=0}^n\binom{n}{k}{E_3}^{n-k}B^k=\sum_{k=0}^{2}\binom{n}{k}B^k [/mm]

Die Summe geht natürlich nur bis n=2, da [mm] B^3=0. [/mm]

Die "Arbeit" liegt jetzt nur noch darin, die Binomialkoeffizienten zu berechnen und die drei Matrizen (wobei sicherlich bekannt ist, welche Gestalt [mm] B^2 [/mm] hat) aufzusummieren.

Bezug
                
Bezug
quadr. Matrix ^n Beweis: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 22:05 Sa 05.12.2015
Autor: Ulquiorra

Tut mir leid, aber ich hab gar nicht erst versucht es mit dem Binomialkoeffizienten zu lösen, da ich es mit hippias Tipp schon geschafft hatte, sonst hätte ich es so versucht, wie du es mir angeboten hattest. Trotzdem echt vielen Dank für die Hilfe und nimm es mir nicht übel, dass ich es nicht damit versucht habe.

Mit freundlichen Grüßen,
Cifer

Bezug
                        
Bezug
quadr. Matrix ^n Beweis: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 22:59 Sa 05.12.2015
Autor: Richie1401

Hallo,

ich nehme dir das überhaupt nicht übel. Ich wollte jedoch nur für andere - die vielleicht auf diese Aufgabe stoßen - einen alternativen Lösungsweg anbieten.

Zumal dieser Lösungsweg eigentlich nur ein Dreizeiler ist. Denn rechnen muss man hier eigentlich gar nicht.

Übrigens ist ja in der Tat nur ein einziger Binomialkoeffizient zu "berechnen".
Also schneller geht es glaube ich wirklich nicht.

Als Übung für die Beweistechnik der Induktion ist obige Aufgabe aber sicherlich nicht schlecht.

Es kann ja allgemein nie schaden sich mehrere Lösungen anzuschauen.

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Lineare Algebra - Matrizen"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]