линейная-алгебра — Доказать, что детерминант симметричной матрицы Паскаля равен 1
На Википедии приведено доказательство через произведение треугольных матриц. Оно какое-то искусственное (как до него додуматься, не зная про треугольные матрицы Паскаля?) + не понимаю, как в общем виде доказать, что произведение треугольных матриц Паскаля равно симметричной.
Сам пробовал приводить матрицу к верхнетреугольному виду: $$\begin
задан 1 Дек ’17 11:31
@SerVB: попробуйте сделать так: вычитать из строки предыдущую, начиная снизу. Записывать это всё в виде сочетаний. Тогда будет получаться понятная закономерность того, что возникает, с учётом тождества C(n+1,m)=C(n,m-1)+C(n,m).
@falcao, закономерность понял, спасибо!
не понимаю, как в общем виде доказать, что произведение треугольных матриц Паскаля равно симметричной. — если я не ошибаюсь, то там просто заметили, что можно каждый элемент записать как свёртку Вандермонда. отсюда и треугольные матрицы Паскаля появились.
Здравствуйте
Математика — это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.
Re: [алгоритм] определитель и трeугольник пaскаля
Определитель = 1. Метод Гаусса. Причем тут треугольник Паскаля?
Re: [алгоритм] определитель и трeугольник пaскаля
Да, обшибся. Не 1.
Re: [алгоритм] определитель и трeугольник пaскаля
попробуй вычислить, применяя элементарные преобразования:
Сначала из j+1 столбца вычитаешь j-тый, проходя по j от n-1 до 1.
Там вроде останется матрица из одних единиц, у которой определитель равен 0.
Хотя я могу ошибаться, а расписывать влом 🙂
Re: [алгоритм] определитель и трeугольник пaскаля
действительно не 0 🙂
но попробуй преобразовать указанным мной методом, матрица значительно упростится
Re: [алгоритм] определитель и трeугольник пaскаля
Определитель будет равен n.
Гоняешь несколько(n-1) раз вычитание столбцов по описанному выше методу, в результате получаешь нижнетреугольную матрицу с диагональю [1,1. 1,n], у которой det=n.
Re: [алгоритм] определитель и трeугольник пaскаля
Не обшибся. Таки 1.
Re: [алгоритм] определитель и трeугольник пaскаля
получится матрица с единичной диагональю
Re: [алгоритм] определитель и трeугольник пaскаля
что там у нас в talks про второкурсника проскакивало? тут лучше )
Re: [алгоритм] определитель и трeугольник пaскаля
я понял как решать, когда сдам отпишу решение.
осталось тока формулу записать и доказать.
всё элементарно, хватило методички за 1 курс, 1 семестр по лин. алегбре. )
Re: [алгоритм] определитель и трeугольник пaскаля
> Не обшибся. Таки 1.
Re: [алгоритм] определитель и трeугольник пaскаля
Биномиальный коэффициент
Если знать такое утверждение из алгебраической комбинаторики, то тоже очень просто. Пусть a_1, a_2, . a_n, b_1, . b_n — целочисленные точки на плоскости и p_ij — количество путей по решетке (идущих, скажем, только вправо или вниз) из точки a_i в точку b_j. Тогда определитель матрицы (p_ij) — это количество наборов таких попарно непересекающихся путей из a_1 в b_1, из a_2 в b_2, . a_n в b_n. Если выбрать a_i=(0,i-1), b_i=(i-1,0), то матрица (p_ij) как раз данная. С другой стороны, есть только один набор непересекающихся путей: a_i->(i-1,i-1)->b_i. Поэтому определитель 1.
В общем, учите математику. Быдлокодерство поспеет.
Re: [алгоритм] определитель и трeугольник пaскаля
так, решение не отпишу) ибо неправильно)
действительно получается всегда один. надо тока оформить это дело теперича.
а с определителем Вандермонда, не очень то и понял в чем его смысл..
с "утверждением из алгебраической комбинаторики" тоже слегка непонятно)
Re: [алгоритм] определитель и трeугольник пaскаля
матрица Вандермонда — (a_i^
ее определитель = \prod (a_i — a_j)
пусть есть многочлены P_j(x) = c_j x^
тогда определитель матрицы (P_j(a_i))_
Матрица Паскаля
В математике, особенно в теории матриц и комбинаторике, ма́трица Паска́ля — это бесконечная матрица, элементами которой являются биномиальные коэффициенты. Существует три варианта расположения элементов в матрице: в виде верхнетреугольной, нижнетреугольной или симметричной матрицы. 5×5-ограничения таких матриц имеют вид:
[math]\displaystyle < S_5=\begin
Эти матрицы удовлетворяют соотношению Sn = LnUn. Отсюда легко видеть, что все три матрицы имеют единичный определитель, так как определитель треугольных матриц Ln и Un равен произведению их диагональных элементов. Другими словами, матрицы Sn, Ln, и Un унимодулярны. След матриц Ln и Un равен n.
Элементы симметричной матрицы Паскаля имеют вид:
Таким образом, след матрицы Sn равен
в зависимости от n образуя последовательность: 1, 3, 9, 29, 99, 351, 1275, … последовательность A006134 в OEIS.
Содержание
Построение
Матрица Паскаля может быть построена посредством взятия экспоненты от поддиагональной или наддиагональной матрицей специального вида. В следующем примере строятся матрицы 7×7, но этот метод работает для любых n×n-матриц Паскаля. (Точками обозначены нулевые элементы.)
Важно отметить, что нельзя просто положить exp(A)exp(B) = exp(A + B) для n×n-матриц A и B, такое равенство имеет место только при AB = BA (то есть когда матрицы A и B коммутируют). В приведённом построении симметричных матриц Паскаля наддиагональные и поддиагональные матрицы не коммутируют. Таким образом, нельзя провести (возможно) ожидаемое упрощение, включающее сумму матриц.
Полезное свойство поддиагональных и наддиагональных матриц, используемое в данном построении — это их нильпотеность, то есть при возведении в достаточно большую целую степень они вырождаются в нулевую матрицу. (Смотри матрица сдвига для дальнейших деталей.) Так как обобщённые n×n-матрицы сдвига, которые тут используются, становятся равными нулю при возведении в степень n, то при вычислении матричной экспоненты необходимо рассматривать только первый n + 1 член бесконечного ряда, чтобы получить точный результат.
Варианты
Интересные варианты могут быть получены посредством очевидных модификаций матриц PL7, от которых берётся экспонента.
Первый пример ниже использует квадраты значений в PL7 вместо исходных и приводит к построению 7×7-матрицы Лагерра (матрицы, элементами которой являются полиномы Лагерра).
(Матрица Лагерра на самом деле использует другое масштабирование и знаки некоторых коэффициентов.)
Второй пример использует v(v + 1) в качестве элементов, если v— элементы исходной матрицы. Он приводит к построению 7×7-матрицы Лаха (матрицы с элементами в виде чисел Лаха).
Использование v(v − 1) приводит к диагональному сдвигу вниз-вправо.
Третий пример использует квадрат исходной PL7-матрицы, делёный на 2, другими словами: биномиальные коэффициенты первого порядка [math]\displaystyle< C_k^2 >[/math] на второй поддиагонали и приводит к построению матрицы, которая возникает в связи с производными и интегралами от гауссовской функции ошибок:
Если обратить эту матрицу (например, снова беря экспоненту, но с другим знаком), то знаки коэффициентов меняются и дают коэффициенты производных гауссовской функции ошибок.
Другой вариант может быть получен при расширении исходной матрицы на отрицательные числа:
От действий над матрицами к пониманию их сути…
Очень уважаю людей, которые имеют смелость заявить, что они что-то не понимают. Сам такой. То, что не понимаю, — обязательно должен изучить, осмыслить, понять. Статья «Математика на пальцах», и особенно матричная запись формул, заставили меня поделиться своим небольшим, но, кажется, немаловажным опытом работы с матрицами.
Лет эдак 20 назад довелось мне изучать высшую математику в вузе, и начинали мы с матриц (пожалуй, как и все студенты того времени). Почему-то считается, что матрицы — самая лёгкая тема в курсе высшей математики. Возможно — потому, что все действия с матрицами сводятся к знанию способов расчёта определителя и нескольких формул, построенных — опять же, на определителе. Казалось бы, всё просто. Но… Попробуйте ответить на элементарный вопрос — что такое определитель, что означает число, которое вы получаете при его расчёте? (подсказка: вариант типа «определитель — это число, которое находится по определённым правилам» не является правильным ответом, поскольку говорит о методе получения, а не о самой сути определителя). Сдаётесь? — тогда читаем дальше.
Сразу хочу сказать, что я не математик ни по образованию, ни по должности. Разве что мне интересна суть вещей, и я порой пытаюсь до них «докопаться». Так же было и с определителем: нужно было разобраться со множественной регрессией, а в этом разделе эконометрики практически всё делается через… матрицы, будь они неладны. Вот и пришлось мне самому провести небольшое исследование, поскольку ни один из знакомых математиков не дал внятного ответа на поставленный вопрос, изначально звучавший как «что такое определитель». Все утверждали, что определитель — это такое число, которое особым образом посчитано, и если оно равно нулю, то… В общем, как в любом учебнике по линейной алгебре. Спасибо, проходили.
Если какую-то идею придумал один человек, то другой человек должен быть в состоянии её понять (правда, для этого порой приходится вооружаться дополнительными знаниями). Обращение к «великому и могучему» поисковику показало, что «площадь параллелограмма равна модулю определителя матрицы, образованной векторами — сторонами параллелограмма». Говоря простым языком, если матрица — это способ записи системы уравнений, то каждое уравнение в отдельности описывает вектор. Построив из точки начала координат векторы, заданные в матрице, мы таким образом зададим в пространстве некоторую фигуру. Если наше пространство одномерное, то фигура — это отрезок; если двумерное — то фигура — параллелограмм, и так далее.
Получается, что для одномерного пространства определитель — это длина отрезка, для плоскости — площадь фигуры, для трёхмерной фигуры — её объём… дальше идут n-мерные пространства, вообразить которые нам не дано. Если объём фигуры (то есть определитель для матрицы 3*3) равен нулю, то это означает, что сама фигура не является трёхмерной (она может быть при этом двухмерной, одномерной или вообще представлять собой точку). Ранг матрицы — это истинная (максимальная) размерность пространства, для которого определитель не равен нулю.
Так, с определителем почти всё понятно: он определяет «объёмность» фигуры, образованной описанными системой уравнений векторами (хотя непонятно, почему его значение не зависит от того, имеем мы дело с исходной матрицей, или с транспонированной — возможно, транспонирование — это вид аффинного преобразования?). Теперь нужно разобраться с действиями над матрицами…
Если матрица — это система уравнений (а иначе зачем нам таблица каких-то цифр, не имеющих к реальности никакого отношения?), то мы можем с ней делать разные вещи. Например, можем сложить две строки одной и той же матрицы, или умножить строку на число (то есть каждый коэффициент строки умножаем на одно и то же число). Если у нас есть две матрицы с одинаковыми размерностями, то мы их можем сложить (главное, чтобы при этом мы не сложили бульдога с носорогом — но разве математики, разрабатывая теорию матриц, думали о таком варианте развития событий?). Интуитивно понятно, тем более что в линейной алгебре иллюстрациями подобных операций являются системы уравнений.
Однако в чём смысл умножения матриц? Как я могу умножить одну систему уравнений на другую? Какой смысл будет иметь то, что я получу в этом случае? Почему для умножения матриц неприменимо переместительное правило (то есть произведение матриц В*А не то что не равно произведению А*В, но и не всегда осуществимо)? Почему, если мы перемножим матрицу на вектор-столбец, то получим вектор-столбец, а если перемножим вектор-строку на матрицу, то получим вектор-строку?
Ну, тут уж не то что Википедия, — тут даже современные учебники по линейной алгебре бессильны дать какое-либо внятное объяснение. Поскольку изучение чего-либо по принципу «вы сначала поверьте — а поймёте потом» — не для меня, копаю в глубь веков (точнее — читаю учебники первой половины XX века) и нахожу интересную фразу…
В книгах об этом напрямую не говорится, но получается, что векторам, параллельным некоторой плоскости, необязательно лежать на этой плоскости. То есть они могут находиться в трёхмерном пространстве где угодно, но если они параллельны именно этой плоскости, то они образуют двумерное пространство… Из приходящих мне на ум аналогий — фотография: трёхмерный мир представлен на плоскости, при этом вектору, параллельному матрице (или плёнке) фотоаппарата, будет соответствовать такой же вектор на картинке (при условии соблюдении масштаба 1:1). Отображение трёхмерного мира на плоскости «убирает» одно измерение («глубину» картинки). Если я правильно понял сложные математические концепции, перемножение двух матриц как раз и представляет собой подобное отражение одного пространства в другом. Поэтому, если отражение пространства А в пространстве В возможно, то допустимость отражения пространства В в пространстве А — не гарантируется.
Любая статья заканчивается в тот момент, когда автору надоедает её писать. Поскольку я не ставил перед собой цели объять необъятное, а исключительно хотел понять суть описанных операций над матрицами и то, как именно матрицы связаны с решаемыми мной системами уравнений, я не полез в дальнейшие дебри линейной алгебры, а вернулся к эконометрике и множественной регрессии, но сделал это уже более осознанно. Понимая, что и зачем я делаю и почему только так, а не иначе. То, что у меня получилось в этом материале, можно озаглавить как «глава о сути основных операций линейной алгебры, которую почему-то забыли напечатать в учебниках». Но ведь мы же не читаем учебников, правда? Если честно, когда я учился в университете, мне очень не хватало именно понимания затронутых здесь вопросов, поэтому я надеюсь, что, изложив этот непростой материал по возможности простыми словами, я делаю доброе дело и помогаю кому-то вникнуть в саму суть матричной алгебры, переведя операции над матрицами из раздела «камлание с бубном» в раздел «практические инструменты, применяемые осознанно».