Сложность решения, является ли матрица полностью регулярной

Матрица называется вполне регулярной, если все ее квадратные подматрицы имеют полный ранг. Такие матрицы использовались для построения суперконцентраторов. В чем сложность решения, является ли данная матрица полностью регулярной по рациональным числам? Над конечными полями?

В более общем смысле , назовем матрицу полностью -регулярной, если все ее квадратные подматрицы размером не более имеют полный ранг. Учитывая матрицу и параметр , какова сложность решения, является ли матрица полностью -регулярной?$k$$k$$k$$k$

Статья « Матрицы Вандермонда, NP-полнота и трансверсальные подпространства» [ps] Александра Чистова, Эрве Фурнье, Леонида Гурвица и Паскаля Койрана может иметь отношение к вашему вопросу (хотя она не отвечает на него).

Они доказывают -полноту следующей задачи: учитывая матрицу n × m над Z ( n ≤ m ), решите, существует ли подматрица n × n , определитель которой обращается в нуль.$\mathsf{NP}$$n\times m$$\mathbb Z$$n\le m$$n\times n$

Да, ваша проблема, по существу , эквивалентно одному (общее положение) в Александровском Чистова, Эрве Фурнье, Леонид Гурвиц и Паскаль Koiran бумаги .

Рассмотрим матрицу A , n < m . Не ограничивая общности, предположим, что rank ( A ) = n и первые n столбцов A независимы: A = [ B | D ] , где B - неособая матрица n × n . Теперь A содержит особую подматрицу n × n тогда и только тогда, когда B - 1$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$ не совсем регулярно.

Есть еще одна проблема NP-Complete в том же духе: для квадратной матрицы решить, являются ли все ее главные подматрицы (т.е. строки и столбцы из одного набора) неособыми. Еще один любопытный факт: сумма квадратов определителей всех квадратных подматриц проста (просто Det (I + AA ^ {T})), но сумма абсолютных значений равна # P-Complete.