Gauss < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:05 Mi 10.11.2004 | | Autor: | beauty |
Hey!
Ich hab mal eine Frage zu dieser Aufgabe:
Also K ist ein Körper und A M(m*n,R). l ist das Minimum von m und n
Man soll zeigen, dass man höchstens m+l Einzelschritte braucht um A in Schubert Normalform zu bringen.
Es ist ja eigentlich logisch, z.B wenn ich eine (4*3) Matrix habe, dass 3 das Minimum ist und das ich 12 Schritte brauche um A in Schubert Mormalform zu bringen.
Aber wie kann ich das allgemein zeigen?
Hat jemand einen kleinen Tip?
|
|
| |
|
Grüße!
Sorry wenn ich nicht vorher antworten konnte - ich weiß, am Donnerstag war Abgabe... aber dafür auch eine vollständige Lösung:
Also, formal kann man so argumentieren: es gibt höchstens $l$ Spalten, in denen ein Pivot-Koeffizient vorkommt, denn in jeder Spalte und jeder Zeile kann immer nur ein Pivot-Koeffizient liegen.
Nur in diesen Spalten ist etwas zu tun.
Fall 1: da, wo der Pivot-Koeffizient für die Schubert-Form hin soll, steht ein Element ungleich 0.
Dann benötigt man eine Operation, um dieses Element auf 1 zu bringen und dann noch maximal $m - 1$ Operationen, um alle anderen Elemente dieser Spalte auf 0 zu bringen. Das wären insgesamt maximal $m$ Operationen.
Fall 2: Da, wo der Pivot-Koeffizient hin soll steht eine 0.
Dann tauscht man diese Zeile mit einer beliebigen Zeile darunter, in der ein Element ungleich 0 in der entsprechenden Spalte steht - das muß es geben, denn sonst gibt es in dieser Spalte nach Def. kein Pivot-Element.
Dieses bringt man auf 1 - das waren 2 Operationen.
Jetzt gibt es aber schon mindestens eine 0 in der Spalte, also sind nur noch maximal $m - 2$ Einträge übrig, die man auf 0 bringen muß.
Macht wieder in der Summe $m$ Operationen.
Also kommt man insgesamt mit $m [mm] \cdot [/mm] l$ Operationen hin - für $l$ Pivot-Spalten und $m$ pro Spalte.
Lars
|
|
|
|
