Komplexität bei der Entscheidung, ob eine Matrix völlig regelmäßig ist

19

Eine Matrix heißt total regular, wenn alle ihre quadratischen Submatrizen den vollen Rang haben. Solche Matrizen wurden verwendet, um Superkonzentratoren zu konstruieren. Wie komplex ist es, zu entscheiden, ob eine gegebene Matrix über die Rationen hinweg völlig regelmäßig ist? Über endliche Felder?

Allgemeiner gesagt , nenne eine Matrix völlig regulär, wenn alle ihre quadratischen Submatrizen mit einer Größe von höchstens k den vollen Rang haben. Wie komplex ist es, bei einer gegebenen Matrix und einem gegebenen Parameter k zu entscheiden, ob die Matrix vollständig k- regulär ist?kkkk

Markus Bläser
quelle
7
Eine elementare Frage: Was meinst du, wenn du reguläre Matrix sagst? Vielen Dank!
Henry Yuen
Meinst du, dass jede Submatrix nicht singulär ist? Ich erinnere mich, dass es eine ähnliche Frage gab, die ich derzeit nicht finden kann
Sasho Nikolov
5
In der Tat gibt es drei verschiedene Bedeutungen von regulär: en.wikipedia.org/wiki/Regular_matrix
Suresh Venkat
2
ah, fand die verwandte Frage: cstheory.stackexchange.com/questions/10962/… . Ihre Frage passt besser zu dem Kommentar, den ich dort gemacht habe: Dies ist eine einfachere Variante der (weit offenen AFAIK) Frage des Testens der eingeschränkten Isometrie-Partei.
Sasho Nikolov
1
Über endlichen Feldern ist das Prüfen, ob eine Matrix k- regulär ist, gleichbedeutend mit dem Prüfen, ob eine n × k- Codegeneratormatrix den Mindestabstand n - k + 1 hat (dh ob es sich um MDS handelt). Selbst konstante Faktorapproximationen zum Ermitteln des Mindestcodeabstands sind schwierig. Überprüfen Sie dieses Papier ee.ucr.edu/~dumer/ieee49-1-03-np.pdf und die darin enthaltenen Referenzen. n×kkn×knk+1
Dimitris

Antworten:

13

Die Arbeit Vandermonde Matrices, NP-Completeness und Transversal Subspaces [ps] von Alexander Chistov, Hervé Fournier, Leonid Gurvits und Pascal Koiran könnte für Ihre Frage relevant sein (obwohl sie diese nicht beantwortet).

Sie beweisen die -completeness aus folgendem Problem: Da eine n × m - Matrix über Z ( n m ), entscheiden , ob es existiert eine n × n Submatrix deren Determinante Null wird .NPn×mZnmn×n

Bruno
quelle
1
Danke, Bruno! Können wir das Problem Ihrer Antwort auf mein Problem nicht durch eine zufällige Reduktion (über die Rationals) reduzieren? Fügen Sie einfach zufällige Zeilen hinzu. Wenn die neue Matrix nicht vollständig regulär ist, enthält sie mit hoher Wahrscheinlichkeit eine singuläre n × n- Submatrix in den ersten n Zeilen. Ah nein. Die Submatrix könnte kleiner sein. Aber vielleicht kann man das klappen lassen ...mnn×nn
Markus Bläser
6

Ja, Ihr Problem ist im Wesentlichen äquivalent zu der (General Position) in dem Alexander Chistov, Hervé Fournier, Leonid Gurvits und Pascal Koiran Papier .

Man betrachte eine Matrix A , n < m . Ohne Verlust der Allgemeinheit sei angenommen, dass Rang ( A ) = n und die ersten n Spalten von A unabhängig sind: A = [ B | D ] , wobei B eine nicht singuläre n × n- Matrix ist. Nun enthält A genau dann eine singuläre n × n- Submatrix, wenn B - 1 Dn×mAn<mrank(A)=nnAA=[B | D]Bn×nAn×nB1D ist nicht ganz normal.

leonidische Gurvits
quelle
3

Es gibt ein weiteres NP-Complete-Problem im selben Sinne: Wenn eine quadratische Matrix entscheidet, ob alle ihre Haupt-Submatrizen (dh Zeilen und Spalten aus derselben Menge) nicht singulär sind. Eine andere merkwürdige Tatsache: Die Summe der Determinantenquadrate aller quadratischen Submatrizen ist einfach (nur Det (I + AA ^ {T})), aber die Summe der absoluten Werte ist # P-Complete.

leonidische Gurvits
quelle