Построение векторов в общем положении

Пусть вещественная матрица ( ) обладает тем свойством, что любой набор из столбцов имеет полный ранг. $k\times n$ $k\le n$ ${\bf A}$ $k$

В: Существует ли эффективный способ детерминированного поиска вектора такой, что расширенная матрица сохраняет то же свойство, что и : любые столбцов имеют полный ранг. ${\bf a}$ ${\bf A}' = [{\bf A}\;{\bf a}]$ ${\bf A}$ $k$

Соответствующий идентификатор. Матрица, обладающая этим свойством, является генератором кода Рида-Соломона: добавление столбцов, сохраняющих свою структуру Вандермонда, сохраняет свойство ранга. $(n,k)$

ds.algorithms linear-algebra matrices coding-theory Димитрис
источник

Я не уверен, понимаю ли я вашу точку зрения. Я требую

не проблема.

k \leq n

$k\le n$

k = n

$k=n$

Димитрис

@ Jɛ ﬀ E k не меняется: в случае k = n только n из (сейчас) n + 1 столбцов должны иметь полный ранг. В этом случае задача должна быть простой: найти аффинное преобразование матрицы в ортогональный базис R ^ n, а затем пусть a будет вектором, изображение которого под ним является вектором всех 1.

Суреш Венкат

Мне кажется, что это должен быть способ сделать это через Grassmanian, но я не совсем понимаю, как.

Суреш Венкат

@Suresh Да, действительно, для случая n = k + 1 это кажется решаемым, как вы упомянули. Или вы можете просто выбрать

чтобы быть в нулевом пространстве всех

-коллекций векторов.

a

${\bf a}$

k

$k$

(k - 1)

$(k-1)$

Димитрис

хороший вопрос звучит как более слабая версия проблемы проверки свойства ограниченной изометрии, которая, насколько я знаю, широко открыта.

Сашо Николов

Ответы:

Если вы выбираете равномерно случайным образом из гиперкуба , матрица будет иметь желаемое свойство с вероятностью . $\mathbf{a}$ $[0,1]^n$ $[\mathbf{A}~ \mathbf{a}]$ $1$

Jeffε
источник

Я не могу не согласиться :). Проблема возникает, когда вы хотите проверить, работает ли такой вектор (независимо от того, работает ли он как). Вы должны проверить

подмножества столбцов. Эта проблема проверки становится более актуальной, когда вы рассматриваете конечные поля (фиксированного порядка), но я старался не говорить о них.

(\binom{n}{k})

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

Димитрис

Вопрос, в частности, требует эффективного детерминированного алгоритма. Если вы отвечаете на что-то связанное, но не удовлетворяете условию, указанному в вопросе, вы должны сказать об этом явно по моему мнению.

Цуёси Ито

@ TsuyoshiIto что, вы не любите котят? :)

Суреш Венкат

@Suresh: На практике было бы забавно, если бы мой компьютер вдруг превратился в котенка. В теории, однако, сначала вы должны определить котенка.

Tsuyoshi Ito

@ Jɛ ﬀ E Может, мне следовало уточнить, почему этот вопрос представляет некоторый интерес. Реальный вопрос такой же, но над конечными полями, но я склонен думать, что поля усложняют вопросы линейной алгебры. Приложение представляет собой дизайн «хороших» матриц генератора кода. Случайные (записи iid) могут быть показаны для удовлетворения свойству whp, используя такие инструменты, как лемма Шварца – Циппеля. Для этой задачи SZ обычно требует порядка полей

и вы не можете эффективно проверить, что матрицы действительно работают. Почему это важно? Потому что коды, которые, скорее всего, являются надежными, иногда не являются предпочтительными.

O (2^{k})

$O(2^k)$

Димитрис