Złożoność decydowania, czy macierz jest całkowicie regularna

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? $k$ $k$ $k$ $k$

— Markus Bläser
źródło

Podstawowe pytanie: co masz na myśli mówiąc „regularna matryca”? Dzięki!

— Henry Yuen

masz na myśli to, że każda submaterrix jest nieparzysty? pamiętam, że było podobne pytanie, którego nie mogę teraz znaleźć

— Sasho Nikolov

Rzeczywiście istnieją trzy różne znaczenia słowa regularnego: en.wikipedia.org/wiki/Regular_matrix

— Suresh Venkat

ah, znalazłem powiązane pytanie: cstheory.stackexchange.com/questions/10962/… . twoje pytanie bardziej pasuje do komentarza, który tam napisałem: jest to łatwiejszy wariant pytania (szeroko otwarte AFAIK) testowania partii z ograniczoną izometrią.

— Sasho Nikolov

W przypadku pól skończonych testowanie, czy macierz jest nieregularna, jest równoważne ze sprawdzeniem, czy macierz generatora kodu ma minimalną odległość (tj. Czy jest to MDS). Nawet stałe przybliżenia współczynników w celu znalezienia minimalnej odległości kodu są trudne. Sprawdź ten artykuł ee.ucr.edu/~dumer/ieee49-1-03-np.pdf i odnośniki w nim zawarte.

n \times k

$n\times k$

k

$k$

n \times k

$n\times k$

n - k + 1

$n-k+1$

— Dimitris,

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. $\mathsf{NP}$ $n\times m$ $\mathbb Z$ $n\le m$ $n\times n$

— Bruno
źródło

Dzięki, Bruno! Czy nie możemy zredukować problemu twojej odpowiedzi na mój problem przez losową redukcję (ponad uzasadnienia)? Wystarczy dodać przypadkowych wierszy. Jeśli nowa matryca nie jest całkowicie regularna, zawiera ona pojedynczą -submatrix w pierwszych wierszach z dużym prawdopodobieństwem. Ah nie. Podmacierz może być mniejsza. Ale może uda się to zrobić ...

m - n

$m-n$

n \times n

$n \times n$

n

$n$

— Markus Bläser,

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. Teraz $n \times m$ $A$ $n < m$ $\text{rank}(A) = n$ $n$ $A$ $A =[B\ |\ D]$ $B$ $n \times n$ $A$ $n \times n$ $B^{-1}D$

— leonid gurvits
ź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.

— leonid gurvits
źródło