Matryca jest nazywana całkowicie regularną, jeśli wszystkie jej kwadratowe submatrice mają pełną rangę. Takie matryce zastosowano do budowy superkoncentratorów. Jaka jest złożoność decyzji, czy dana matryca jest całkowicie regularna w stosunku do racjonalności? Ponad skończonymi polami?
Mówiąc bardziej ogólnie, nazwij matrycę całkowicie nieregularną, jeśli wszystkie kwadratowe podmacie wielkości co najwyżej mają pełną rangę. Biorąc pod uwagę macierz i parametr , jaka jest złożoność decyzji, czy macierz jest całkowicie nieregularna?
cc.complexity-theory
reference-request
linear-algebra
matrices
Markus Bläser
źródło
źródło
Odpowiedzi:
Artykuł Vandermonde Matrices, NP-Completeness i Transversal Subspaces [ps] autorstwa Alexandra Chistova, Hervé Fourniera, Leonida Gurvitsa i Pascala Koirana może być istotny dla twojego pytania (choć nie odpowiada na nie).
Dowodzą one kompletności następującego problemu: : Biorąc pod uwagę macierz nad ( ), zdecyduj, czy istnieje podmacierz której wyznacznik znika.NP n×m Z n≤m n×n
źródło
Tak, twój problem jest zasadniczo równoznaczny z tym (stanowisko ogólne) w artykule Aleksandra Chistova, Hervé Fourniera, Leonida Gurvitsa i Pascala Koirana .
Rozważmy macierz , . Bez utraty ogólności, załóżmy, że i pierwsze kolumn są niezależne: , gdzie jest macierzą niepodzielną macierzy. Terazn×m A n<m rank(A)=n n A A=[B | D] B n×n A n×n B−1D
źródło
Jest jeszcze jeden problem NP-Complete w tym samym duchu: aby matryca kwadratowa decydowała, czy wszystkie jej główne podmacierze (tj. Rzędy i kolumny z tego samego zestawu) nie są jednostkowe. Kolejny ciekawy fakt: suma kwadratów wyznaczników wszystkich podmacierzy kwadratowych jest łatwa (tylko Det (I + AA ^ {T})), ale suma wartości bezwzględnych wynosi # P-Complete.
źródło