Finden einer Basis

Neue Frage »

08.06.2023, 19:43	Ralf2023	Auf diesen Beitrag antworten »
Finden einer Basis Hallöchen, wenn ich die Menge $\begin{eqnarray} L(A) := \left\{z \in Z^m : Az = y \text{ mod } q \right\} \end{eqnarray}$ habe und $\begin{eqnarray} A \in Z_q^{n \times m} \end{eqnarray}$ ist, wobei wir annehmen $\begin{eqnarray} n \leq m \end{eqnarray}$ , wie würde man zu einem gegebenen $\begin{eqnarray} A \end{eqnarray}$ eine Basis dieses Raumes finden?
08.06.2023, 21:41	Elvis	Auf diesen Beitrag antworten »
Für eine Primzahlpotenz $\begin{eqnarray} q=p^n \end{eqnarray}$ haben wir es mit einem Vektorraum V über einem endlichen Körper zu tun, also kann man wie immer den Gauß-Algorithmus anwenden. Die Lösungsmenge kann leer oder eine Nebenklasse von V nach dem Lösungsraum des homogenen LGS sein, nur für homogenes LGS hat die Frage nach einer Basis eine Bedeutung. Wenn q keine Primzahlpotenz ist, weiß ich auch keine Antwort.
08.06.2023, 22:54	Ralf2023	Auf diesen Beitrag antworten »
Ok, gehen wir mal davon aus, dass $\begin{eqnarray} q \end{eqnarray}$ eine Primzahl ist. Der Gauß-Algorithmus ist anwendbar, weil es in diesem Fall ein multiplikatives inverses gibt, oder? Wie genau sehe denn eine Basis aus, also gibt es eine Möglichkeit zu beschreiben, wie diese konkret beschaffen ist. Mit dem Gauß-Algorithmus könnte man ja erstmal auf eine Zeilen-Stufen-Form umformen. Danke für deine Hilfe, Elvis!
09.06.2023, 07:14	Elvis	Auf diesen Beitrag antworten »
Wenn q=p eine Primzahl ist, dann haben wir einen Primkoerper $\begin{eqnarray} \mathbb F_p \end{eqnarray}$ . Der Gauß-Algorithmus liefert eine Matrix in einer Form, an der man die Lösungsmenge ablesen kann. Der Gauß-Algorithmus funktioniert für Matrizen über einem beliebigen Körper, weil die Grundrechenarten in jedem Körper ausführbar sind. Wenn die Lösungsmenge ein UVR ist, hat der eine Basis. Eine Basis kann man berechnen, ich weiß nicht, wie man eine Basis beschreiben kann. Per Definition ist eine Basis ein linear unabhängiges Erzeugendensystem, ein minimales Erzeugendensystem, ein maximales linear unabhängiges Erzeugendensystem. Wenn du ein konkretes Beispiel hast, kannst du rechnen. Wenn du deine Rechnung fertig hast und hier vorstellst, kann ich mehr dazu sagen.
09.06.2023, 08:07	Ralf2023	Auf diesen Beitrag antworten »
Hallo Elvis, das Beschreiben, bezog sich eher auf die Gestalt der Basismatrix. Nach Anwendung des Gauß-Algorithmus kann man festhalten, dass es eine rechts obere Matrix sein muss. Gibt es weitere Charakteristika? Ich versuche eine Art Block-Matrix für die Basis zu finden. Wir könnten auch den $\begin{eqnarray} n \times n \end{eqnarray}$ Teil der Matrix $\begin{eqnarray} A \end{eqnarray}$ als invertierbar auffassen. Das hieße dann $\begin{eqnarray} A = \left[A_1 \| A_2\right] = \left[I \| A_1^{-1}A_2\right] \end{eqnarray}$ , wobei $\begin{eqnarray} I \end{eqnarray}$ die $\begin{eqnarray} n \times n \end{eqnarray}$ Einheitsmatrix ist. Gibt uns das eine Möglichkeit, diesen Gedanken fortzusetzen, sodass man die resultierende Basis als eine Art Block-Matrix verstehen kann?
09.06.2023, 09:50	Elvis	Auf diesen Beitrag antworten »
So kommst du nicht weiter, denn eine Basis ist keine Matrix irgend einer Art sondern eine Menge von Vektoren. Beispiele in $\begin{eqnarray} \mathbb F_2 \end{eqnarray}$ mit $\begin{eqnarray} s\in \mathbb F_2 \end{eqnarray}$ Beispiel 1 $\begin{eqnarray} \begin{pmatrix} 1 & 1 & \| & 1 \\ 1 & 1 & \| & 0 \end{pmatrix}\rightarrow \begin{pmatrix} 1 & 1 & \| & 1 \\ 0 & 0 & \| & 1 \end{pmatrix}\Rightarrow \mathbb L=\emptyset \end{eqnarray}$ hat keine Basis Beispiel 2 $\begin{eqnarray} \begin{pmatrix} 1 & 1 & \| & 0 \\ 1 & 1 & \| & 0 \end{pmatrix}\rightarrow \begin{pmatrix} 1 & 1 & \| & 0 \\ 0 & 0 & \| & 0 \end{pmatrix}\Rightarrow x_2=s, x_1=x_2\Rightarrow \mathbb L=\{s\begin{pmatrix} 1 \\ 1 \end{pmatrix}\}\Rightarrow \end{eqnarray}$ Basis von $\begin{eqnarray} \mathbb L=\{\begin{pmatrix} 1 \\ 1 \end{pmatrix}\} \end{eqnarray}$ Beispiel 3 $\begin{eqnarray} \begin{pmatrix} 1 & 1 & \| & 1 \\ 0 & 0 & \| & 0 \end{pmatrix}\Rightarrow x_2=s, x_1=s+1\Rightarrow \mathbb L=\{\begin{pmatrix} 1 \\ 0 \end{pmatrix}+s\begin{pmatrix} 1 \\ 1 \end{pmatrix}\} \end{eqnarray}$ hat keine Basis
Anzeige

09.06.2023, 10:06	Ralf2023	Auf diesen Beitrag antworten »
Hallo Elvis, ich glaube ich sollte mich besser ausdrücken. Eine Basis ist garantiert keine Matrix, genau, sondern ein linear unabhängiges erzeugendes System. Ich versuche eine Matrix zu finden, aus deren Spalten man eine Basis für L(A) ablesen kann. Dies habe ich versucht mit meinem vorherigen Statement etwas in die Wege zu leiten.
09.06.2023, 10:45	Elvis	Auf diesen Beitrag antworten »
Aus der Matrix A kann man nichts ableiten. In meinen Beispielen ist die Matrix immer dieselbe, wenn ich in Beispiel 3 die erste Gleichung zwei mal schreibe, und nur zusammen mit der rechten Seite liefert der Gauß-Algorithmus den Lösungsraum und eine Basis, falls es eine gibt. Eine Basis muss man nicht extra berechnen, Gauß macht alles.
09.06.2023, 11:04	URL	Auf diesen Beitrag antworten »
@Elvis: Du hast doch schon konstatiert, dass die Frage nur für homogene LGS sinnvoll ist. Also beschränken wir uns doch darauf. Und auf eine Matrix, die nach Anwendung des Gauß-Verfahrens entstanden ist. Beispielsweise $\begin{eqnarray} \begin{pmatrix} 1 & \textcolor{brown}{-1} & 0 & \textcolor{brown}{0} & \textcolor{brown}{-3} \\ 0 &0 &1 &-1 &-1 \end{pmatrix} \end{eqnarray}$ In Gleichungen also $\begin{eqnarray} x_1=x_2+3x_5 \end{eqnarray}$ und $\begin{eqnarray} x_3=x_4+x_5 \end{eqnarray}$ Freie Parameter wären hier $\begin{eqnarray} x_2, x_4, x_5 \end{eqnarray}$ und man bekommt $\begin{eqnarray} \begin{pmatrix} x_1\\x_2\\x_3\\x_4\\x_5\end{pmatrix}= x_2 \begin{pmatrix} \textcolor{brown}{1}\\ \textcolor{red}{1}\\0\\ \textcolor{red}{0} \\ \textcolor{red}{0}\end{pmatrix} + x_4 \begin{pmatrix} \textcolor{brown}{0 } \\ \textcolor{red}{0} \\1\\ \textcolor{red}{1} \\ \textcolor{red}{0}\end{pmatrix} + x_5 \begin{pmatrix} \textcolor{brown}{3}\\ \textcolor{red}{0} \\1\\ \textcolor{red}{0} \\ \textcolor{red}{1}\end{pmatrix} \end{eqnarray}$ Dass die rot markierten Einträge gerade die kanonischen Einheitsvektoren des Parameterraums sind, ist natürlich kein Zufall.
09.06.2023, 15:08	Elvis	Auf diesen Beitrag antworten »
Das darfst du so machen, weil du weißt, was du tust. Ich finde es nicht so gut, die Unbestimmte $\begin{eqnarray} x_k \end{eqnarray}$ als Variable $\begin{eqnarray} s\in K \end{eqnarray}$ zu benutzen, weil das unterschiedliche Objekte sind.
09.06.2023, 16:17	URL	Auf diesen Beitrag antworten »
Es ging nur darum festzulegen, nach welchen Unbestimmten ich die beiden Gleichungen auflöse. Die gezeigte Basis hätte man dann genauso gefunden, auch wenn man kein Wort über freie Parameter verloren hätte.

Neue Frage »

Antworten »

Finden einer Basis

Verwandte Themen