Матрица Паскаля

Матрица Паскаля

19.12.2020


В математике, особенно в теории матриц и комбинаторике, матрица Паскаля — это бесконечная матрица, элементами которой являются биномиальные коэффициенты. Существует три варианта расположения элементов в матрице: в виде верхнетреугольной, нижнетреугольной или симметричной матрицы. 5×5-ограничения таких матриц имеют вид:

Верхнетреугольная матрица:

U 5 = ( 1 1 1 1 1 0 1 2 3 4 0 0 1 3 6 0 0 0 1 4 0 0 0 0 1 ) ; {displaystyle U_{5}={egin{pmatrix}1&1&1&1&1&1&2&3&4&0&1&3&6&0&0&1&4&0&0&0&1end{pmatrix}};}

нижнетреугольная матрица

L 5 = ( 1 0 0 0 0 1 1 0 0 0 1 2 1 0 0 1 3 3 1 0 1 4 6 4 1 ) ; {displaystyle L_{5}={egin{pmatrix}1&0&0&0&01&1&0&0&01&2&1&0&01&3&3&1&01&4&6&4&1end{pmatrix}};}

симметричная матрица

S 5 = ( 1 1 1 1 1 1 2 3 4 5 1 3 6 10 15 1 4 10 20 35 1 5 15 35 70 ) . {displaystyle S_{5}={egin{pmatrix}1&1&1&1&11&2&3&4&51&3&6&10&151&4&10&20&351&5&15&35&70end{pmatrix}}.}

Эти матрицы удовлетворяют соотношению Sn = LnUn. Отсюда легко видеть, что все три матрицы имеют единичный определитель, так как определитель треугольных матриц Ln и Un равен произведению их диагональных элементов. Другими словами, матрицы Sn, Ln, и Un унимодулярны. След матриц Ln и Un равен n.

Элементы симметричной матрицы Паскаля имеют вид:

S i j = ( n r ) = n ! r ! ( n − r ) ! , n = i + j , r = i . {displaystyle S_{ij}={n choose r}={frac {n!}{r!(n-r)!}},quad n=i+j,quad r=i.}

Эквивалентно:

S i j = C i + j i = ( i + j ) ! ( i ) ! ( j ) ! . {displaystyle S_{ij}= extstyle C_{i+j}^{i}={frac {(i+j)!}{(i)!(j)!}}.}

Таким образом, след матрицы Sn равен

tr ( S n ) = ∑ i = 1 n [ 2 ( i − 1 ) ] ! [ ( i − 1 ) ! ] 2 = ∑ k = 0 n − 1 ( 2 k ) ! ( k ! ) 2 {displaystyle { ext{tr}}(S_{n})=sum _{i=1}^{n}{frac {[2(i-1)]!}{[(i-1)!]^{2}}}=sum _{k=0}^{n-1}{frac {(2k)!}{(k!)^{2}}}}

в зависимости от n образуя последовательность: 1, 3, 9, 29, 99, 351, 1275, … последовательность A006134 в OEIS.

Построение

Матрица Паскаля может быть построена посредством взятия экспоненты от поддиагональной или наддиагональной матрицей специального вида. В следующем примере строятся матрицы 7×7, но этот метод работает для любых n×n-матриц Паскаля. (Точками обозначены нулевые элементы.)

L 7 = exp ⁡ ( [ . . . . . . . 1 . . . . . . . 2 . . . . . . . 3 . . . . . . . 4 . . . . . . . 5 . . . . . . . 6 . ] ) = [ 1 . . . . . . 1 1 . . . . . 1 2 1 . . . . 1 3 3 1 . . . 1 4 6 4 1 . . 1 5 10 10 5 1 . 1 6 15 20 15 6 1 ] ; U 7 = exp ⁡ ( [ . 1 . . . . . . . 2 . . . . . . . 3 . . . . . . . 4 . . . . . . . 5 . . . . . . . 6 . . . . . . . ] ) = [ 1 1 1 1 1 1 1 . 1 2 3 4 5 6 . . 1 3 6 10 15 . . . 1 4 10 20 . . . . 1 5 15 . . . . . 1 6 . . . . . . 1 ] ; ∴ S 7 = exp ⁡ ( [ . . . . . . . 1 . . . . . . . 2 . . . . . . . 3 . . . . . . . 4 . . . . . . . 5 . . . . . . . 6 . ] ) exp ⁡ ( [ . 1 . . . . . . . 2 . . . . . . . 3 . . . . . . . 4 . . . . . . . 5 . . . . . . . 6 . . . . . . . ] ) = [ 1 1 1 1 1 1 1 1 2 3 4 5 6 7 1 3 6 10 15 21 28 1 4 10 20 35 56 84 1 5 15 35 70 126 210 1 6 21 56 126 252 462 1 7 28 84 210 462 924 ] . {displaystyle {egin{array}{lll}&L_{7}=exp left(left[{egin{smallmatrix}.&.&.&.&.&.&.1&.&.&.&.&.&..&2&.&.&.&.&..&.&3&.&.&.&..&.&.&4&.&.&..&.&.&.&5&.&..&.&.&.&.&6&.end{smallmatrix}} ight] ight)=left[{egin{smallmatrix}1&.&.&.&.&.&.1&1&.&.&.&.&.1&2&1&.&.&.&.1&3&3&1&.&.&.1&4&6&4&1&.&.1&5&10&10&5&1&.1&6&15&20&15&6&1end{smallmatrix}} ight];quad \&U_{7}=exp left(left[{egin{smallmatrix}.&1&.&.&.&.&..&.&2&.&.&.&..&.&.&3&.&.&..&.&.&.&4&.&..&.&.&.&.&5&..&.&.&.&.&.&6.&.&.&.&.&.&.end{smallmatrix}} ight] ight)=left[{egin{smallmatrix}1&1&1&1&1&1&1.&1&2&3&4&5&6.&.&1&3&6&10&15.&.&.&1&4&10&20.&.&.&.&1&5&15.&.&.&.&.&1&6.&.&.&.&.&.&1end{smallmatrix}} ight];\ herefore &S_{7}=exp left(left[{egin{smallmatrix}.&.&.&.&.&.&.1&.&.&.&.&.&..&2&.&.&.&.&..&.&3&.&.&.&..&.&.&4&.&.&..&.&.&.&5&.&..&.&.&.&.&6&.end{smallmatrix}} ight] ight)exp left(left[{egin{smallmatrix}.&1&.&.&.&.&..&.&2&.&.&.&..&.&.&3&.&.&..&.&.&.&4&.&..&.&.&.&.&5&..&.&.&.&.&.&6.&.&.&.&.&.&.end{smallmatrix}} ight] ight)=left[{egin{smallmatrix}1&1&1&1&1&1&11&2&3&4&5&6&71&3&6&10&15&21&281&4&10&20&35&56&841&5&15&35&70&126&2101&6&21&56&126&252&4621&7&28&84&210&462&924end{smallmatrix}} ight].end{array}}}

Важно отметить, что нельзя просто положить exp(A)exp(B) = exp(A + B) для n×n-матирц A и B, такое равенство имеет место только при AB = BA (то есть когда матрицы A и B коммутируют). В приведённом построении симметричных матриц Паскаля наддиагональные и поддиагональные матрицы не коммутируют. Таким образом, нельзя провести (возможно) ожидаемое упрощение, включающее сумму матриц.

Полезное свойство поддиагональных и наддиагональных матриц, используемое в данном построении - это их нильпотеность, то есть при возведении в достаточно большую целую степень они вырождаются в нулевую матрицу. (Смотри матрица сдвига для дальнейших деталей.) Так как обобщённые n×n-матрицы сдвига, которые тут используются, становятся равными нулю при возведении в степень n, то при вычислении матричной экспоненты необходимо рассматривать только первый n + 1 член бесконечного ряда, чтобы получить точный результат.

Варианты

Интересные варианты могут быть получены посредством очевидных модификаций матриц PL7, от которых берётся экспонента.

Первый пример ниже использует квадраты значений в PL7 вместо исходных и приводит к построению 7×7-матрицы Лагерра (матрицы, элементами которой являются полиномы Лагерра).

L A G 7 = exp ⁡ ( [ . . . . . . . 1 . . . . . . . 4 . . . . . . . 9 . . . . . . . 16 . . . . . . . 25 . . . . . . . 36 . ] ) = [ 1 . . . . . . 1 1 . . . . . 2 4 1 . . . . 6 18 9 1 . . . 24 96 72 16 1 . . 120 600 600 200 25 1 . 720 4320 5400 2400 450 36 1 ] ; {displaystyle {egin{array}{lll}&LAG_{7}=exp left(left[{egin{smallmatrix}.&.&.&.&.&.&.1&.&.&.&.&.&..&4&.&.&.&.&..&.&9&.&.&.&..&.&.&16&.&.&..&.&.&.&25&.&..&.&.&.&.&36&.end{smallmatrix}} ight] ight)=left[{egin{smallmatrix}1&.&.&.&.&.&.1&1&.&.&.&.&.2&4&1&.&.&.&.6&18&9&1&.&.&.24&96&72&16&1&.&.120&600&600&200&25&1&.720&4320&5400&2400&450&36&1end{smallmatrix}} ight];quad end{array}}}

(Матрица Лагерра на самом деле использует другое масштабирование и знаки некоторых коэффициентов.)

Второй пример использует v(v + 1) в качестве элементов, если v— элементы исходной матрицы. Он приводит к построению 7×7-матрицы Лаха (матрицы с элементами в виде чисел Лаха).

L A H 7 = exp ⁡ ( [ . . . . . . . 2 . . . . . . . 6 . . . . . . . 12 . . . . . . . 20 . . . . . . . 30 . . . . . . . 42 . ] ) = [ 1 . . . . . . . 2 1 . . . . . . 6 6 1 . . . . . 24 36 12 1 . . . . 120 240 120 20 1 . . . 720 1800 1200 300 30 1 . . 5040 15120 12600 4200 630 42 1 . 40320 141120 141120 58800 11760 1176 56 1 ] ; {displaystyle {egin{array}{lll}&LAH_{7}=exp left(left[{egin{smallmatrix}.&.&.&.&.&.&.2&.&.&.&.&.&..&6&.&.&.&.&..&.&12&.&.&.&..&.&.&20&.&.&..&.&.&.&30&.&..&.&.&.&.&42&.end{smallmatrix}} ight] ight)=left[{egin{smallmatrix}1&.&.&.&.&.&.&.2&1&.&.&.&.&.&.6&6&1&.&.&.&.&.24&36&12&1&.&.&.&.120&240&120&20&1&.&.&.720&1800&1200&300&30&1&.&.5040&15120&12600&4200&630&42&1&.40320&141120&141120&58800&11760&1176&56&1end{smallmatrix}} ight];quad end{array}}}

Использование v(v − 1) приводит к диагональному сдвигу вниз-вправо.

Третий пример использует квадрат исходной PL7-матрицы, делёный на 2, другими словами: биномиальные коэффициенты первого порядка C k 2 {displaystyle C_{k}^{2}} на второй поддиагонали и приводит к построению матрицы, которая возникает в связи с производными и интегралами от гауссовской функции ошибок:

G S 7 = exp ⁡ ( [ . . . . . . . . . . . . . . 1 . . . . . . . 3 . . . . . . . 6 . . . . . . . 10 . . . . . . . 15 . . ] ) = [ 1 . . . . . . . 1 . . . . . 1 . 1 . . . . . 3 . 1 . . . 3 . 6 . 1 . . . 15 . 10 . 1 . 15 . 45 . 15 . 1 ] ; {displaystyle {egin{array}{lll}&GS_{7}=exp left(left[{egin{smallmatrix}.&.&.&.&.&.&..&.&.&.&.&.&.1&.&.&.&.&.&..&3&.&.&.&.&..&.&6&.&.&.&..&.&.&10&.&.&..&.&.&.&15&.&.end{smallmatrix}} ight] ight)=left[{egin{smallmatrix}1&.&.&.&.&.&..&1&.&.&.&.&.1&.&1&.&.&.&..&3&.&1&.&.&.3&.&6&.&1&.&..&15&.&10&.&1&.15&.&45&.&15&.&1end{smallmatrix}} ight];quad end{array}}}

Если обратить эту матрицу (например, снова беря экспоненту, но с другим знаком), то знаки коэффициентов меняются и дают коэффициенты производных гауссовской функции ошибок.

Другой вариант может быть получен при расширении исходной матрицы на отрицательные числа:

exp ⁡ ( [ . . . . . . . . . . . . − 5 . . . . . . . . . . . . − 4 . . . . . . . . . . . . − 3 . . . . . . . . . . . . − 2 . . . . . . . . . . . . − 1 . . . . . . . . . . . . 0 . . . . . . . . . . . . 1 . . . . . . . . . . . . 2 . . . . . . . . . . . . 3 . . . . . . . . . . . . 4 . . . . . . . . . . . . 5 . ] ) = [ 1 . . . . . . . . . . . − 5 1 . . . . . . . . . . 10 − 4 1 . . . . . . . . . − 10 6 − 3 1 . . . . . . . . 5 − 4 3 − 2 1 . . . . . . . − 1 1 − 1 1 − 1 1 . . . . . . . . . . . 0 1 . . . . . . . . . . . 1 1 . . . . . . . . . . 1 2 1 . . . . . . . . . 1 3 3 1 . . . . . . . . 1 4 6 4 1 . . . . . . . 1 5 10 10 5 1 ] . {displaystyle {egin{array}{lll}&exp left(left[{egin{smallmatrix}.&.&.&.&.&.&.&.&.&.&.&.-5&.&.&.&.&.&.&.&.&.&.&..&-4&.&.&.&.&.&.&.&.&.&..&.&-3&.&.&.&.&.&.&.&.&..&.&.&-2&.&.&.&.&.&.&.&..&.&.&.&-1&.&.&.&.&.&.&..&.&.&.&.&0&.&.&.&.&.&..&.&.&.&.&.&1&.&.&.&.&..&.&.&.&.&.&.&2&.&.&.&..&.&.&.&.&.&.&.&3&.&.&..&.&.&.&.&.&.&.&.&4&.&..&.&.&.&.&.&.&.&.&.&5&.end{smallmatrix}} ight] ight)=left[{egin{smallmatrix}1&.&.&.&.&.&.&.&.&.&.&.-5&1&.&.&.&.&.&.&.&.&.&.10&-4&1&.&.&.&.&.&.&.&.&.-10&6&-3&1&.&.&.&.&.&.&.&.5&-4&3&-2&1&.&.&.&.&.&.&.-1&1&-1&1&-1&1&.&.&.&.&.&..&.&.&.&.&0&1&.&.&.&.&..&.&.&.&.&.&1&1&.&.&.&..&.&.&.&.&.&1&2&1&.&.&..&.&.&.&.&.&1&3&3&1&.&..&.&.&.&.&.&1&4&6&4&1&..&.&.&.&.&.&1&5&10&10&5&1end{smallmatrix}} ight].end{array}}}