(Twitter)
0
Hallo
Ich habe eine Matrix über den binären Körper gegeben \(A \in \mathbb{B}^{n\times m}\) und ein Vektor \(b \in \mathbb{B}^n\). Ich soll nun \(A\) minimieren, ohne den Lösungsraum in \(x\) für \(Ax=b\) beziehungsweise \(\text{Lös}(A\mid b)\) zu verändern.
Also gesucht ist eine Matrix \(A'\) und ein Vektor \(b'\), sodass \((A\mid b)\) und \( (A'\mid b') \) den selben Lösungsraum haben und \(A' \) dabei minimal viele Einsen enthält.
Mein Lösungsansatz ist, dass ich erstmal das Gaussche Eliminationsverfahren anwende. Ist die Lösung leer so setze ich \(A':=(0 \cdots 0)\) und \(b':=(1)\). Dann enthält \(A'\) keine Einsen und der Lösungsraum bleibt die leere Menge.
Wenn es genau eine Lösung \(x^\dagger\) gibt, dann setze ich \(A':=I_n \) und \(b:=x^\dagger\).
Aber was mache ich in den komplizierten Fällen? Hat jemand eine Idee? Mir ist bewusst, dass diese Aufgabe sehr schwer ist. Auch wenn jemand keine direkte Antwort hat, aber eine gute Quelle, die mir potenziell weiterhelfen könnte, würde ich mich auch sehr freuen.
Ich habe einfach keine Idee, wie ich Literatur finden kann, die mir hierbei hilft.
Kann es sein, dass dies ein NP hartes Problem ist? Ich habe jedenfalls kein effizienes Verfahren gefunden, dass deutlich effizienter ist (oberhalb von polynomiell), als alle Möglichkeiten für \(A'\) auszuprobieren und dann das minimalste \(A'\) zu nehmen, dass die Voraussetzung erfüllt.
Liebe Grüße
Ich habe eine Matrix über den binären Körper gegeben \(A \in \mathbb{B}^{n\times m}\) und ein Vektor \(b \in \mathbb{B}^n\). Ich soll nun \(A\) minimieren, ohne den Lösungsraum in \(x\) für \(Ax=b\) beziehungsweise \(\text{Lös}(A\mid b)\) zu verändern.
Also gesucht ist eine Matrix \(A'\) und ein Vektor \(b'\), sodass \((A\mid b)\) und \( (A'\mid b') \) den selben Lösungsraum haben und \(A' \) dabei minimal viele Einsen enthält.
Mein Lösungsansatz ist, dass ich erstmal das Gaussche Eliminationsverfahren anwende. Ist die Lösung leer so setze ich \(A':=(0 \cdots 0)\) und \(b':=(1)\). Dann enthält \(A'\) keine Einsen und der Lösungsraum bleibt die leere Menge.
Wenn es genau eine Lösung \(x^\dagger\) gibt, dann setze ich \(A':=I_n \) und \(b:=x^\dagger\).
Aber was mache ich in den komplizierten Fällen? Hat jemand eine Idee? Mir ist bewusst, dass diese Aufgabe sehr schwer ist. Auch wenn jemand keine direkte Antwort hat, aber eine gute Quelle, die mir potenziell weiterhelfen könnte, würde ich mich auch sehr freuen.
Ich habe einfach keine Idee, wie ich Literatur finden kann, die mir hierbei hilft.
Kann es sein, dass dies ein NP hartes Problem ist? Ich habe jedenfalls kein effizienes Verfahren gefunden, dass deutlich effizienter ist (oberhalb von polynomiell), als alle Möglichkeiten für \(A'\) auszuprobieren und dann das minimalste \(A'\) zu nehmen, dass die Voraussetzung erfüllt.
Liebe Grüße
Diese Frage melden
gefragt
cunni
Punkte: 705
Punkte: 705
Das Gaussche Eliminationsverfahren führt nicht immer zur minimalen Matrix. Nehme \(A:=\begin{pmatrix}1 & 0 & 1 & 1 & 1 & 1\\
0 & 1 & 1 & 1 & 1 & 1
\end{pmatrix}\) und \(b:=\begin{pmatrix}1 \\
0
\end{pmatrix}\).
Dann würde das Gaussche Eliminationsverfahren nichts machen. Ebenso Gauß-Jordan. Aber die Matrix \(A':=\begin{pmatrix}1 & 1 & 0 & 0 & 0 & 0\\
0 & 1 & 1 & 1 & 1 & 1
\end{pmatrix}\) hat viel weniger Einsen und den selben Lösungsraum mit \(b':=b=\begin{pmatrix}1 \\
0
\end{pmatrix}\). (Ich habe einfach die zweite Zeile auf die erste addiert und damit hat sich die Lösungsmenge nicht geändert.) ─ cunni 23.07.2021 um 20:31
0 & 1 & 1 & 1 & 1 & 1
\end{pmatrix}\) und \(b:=\begin{pmatrix}1 \\
0
\end{pmatrix}\).
Dann würde das Gaussche Eliminationsverfahren nichts machen. Ebenso Gauß-Jordan. Aber die Matrix \(A':=\begin{pmatrix}1 & 1 & 0 & 0 & 0 & 0\\
0 & 1 & 1 & 1 & 1 & 1
\end{pmatrix}\) hat viel weniger Einsen und den selben Lösungsraum mit \(b':=b=\begin{pmatrix}1 \\
0
\end{pmatrix}\). (Ich habe einfach die zweite Zeile auf die erste addiert und damit hat sich die Lösungsmenge nicht geändert.) ─ cunni 23.07.2021 um 20:31
Ich habe in der Frage jetzt den Begriff "binärer Raum" in "binärer Körper" geändert um mehr Klarheit zu schaffen.
─
cunni
23.07.2021 um 20:34
Ich hatte im Hinterkopf das Verfahren, was ich aus der Numerik noch im Hinterkopf habe, wie es technisch umgesetzt wurde. Da wird erst eine Dreieckmatrix erstellt und dann rückwärts (von unten nach oben) weiter addiert, bis rechts der Diagonalen auch Nullen entstehen. Und dabei fängt man rechts unten an, wenn die "Spitze" des Dreiecks rechts unten ist.
Also im Beipsiel ist ja $a_{1;6}\neq 0$, d.h. hier würde dann noch eine Addition stattfinden. Mit Deinem nächsten Ergebnis...
Aufgrund dessen, dass aber natürlich die Einsen in der vorletzten Zeile auch anders verteilt sein können, kann passieren, dass hinterher mehr Einsen in dieser Zeile sind. Da müsste dann vermutlich verglichen werden...
Aber vielleicht habe ich das Vorgehen auch nur falsch in Erinnerung... deshalb ja auch nur ein Kommentar und keine Antwort.... ─ joergwausw 23.07.2021 um 20:44
Also im Beipsiel ist ja $a_{1;6}\neq 0$, d.h. hier würde dann noch eine Addition stattfinden. Mit Deinem nächsten Ergebnis...
Aufgrund dessen, dass aber natürlich die Einsen in der vorletzten Zeile auch anders verteilt sein können, kann passieren, dass hinterher mehr Einsen in dieser Zeile sind. Da müsste dann vermutlich verglichen werden...
Aber vielleicht habe ich das Vorgehen auch nur falsch in Erinnerung... deshalb ja auch nur ein Kommentar und keine Antwort.... ─ joergwausw 23.07.2021 um 20:44
Meinst du den Gauß-Jordan-Algorithmus?
─
cunni
23.07.2021 um 21:30
Ja, habe gerade nachgeschlagen, das war der wohl. Zumindest laut dem Wikipedia-Beispiel würde in Deinem Beispiel der eine Schritt noch gemacht.
─
joergwausw
23.07.2021 um 21:58
Eine Diagonalmatrix hat doch die minimal mögliche Anzahl von Einsen. Das Gaußverfahren führt auf eine Diagonalmatrix bzw. eine solche mit minimal vielen zusätzlichen Einträgen bei Unterbestimmtheit... dann gilt das Vorgehen doch für jede gegebene Matrix. Oder wo ist das Problem genau? ─ joergwausw 23.07.2021 um 20:19