рассмотрим квадратные матрицы с элементами из поля GF2 у которых на главной диагонали всегда "1" и также есть "ленточка" 1-чек параллельно главной диагонали. очевидно что определитель такой матрицы всегда отличене от нуля. расширим круг рассматриваемых матриц. как и прежде на главной диагонали "1"ки. но количество "ленточек" из 1чек параллельно главной диагонали > 1. например 1 0 1 0 0 1 0 0 1 0 1 0 0 1 0 0 1 0 1 0 0 0 0 0 1 0 1 0 1 0 0 0 1 0 1 0 1 0 0 0 1 0 0 0 1 0 0 0 1 суть вопроса. при каких "геометрических" условиях на количество и расположение ленточек в матрице ее определитель не равен нулю ?
То есть нужна формула, вычисляемая с меньшими затратами чем алгоритм Гаусса? Вряд ли это возможно в принципе. Частных же случаев довольно много, например: не равен нулю если все "боковые ленточки" находятся в одной половине, равен нулю если "боковых ленточек" две и расположены они симметрично(если постараться то для симметричного случая наверное действительно можно вывести общие правила) и.т.д. Эта проблема имеет какое-то "практическое значение" или просто "из интереса"?
нужен критерий отличности определителя от нуля. собственно его значение не играет роли она вылезла при рассмотрении обобщенных псевдокодов грея.
Relayer Если я правильно понимаю, то в GF2 неравный нулю определитель может иметь только одно значение: 1 А так запускаешь Гаусса и смотришь что окажется на главной диагонали.
да, это меня заклинило малость ) хе. эт мы умеем. вопрос то не в этом. как выяснить энто не запуская гаусса.
А так запускаешь Гаусса и смотришь что окажется на главной диагонали. Пардон, я не силен в линейной алгебре вообще - довольно далекая от меня область. Однако, насколько я знаю, для GF(2) лучше брать Ланщоца. Модификация описана Монтгомери. У мя pdf есть.
volodya А ссылкой или самим pdfом не поделишься? Или по каким ключевым словам искать? А то "Ланщоц" поисковым машинам не известен, а нужного Монтгомери можно до посинения искать..
Ссылка под паролем. Это американская сеть журналов. Однако сайт васма - рулит Есть книжечка: http://wasm.ru/docs/8/vasilenko.zip там в приложении Ланшоц кратенько. Если этого будет мало - сугубо в этом топе положу pdf с измышлизмами Монтгомери.
А то "Ланщоц" поисковым машинам не известен Пишется как "lanczos" В гугле тут же дает ссылкочку на, например, http://www.netlib.org/lanczos/
volodya Ааа, так это Ланцош, то бишь Lanczos, тогда конечно знаю Метод итеративный, то есть выигрыш будет для больших матриц с небольшим количеством боковых ленточек("sparse matrix"). Работу Montgomery нашел в списке литературы в pdfе, спасибо, посмотрю в библиотеке.
тогда конечно знаю Я же и говорю - приятно иметь дело со специалистами Тьфу, неправильно имя написал. Никогда эту гадость выговорить не мог
Могу предложить критерий для одного частного случая. Пусть исходная матрица является суммой матриц циклических перестановок(тобишь, когда эту матрицу умножают на вектор, его координаты циклический сдвигаются). Такая матрица имеет ленточный вид: x0 x1 x2 ... xn xn x0 x1 ... xn-1 ............... x1 x2 x3 ... x0 Построим многочлен над GF2 p(t)=x0+x1*t+x2*t^2+...+xn*t^n, то определитель матрицы равен 1 если gcd(p(t),t^(n+1)+1)=1, иначе 0 (gcd - наибольший общий делитель многочленов в GF2) З.Ы. Сомневаюсь что существует простой геометрический критерий для этого, тем более для общего случая. З.Ы.Ы Может быть я ошибся...
blood Всё верно, только почему для "частного случая"? Это как раз и есть общий случай. Вычислять gcd над GF2 - одно удовольствие. Многочлены можно как как числа представлять с XOR вместо сложения (также как в CRC). Так что, всё очень эффективно.
