«
»

Определитель Смита

8 Январь 2015, 21:53

Генри Джон Стивен Смит (1826–1883) — английский математик, известный прежде всего своими работами по элементарным делителям, квадратичным формам и формулой Смита — Минковского — Зигеля для масс. В теории матриц используется нормальная форма Смита для матрицы.

Определитель Смита имеет вид

    \[D=\left|\begin{array}{ccccc} (1,1)&(1,2)&(1,3)&\ldots&(1,n)\\ (2,1)&(2,2)&(2,3)&\ldots&(2,n)\\ (3,1)&(3,2)&(3,3)&\ldots&(3,n)\\ \ldots&&&&\\ (n,1)&(n,2)&(n,3)&\ldots&(n,n) \end{array}\right|,\]

где (i,j) обозначает наибольший общий делитель чисел i и j.

А равен этот определитель довольно красивой величине:

    \[D=\varphi(1)\varphi(2)\varphi(3)\ldots\varphi(n),\]


где \varphi(n) — функция Эйлера натурального числа n (т.е. количество чисел, не превосходящих n и взаимно простых с n).

Докажем сначала, что любое натуральное число n представимо в виде суммы значений функции Эйлера от его натуральных делителей:

    \[n=\sum_{d|n}\varphi(d)\]

(здесь d|n обозначает, что d — делитель n).

Пусть разложение числа n на простые множители имеет вид

    \[n=p_1^{\alpha_1}p_2^{\alpha_2}\ldots p_m^{\alpha_m}.\]

Тогда любой делитель d числа n может быть записан в виде

    \[d=p_1^{\beta_1}p_2^{\beta_2}\ldots p_m^{\beta_m},\]

где 0\le\beta_1\le\alpha_1,0\le\beta_2\le\alpha_2,\ldots,0\le\beta_m\le\alpha_m.

В силу мультипликативности функции Эйлера имеем

    \[\varphi(d)=\varphi(p_1^{\beta_1}p_2^{\beta_2}\ldots p_m^{\beta_m})=\varphi(p_1^{\beta_1})\varphi(p_2^{\beta_2})\ldots \varphi(p_m^{\beta_m}).\]

Теперь рассмотрим выражение

    \[(1+\varphi(p_1)+\varphi(p_1^2)+\ldots+\varphi(p_1^{\alpha_1}))(1+\varphi(p_2)+\varphi(p_2^2)+\ldots+\varphi(p_2^{\alpha_2}))\times\ldots\]

    \[\times(1+\varphi(p_m)+\varphi(p_m^2)+\ldots+\varphi(p_m^{\alpha_1}))\]

После раскрытия скобок с учетом предыдущего замечания получаем, что это выражение равно \displaystyle \sum_{d|n}\varphi(d).

Далее воспользуемся формулой для вычисления функции Эйлера степени простого числа

    \[\varphi(p^k)=p^k-p^{k-1}\]

(см. здесь):

    \[\sum_{d|n}\varphi(d)=(1+(p_1-1)+(p_1^2-p_1)+\ldots+(p_1^{\alpha_1}-p_1^{\alpha_1-1}))\times\]

    \[\times(1+(p_2-1)+(p_2^2-p_2)+\ldots+(p_2^{\alpha_2}-p_2^{\alpha_2-1}))\times\ldots\]

    \[\times(1+(p_m-1)+(p_m^2-p_m)+\ldots+(p_m^{\alpha_m}-p_m^{\alpha_m-1}))\]

и после приведения подобных слагаемых в каждой большой скобке получим

    \[\sum_{d|n}\varphi(d)=p_1^{\alpha_1}p_2^{\alpha_2}\ldots p_m^{\alpha_m}=n.\]

Отсюда следует, что

    \[(i,j)=\sum_{d|(i,j)}\varphi(d).\]

Суммирование здесь производится по всем значениям d, которые являются делителями (i,j), иначе говоря, по всем общим делителям чисел i и j. Поэтому можно представить (i,j) в следующем виде:

    \[(i,j)=a_{i1}a_{j1}\varphi(1)+a_{i2}a_{j2}\varphi(2)+a_{i3}a_{j3}\varphi(3)+\ldots+a_{in}a_{jn}\varphi(n),\]

условившись считать a_{ij}=1, когда i делится на j, и a_{ij}=0, когда i не делится на j (так что для всех значений i< j a_{ij}=0). В самом деле, при этих условиях коэффициент a_{i\nu}a_{j\nu} при \varphi(\nu) будет равен 1, когда i и j оба делятся на \nu, и равен нулю, когда \nu не является общим делителем чисел i и j, так что в правой части приведенной выше формулы будем иметь \sum\varphi(\nu), взятую по всем общим делителям \nu чисел i и j. Тогда

    \[D=\left|\begin{array}{ccccc} a_{11}&a_{12}&a_{13}&\ldots&a_{1n}\\ a_{21}&a_{22}&a_{23}&\ldots&a_{2n}\\ a_{31}&a_{32}&a_{33}&\ldots&a_{3n}\\ \ldots&&&&\\ a_{n1}&a_{n2}&a_{n3}&\ldots&a_{nn} \end{array}\right|\cdot\left|\begin{array}{ccccc} a_{11}\varphi(1)&a_{12}\varphi(2)&a_{13}\varphi(3)&\ldots&a_{1n}\varphi(n)\\ a_{21}\varphi(1)&a_{22}\varphi(2)&a_{23}\varphi(3)&\ldots&a_{2n}\varphi(n)\\ a_{31}\varphi(1)&a_{32}\varphi(2)&a_{33}\varphi(3)&\ldots&a_{3n}\varphi(n)\\ \ldots&&&&\\ a_{n1}\varphi(1)&a_{n2}\varphi(2)&a_{n3}\varphi(3)&\ldots&a_{nn}\varphi(n) \end{array}\right|=\]

    \[=\left|\begin{array}{ccccc} 1&0&0&0&\ldots\\ 1&1&0&0&\ldots\\ 1&0&1&0&\ldots\\ 1&1&0&1&\ldots\\ \ldots&&&& \end{array}\right|\cdot\left|\begin{array}{ccccc} a_{11}\varphi(1)&0&0&\ldots&0\\ a_{21}\varphi(1)&a_{22}\varphi(2)&0&\ldots&0\\ a_{31}\varphi(1)&a_{32}\varphi(2)&a_{33}\varphi(3)&\ldots&0\\ \ldots&&&&\\ a_{n1}\varphi(1)&a_{n2}\varphi(2)&a_{n3}\varphi(3)&\ldots&a_{nn}\varphi(n) \end{array}\right|=\]

    \[=\varphi(1)\varphi(2)\ldots\varphi(n).\]

Источники: Чезаро Э. Элементарный учебник алгебраического анализа и исчисления бесконечно малых. Одесса, 1913.

И.М. Виноградов. Основы теории чисел. Лань, 2004.

http://en.wikipedia.org/wiki/Henry_John_Stephen_Smith

Теги: ,
Рубрика: Статьи по математике  |  Отзывы (RSS)  |  Трекбек

Оставьте свой отзыв

Добавить изображение