Matrizen, Lineare Unabhängigkeit

Ich versuche mich gerade etwas in die Kodierungstheorie einzuarbeiten, aber jetzt bin ich leider schon relativ früh auf eine eigentlich einfache Frage gestoßen.

Sei

$H:= \begin{pmatrix} 1 & 0 & 0 &1&1 \\ 0 & 1 & 0 &1&0\\ 0&0&1&1&1 \end{pmatrix} \in Mat(3,5;\mathbb{F}_2)$

Ich möchte jetzt die Anzahl der linear unabhängigen Spalten rausfinden. Die ersten drei Spalten bilden ja eine Basis für die 5 Spaltenvektoren, daher sind sie linear unabhängig. Meine Antwort wäre jetzt 3. Aber den zweiten Vector kann ich ja durch den 4ten + 5ten darstellen, aber demnach wäre er ja nicht mehr unabhängig. Irgendwo habe ich einen gravierenden Denkfehler, aber ich finde ihn gerade nicht ....

kodierer schrieb:

Aber den zweiten Vector kann ich ja durch den 4ten + 5ten darstellen, aber demnach wäre er ja nicht mehr unabhängig.

Hier ist der Fehler. Was ist ein unabhängiger Vektor?

Das ist gerade mein Problem. Wann EIN Vektor linear unabhängig ist verstehe ich nicht ganz. Bei mehreren Vektoren muss man ja nur gucken ob man den Nullvektor durch eine Linearkombinantion darstellen kann ohne das alle Koeffizienten 0 sind.

Könnte es sein, dass die Anzahl der linear unabhängigen Spalten gleich der Anzahl der Elemente einer Basis ist?

der maximalen zahl, ja

Ich verstehe nicht ganz was die maximale/minimale Anzahl sein soll. Minimal im Bezug auf was? Die ersten 3 Vektoren waren zueinder linear unabhängig, aber wenn ich alle 5 nehme sind sie es wieder nicht. Mir fehlt irgednwie ein Hinweis. Im Endeffekt möchte ich die Minimaldistanz bestimmen.

Bashar

kodierer schrieb:

Wann EIN Vektor linear unabhängig ist verstehe ich nicht ganz.

Warum nicht? Die Definition gilt nicht nur für n ≥ 2.

Es geht hier aber gar nicht darum, ob einzelne Vektoren linear unabhängig sind, sondern darum, wieviele Vektoren maximal linear unabhängig sein können. Oder genauer: Gesucht ist \max \{ |S| \mid S \text{ ist System linear unabhängiger Spalten}\}.

kodierer schrieb:

Ich verstehe nicht ganz was die maximale/minimale Anzahl sein soll. Minimal im Bezug auf was?

Maximal. In Bezug auf die Anzahl der Elemente.

Die ersten 3 Vektoren waren zueinder linear unabhängig, aber wenn ich alle 5 nehme sind sie es wieder nicht.

Dann ist vielleicht 3 schon das Maximum, wer weiß. Oder 4. 5 jedenfalls nicht. Versuch es selbst herauszufinden (oder lies dir ein bisschen was zu linearer Algebra an...)

Bashar schrieb:

Gesucht ist \max \{ |S| \mid S \text{ ist System linear unabhängiger Spalten}\}.)

kodierer schrieb:

$H:= \begin{pmatrix} 1 & 0 & 0 &1&1 \\ 0 & 1 & 0 &1&0\\ 0&0&1&1&1 \end{pmatrix} \in Mat(3,5;\mathbb{F}_2)$

Wir haben eine 3*5 Matrix im $\mathbb{F}_2$ . Somit kann es maximal 3 linear unabhängige Spaltenvektoren geben. Da wir mit den ersten drei Spaltenvektoren ein System mit 3 Elementen gefunden haben wird die maximale Anzahl erreicht.

Da wir maximal 3 linear unabhängige Spalten haben wäre die Minimaldistanz 4.

Die Stufenform ist ja in den wenigsten Fällen gegeben. Durch "gaußen" der Kontrollmatrix wird die Lösung nicht verfälscht, oder?

Bashar

kodierer schrieb:

Wir haben eine 3*5 Matrix im $\mathbb{F}_2$ . Somit kann es maximal 3 linear unabhängige Spaltenvektoren geben.

Richtig.

Die Stufenform ist ja in den wenigsten Fällen gegeben. Durch "gaußen" der Kontrollmatrix wird die Lösung nicht verfälscht, oder?

Die Schritte des Gauss-Algorithmus sind nichts anderes als Multiplikationen mit speziellen nichtsingulären Matrizen, der Rang bleibt dabei also erhalten. Achja, der Rang einer Matrix ist die ganze Zeit der Begriff, den du suchst.

Bashar schrieb:

Die Schritte des Gauss-Algorithmus sind nichts anderes als Multiplikationen mit speziellen nichtsingulären Matrizen, der Rang bleibt dabei also erhalten. Achja, der Rang einer Matrix ist die ganze Zeit der Begriff, den du suchst.

Danke. Das war es genau. Insbesondere, dass auch Spaltenrang = Zeilenrang gilt.
An einer Stelle komme ich jetzt aber noch ins schwimmen. Sei wieder ein linerarer Code mit der Kontrollmatrix gegeben.

$H:= \begin{pmatrix} 1 & 0 & 0 &1&1 \\ 0 & 1 & 0 &1&0\\ 0&0&1&1&1 \end{pmatrix} \in Mat(3,5;\mathbb{F}_2)$

Die Minimaldistanz kann man bestimmen durch:

d(C) = wt(C) #1
= min{ a | es gibt a linear abhängige Spalten von H } #2
= max{ a | es gibt (a - 1 ) linear unabhängige Spalten von H } #3

Wie gesagt kann es ja maximal 3 linear unabhängige Splaten geben. Mit

$\begin{pmatrix} 1 \\ 0 \\ 0 \end{pmatrix} \begin{pmatrix} 0 \\ 1 \\ 0 \end{pmatrix} \begin{pmatrix} 0 \\ 0 \\ 1 \end{pmatrix}$

wird diese maximale Anzhal erreicht und laut #3 ist d(C) = 4

Aber mit

$\begin{pmatrix} 1 \\ 0 \\ 0 \end{pmatrix} \begin{pmatrix} 0 \\ 0 \\ 1 \end{pmatrix} \begin{pmatrix} 1 \\ 0 \\ 1 \end{pmatrix}$

hätte ich ein System mit 3 linear abhängigen Spalten und somit wäre laut #2 d(C) = 3

Michael E.

Deine Definition kann nicht stimmen. Ein Gegenbeispiel für die Gleichheit von Minimum und Maximum hast du schon gefunden. Noch deutlicher wird es, wenn du eine Einheitsmatrix der Dimension n x n nimmst und eine Nullspalte hinzufügst. Dann gibt es n linear unabhängige Spalten, aber es gibt auch eine einzelne Spalte, die linear abhängig ist.

Dann war es ein Fehler meinerseits. Ich habe die Definitionen nochmal nachgeschlagen. Den Fehler habe ich fett gedruckt.

Die Minimaldistanz kann man bestimmen durch:

d(C) = wt(C) #1
= min{ a | es gibt a linear abhängige Spalten von H } #2
= max{ a | je (a - 1 ) Spalten von H sind linear unabhängige } #3

Verstehe ich es richtig, dass damit gemeint ist:
- Wähle a beliebige Spaltenvektoren.
- Es gilt, dass diese a Vektoren linear unabhängig sind.
- Maximiere das a.
Blöde Beschreibung
Somit würde es aber hinkommen. Egal welche Paare an Spaltenvektoren ich wähle, sie sind immer linear unabhängig. Sobald ich aber 3 wähle, gilt z.B. es für das Beispiel mit

$\begin{pmatrix} 1 \\ 0 \\ 0 \end{pmatrix} \begin{pmatrix} 0 \\ 0 \\ 1 \end{pmatrix} \begin{pmatrix} 1 \\ 0 \\ 1 \end{pmatrix}$

nicht mehr. Somit gilt: "Je 2 Spalten von H sind linear unabhängig und d(C) ist 3".

Danke für die Hilfe. Ich muss wohl lernen genauer zu lesen. Ich hatte das "je" einfach wegfallen lassen, weil ich ihm keine zu große Beudeutung zugeschrieben hatte.