Нижние оценки гауссовой сложности

Определим Gaussian сложность в качестве матрицы , чтобы минимальное число элементарных операций строк и столбцов , необходимых для приведения матрицы в верхней треугольной форме. Это величина от до (через гауссовское исключение). Понятие имеет смысл в любой области.$n \times n$n $0$$n^2$

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

Известны ли какие-либо нетривиальные явные нижние оценки?

Под нетривиальным я подразумеваю суперлинейный. Просто для ясности: для конечных полей счетный аргумент показывает, что случайная матрица имеет порядок сложности n ^ 2 (аналогичное утверждение должно быть верно для бесконечных полей). Следовательно, мы ищем явное семейство матриц, например, матрицы Хадмара. Это то же самое, что и со сложностью булевой схемы, когда мы знаем, что случайная функция имеет высокую сложность, но мы ищем явные функции с этим свойством.

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

Предположим, мы рассматриваем квадратную обратимую матрицу A и определяем c (A) как минимальное количество операций элементарной строки, необходимых для приведения A к единичной матрице. Эта мера сложности больше, чем та, которую предлагает Мориц, поэтому доказать суперлинейные оценки для нее можно только проще.

Теперь операции со строками обратимы . Отсюда следует, что c (A) может быть эквивалентно определено как минимальное количество операций строки, необходимых для получения A, начиная с единичной матрицы.

Обратите внимание, что создание A таким способом приводит к арифметической схеме для вычисления карты, переводящей x в Ax. Fanin каждого вентиля равен 2, а количество невходных вентилей соответствует количеству операций со строками.

Нет очевидного сокращения в обратном направлении (от цепей до последовательностей строк). Тем не менее, мы можем охарактеризовать c (A) с точки зрения сложности арифметической схемы Ax в модели ограниченного контура: я утверждаю, что c (A) равна половине минимального числа ребер в арифметической схеме для A, из fanin самое большее 2 и ширина n, где мы не взимаем плату за ребра, ведущие к воротам fanin 1. (Я использую обычное понятие ширины цепи здесь.) Это можно показать с помощью простой идеи, набросанной ранее.

Теперь вот связь с хорошо изученными проблемами: более 30 лет было известной открытой проблемой, чтобы показать явное линейное отображение Ax (над любым конечным полем), для которого требуется суперлинейное число вентилей в схеме fanin-2. Классическим справочником является Valiant, «Теоретические графы аргументы в низкоуровневой сложности», а также недавний опрос FTTCS Lokam также полезен.

Изучая c (A), мы накладываем дополнительное ограничение ширины, но, поскольку наше ограничение очень слабое (ширина n), я не ожидаю, что проблема станет намного проще. Но, эй, я бы хотел оказаться неправым.

Есть ссылки, и они довольно старые. Я сталкивался с ними, работая над комбинаторными алгоритмами для умножения булевых матриц.

В 1966 году Мун и Мозер доказали, что для вычисления обратной матрицы над GF (2) требуется $\Theta(n^2/log n)$$\log n$

Дж. В. Мун и Л. Мозер. Задача сокращения матриц. Математика вычислений 20 (94): 328–330, 1966.

Статья должна быть доступна на JSTOR.

Я почти уверен, что нижняя граница - это просто счетный аргумент, и никаких явных матриц, достигающих нижней границы, не было дано.