матрица НОД

В математике матрица наибольшего общего делителя (иногда сокращенно матрица НОД ) — это матрица , которую также можно назвать матрицей Смита . Исследование было начато HJS Smith (1875). Новое вдохновение началось со статьи Bourque & Ligh (1992). Это привело к интенсивным исследованиям сингулярности и делимости матриц типа НОД. Краткий обзор статей по матрицам типа НОД до этого времени представлен в Haukkanen, Wang & Sillanpää (1997).

Определение

Пусть будет списком положительных целых чисел. Тогда матрица, имеющая наибольший общий делитель в качестве своего элемента, называется матрицей НОД на . Матрица НОК определяется аналогично. ^{[1] [2]} ${\displaystyle S=(x_{1},x_{2},\ldots ,x_{n})}$ ${\displaystyle n\times n}$ ${\displaystyle (S)}$ ${\displaystyle \gcd(x_{i},x_{j})}$ ${\displaystyle ij}$ ${\displaystyle S}$ ${\displaystyle [S]}$

Изучение матриц типа НОД берет начало от Смита (1875), который оценил определитель некоторых матриц НОД и НОК. Смит показал, среди прочего, что определитель матрицы равен , где — функция Эйлера . ^[3] ${\displaystyle n\times n}$ ${\displaystyle (\gcd(i,j))}$ ${\displaystyle \phi (1)\phi (2)\cdots \phi (n)}$ ${\displaystyle \phi }$

Гипотеза Бурка–Лига

Бурк и Лай (1992) предположили, что матрица НОК на НОД-замкнутом множестве невырожденна. ^[1] Эта гипотеза была опровергнута Хаукканеном, Ваном и Силланпяей (1997), а затем Хонгом (1999). ^{[4] [2]} Решеточно-теоретический подход предложен Корки, Маттилой и Хаукканеном (2019). ^[5] ${\displaystyle S}$

Контрпример, представленный в Haukkanen, Wang & Sillanpää (1997), а в Hong (1999) — Контрпример, состоящий из нечетных чисел, — . Его диаграмма Хассе представлена ​​справа ниже. ${\displaystyle S=\{1,2,3,4,5,6,10,45,180\}}$ ${\displaystyle S=\{1,2,3,5,36,230,825,227700\}.}$ ${\displaystyle S=\{1,3,5,7,195,291,1407,4025,1020180525\}}$

Структуры кубического типа этих множеств относительно отношения делимости объясняются в работе Korkee, Mattila & Haukkanen (2019).

Диаграмма Хассе нечетного замкнутого множества НОД, матрица НОК которого является вырожденной

Делимость

Пусть будет факторно замкнутым множеством. Тогда матрица НОД делит матрицу НОК в кольце матриц над целыми числами, то есть существует целочисленная матрица такая, что , см. Bourque & Ligh (1992). Поскольку матрицы и симметричны, то имеем . Таким образом, делимость справа совпадает с делимостью слева. Таким образом, мы можем использовать термин делимость. ${\displaystyle S=(x_{1},x_{2},\ldots ,x_{n})}$ ${\displaystyle (S)}$ ${\displaystyle [S]}$ ${\displaystyle n\times n}$ ${\displaystyle B}$ ${\displaystyle [S]=B(S)}$ ${\displaystyle (S)}$ ${\displaystyle [S]}$ ${\displaystyle [S]=(S)B^{T}}$

В литературе имеется большое количество обобщений и аналогов этого основного результата делимости.

Матричные нормы

Некоторые результаты по нормам матриц типа НОД представлены в литературе. Два основных результата касаются асимптотического поведения нормы матрицы НОД и НОК на . ^[6] ${\displaystyle \ell _{p}}$ ${\displaystyle S=\{1,2,\dots ,n\}}$

При этом норма матрицы определяется как ${\displaystyle p\in \mathbb {N} ^{+}}$ ${\displaystyle \ell _{p}}$ ${\displaystyle n\times n}$ ${\displaystyle A}$

${\displaystyle \Vert A\Vert _{p}=\left(\sum _{i=1}^{n}\sum _{j=1}^{n}|a_{ij}|^{p}\right)^{1/p}.}$

Пусть . Если , то ${\displaystyle S=\{1,2,\dots ,n\}}$ ${\displaystyle p\geq 2}$

${\displaystyle \Vert (S)\Vert _{p}=C_{p}^{1/p}n^{1+(1/p)}+O((n^{(1/p)-p}E_{p}(n)),}$

где

${\displaystyle C_{p}:={\frac {2\zeta (p)-\zeta (p+1)}{(p+1)\zeta (p+1)}}}$

и для и . Далее, если , то ${\displaystyle E_{p}(x)=x^{p}}$ ${\displaystyle p>2}$ ${\displaystyle E_{2}(x)=x^{2}\log x}$ ${\displaystyle p\geq 1}$

${\displaystyle \Vert [S]\Vert _{p}=D_{p}^{1/p}n^{2+(2/p)}+O((n^{(2/p)+1}(\log n)^{2/3}(\log \log n)^{4/3}),}$

где

${\displaystyle D_{p}:={\frac {\zeta (p+2)}{(p+1)^{2}\zeta (p)}}.}$

Факторизации

Пусть будет арифметической функцией, и пусть будет набором различных положительных целых чисел. Тогда матрица называется матрицей НОД на , связанной с . Матрица НОК на , связанная с , определяется аналогично. Можно также использовать обозначения и . ${\displaystyle f}$ ${\displaystyle S=(x_{1},x_{2},\ldots ,x_{n})}$ ${\displaystyle (S)_{f}=(f(\gcd(x_{i},x_{j}))}$ ${\displaystyle S}$ ${\displaystyle f}$ ${\displaystyle [S]_{f}}$ ${\displaystyle S}$ ${\displaystyle f}$ ${\displaystyle (S)_{f}=f(S)}$ ${\displaystyle [S]_{f}=f[S]}$

Пусть — замкнутое множество НОД. Тогда ${\displaystyle S}$

${\displaystyle (S)_{f}=E\Delta E^{T},}$

где матрица определяется как ${\displaystyle E}$ ${\displaystyle n\times n}$

${\displaystyle e_{ij}={\begin{cases}1&{\mbox{if }}x_{j}\,\mid \,x_{i},\\0&{\mbox{otherwise}}\end{cases}}}$

и — диагональная матрица, диагональные элементы которой равны ${\displaystyle \Delta }$ ${\displaystyle n\times n}$

${\displaystyle \delta _{i}=\sum _{d\mid x_{i} \atop {d\nmid x_{t} \atop x_{t}<x_{i}}}(f\star \mu )(d).}$

Здесь — свертка Дирихле, а — функция Мёбиуса. ${\displaystyle \star }$ ${\displaystyle \mu }$

Далее, если — мультипликативная функция и всегда ненулевая, то ${\displaystyle f}$

${\displaystyle [S]_{f}=\Lambda E\Delta ^{\prime }E^{T}\Lambda ,}$

где и — диагональные матрицы, диагональные элементы которых равны и ${\displaystyle \Lambda }$ ${\displaystyle \Delta '}$ ${\displaystyle n\times n}$ ${\displaystyle \lambda _{i}=f(x_{i})}$

${\displaystyle \delta _{i}^{\prime }=\sum _{d\vert x_{i} \atop {d\nmid x_{t} \atop x_{t}<x_{i}}}({\frac {1}{f}}\star \mu )(d).}$

Если факторно замкнуто, то и . ^[6] ${\displaystyle S}$ ${\displaystyle \delta _{i}=(f\star \mu )(x_{i})}$ ${\displaystyle \delta _{i}^{\prime }=({\frac {1}{f}}\star \mu )(x_{i})}$

Ссылки

1. Бурк, К.; Лиг, С. (1992). «О матрицах НОД и НОК». Линейная алгебра и ее приложения . 174 : 65–74. doi : 10.1016/0024-3795(92)90042-9 .
2. Hong, S. (1999). «О гипотезе Бурка–Лая о матрицах наименьшего общего кратного». Журнал алгебры . 218 : 216–228. doi : 10.1006/jabr.1998.7844 .
3. Смит, Г. Дж. С. (1875). «О значении некоторого арифметического определителя». Труды Лондонского математического общества . 1 : 208–213. doi :10.1112/plms/s1-7.1.208.
4. Хаукканен, П.; Ван, Дж.; Силланпяя, Дж. (1997). «Об определителе Смита». Линейная алгебра и ее приложения . 258 : 251–269. дои : 10.1016/S0024-3795(96)00192-9 .
5. Корки, И.; Маттила, М.; Хаукканен, П. (2019). «Решеточно-теоретический подход к гипотезе Бурка–Лая». Линейная и мультилинейная алгебра . 67 (12): 2471–2487. arXiv : 1403.5428 . doi :10.1080/03081087.2018.1494695. S2CID  117112282.
6. Haukkanen, P.; Toth, L. (2018). «Инерция, положительная определенность и норма ℓp матриц GCD и LCM и их унитарных аналогов». Линейная алгебра и ее приложения . 558 : 1–24. doi : 10.1016/j.laa.2018.08.022 .