Konstruowanie wektorów w pozycji ogólnej

Niech prawdziwa macierz $k\times n$ ( $k\le n$ ) ${\bf A}$ z tą właściwością, że dowolny zbiór $k$ kolumn ma pełną rangę.

P: istnieje efektywny sposób deterministyczny znaleźć wektor tak że zmodyfikowanym matrycy ${\bf a}$ ${\bf A}' = [{\bf A}\;{\bf a}]$ zachowuje tę samą właściwość co ${\bf A}$ : dowolne $k$ kolumn ma pełną pozycję.

Odpowiedni Sidenote: Macierz, która ma tę właściwość, jest generatorem kodu $(n,k)$ Reeda-Solomona: dodanie kolumn, które zachowują jej strukturę Vandermonde, zachowuje właściwość rangi.

ds.algorithms linear-algebra matrices coding-theory Dimitris
źródło

Nie jestem pewien, czy rozumiem twój punkt widzenia. Wymagam

k \leq n

$k\le n$ ,

k = n

$k=n$ nie jest problemem.

Dimitris,

@ Jɛ ﬀ E k się nie zmienia: w przypadku k = n tylko n (obecnie) n + 1 kolumn musi mieć pełną rangę. W takim przypadku problem powinien być łatwy: znajdź afiniczną transformację macierzy do ortogonalnej podstawy R ^ n, a następnie niech będzie wektorem, którego obrazem jest wektor all 1s.

Suresh Venkat

Wydaje mi się, że powinien to być sposób na zrobienie tego za pośrednictwem Grassmanian, ale nie bardzo rozumiem, jak to zrobić.

Suresh Venkat

a

${\bf a}$

k

$k$

(k - 1)

$(k-1)$

Fajne pytanie. brzmi jak słabsza wersja problemu weryfikacji ograniczonej właściwości izometrycznej, która jest szeroko otwarta, o ile mi wiadomo.

Sasho Nikolov

Odpowiedzi:

$\mathbf{a}$ $[0,1]^n$ $[\mathbf{A}~ \mathbf{a}]$ $1$

Jeffε
źródło

Nie mogę się zgodzić :). Problem pojawia się, gdy chcesz sprawdzić, czy taki wektor działa (bez względu na to, czy działa jak). Musisz sprawdzić podzbiory kolumn. Ten problem sprawdzania staje się bardziej istotny, gdy weźmie się pod uwagę pola skończone (o ustalonej kolejności), ale starałem się nie mówić o nich.

(\binom{n}{k})

${{n}\choose{k}}$

Dimitris,

Pytanie dotyczy w szczególności wydajnego algorytmu deterministycznego . Jeśli odpowiesz na coś powiązanego, ale nie spełnia warunku określonego w pytaniu, moim zdaniem powinieneś to wyraźnie powiedzieć.

Tsuyoshi Ito

@TsuyoshiIto co, nie lubisz kociąt? :)

Suresh Venkat

@Suresh: W praktyce zabawne byłoby, gdyby mój komputer nagle zmienił się w kotka. Teoretycznie jednak najpierw musisz zdefiniować kociaka.

Tsuyoshi Ito

@ Jɛ ﬀ E Może powinienem był wyjaśnić, dlaczego to pytanie jest interesujące. Prawdziwe pytanie jest takie samo, ale dotyczy pól skończonych, ale wydaje mi się, że pola komplikują pytania dotyczące algebry liniowej. Aplikacja polega na zaprojektowaniu „dobrych” matryc generatora kodu. Te losowe (wpisy iid) mogą być pokazane, aby zaspokoić właściwość whp, za pomocą narzędzi takich jak lemat Schwartz – Zippel. W przypadku tego problemu SZ zwykle wymaga rzędów pola i nie można skutecznie sprawdzić, czy macierze naprawdę działają. Dlaczego to jest ważne? Ponieważ kody, które są najprawdopodobniej wiarygodne, są czasami nie preferowane.

O (2^{k})

$O(2^k)$

Dimitris,