Алгебра · объяснение и практика
Что целочисленная матрица сохраняет сверх ранга: инвариантные множители Смита
Определить структуру фактор-группы целочисленной решётки по детерминантным делителям и отличить её от рационального ранга матрицы.

В теме Матрицы и комплексные числа: углубление · Учебная карта
Главная мысль
Столбцы целочисленной матрицы порождают подгруппу в Z^m. Инвариантные множители Смита описывают фактор по этой подгруппе: конечные циклические части и свободные направления. Их можно получить из НОД всех миноров каждого порядка.
Метод и постановка
Сначала закрепите кольцо коэффициентов. В отличие от решения системы над рациональными числами, деление строки на любое ненулевое число здесь не разрешено: обратное преобразование тоже должно иметь целые коэффициенты. Допустимые замены целочисленных базисов имеют определитель плюс или минус единица. Они сохраняют структуру решётки, а не только линейную зависимость столбцов.
Для каждого порядка k вычислите все квадратные миноры и найдите положительный НОД их определителей. Обозначим его Δₖ, а для нулевого порядка положим Δ₀=1. Пока НОД ненулевой, очередной инвариантный множитель равен Δₖ/Δₖ₋₁. Первый порядок, где все миноры нулевые, показывает превышение ранга. Для малой матрицы полный перебор миноров прозрачен и ограничен; для больших размеров потребовался бы другой вычислительный алгоритм.
Проверка и границы вывода
Полученные положительные множители образуют цепочку делимости: каждый делит следующий. Одного возрастающего порядка недостаточно, поэтому проверяйте именно остаток от деления соседних значений. Произведение первых k множителей должно вернуть Δₖ. Эти проверки связывают результат со всеми минорами, а не только с определителем полной квадратной матрицы.
Свободный ранг фактор-группы равен числу строк минус рангу образа. Каждый множитель больше единицы даёт конечную циклическую компоненту соответствующего порядка; множитель один даёт тривиальную компоненту. Если свободных направлений нет, индекс образа конечен и равен произведению ненулевых множителей. При свободной части индекс бесконечен, поэтому инструмент не выдаёт конечное число вместо него. Нулевая матрица оставляет все координатные направления свободными. Преобразующие матрицы базисов здесь не строятся: канонические инварианты не следует выдавать за конкретную замену координат.
Пример
Для матрицы [[2,4],[0,6]] НОД элементов равен двум, определитель равен двенадцати. Поэтому Δ₁=2, Δ₂=12 и множители равны 2,6. Фактор имеет вид Z/2Z ⊕ Z/6Z и содержит двенадцать классов.
Матрица diag(1,12) имеет тот же определитель и тот же рациональный ранг, но фактор циклический Z/12Z. В первом факторе каждый элемент имеет порядок не больше шести. Поэтому один определитель не заменяет полную цепочку инвариантов.
От чтения к действию
А теперь — вы
Частые вопросы
Почему нельзя обычное деление строки на два?
Оно обратимо над рациональными числами, но не над целыми: может изменить порождённую решётку и фактор-группу.
Возвращаются преобразующие матрицы U,V?
Нет. Вычисляются канонические инварианты через все миноры, без обещания конкретных целочисленных базисов.
Углублённый разбор
Целочисленная совместность через делимость в форме Смита
Диагональные инварианты сами по себе не решают систему с данной правой частью. Для целочисленной совместности нужно преобразовать и эту правую часть тем же унимодулярным оператором, после чего проверить делимость координат.
Перед началом: Целочисленная матрица; Унимодулярная замена базиса.
Преобразуйте уравнение, а не только матрицу
Пусть A — целочисленная матрица размера m×n и найдены целочисленные обратимые матрицы U,V с определителями±1 такие, что UAV=D. Умножение Ax=b на U и замена x=Vy превращают задачу в Dy=Ub. Обе замены взаимно однозначны на целых векторах, поскольку обратные U,V также целочисленны.
Первые r ненулевых диагональных элементов D обозначим d₁,…,dᵣ. В соответствующих координатах требуется dᵢyᵢ=cᵢ, где c=Ub. Поэтому dᵢ должен делить cᵢ. В оставшихся нулевых строках необходимо cᵢ=0. Только проверка этих условий одновременно даёт существование целого решения.
Нулевые столбцы дают целые параметры
Если проверки прошли, назначают yᵢ=cᵢ/dᵢ для i≤r. Координаты y после r свободны и принимают любые целые значения, затем возвращают x=Vy. При полном столбцовом ранге целое решение, если существует, единственно. При свободных направлениях получается аффинная целочисленная решётка, а не произвольное вещественное семейство.
Делимость простого НОД всех элементов A на каждую координату b обычно недостаточна. Она игнорирует связи между строками и размещение правой части относительно образа. По той же причине ненулевой определитель гарантирует единственное рациональное решение, но не целое. Матрицы преобразования нужны именно для сохранения этой информации.
Сертификат проверяется без доверия к алгоритму Смита
Готовые U,V,D можно проверить перемножением UAV=D и вычислением определителей U,V. Затем отдельно проверяют c=Ub и целочисленные условия. Такая проверка значительно проще общего алгоритма построения формы и обнаруживает ошибку направления замены x=Vy вместо неверного x=V⁻¹y.
При отрицательном результате полезно предъявить конкретную координату cᵢ, не делящуюся на dᵢ, либо ненулевую нулевую строку. Это короткое свидетельство несовместности. При положительном — подставить найденный x непосредственно в исходную Ax=b. Проверка только преобразованной системы могла бы повторить ошибку построения U или V.
Одна матрица и две правые части
Условие. Для A=[[4,6],[2,8]] даны U=[[0,1],[−1,2]],V=[[1,−4],[0,1]]. Решите над целыми Ax=b для b=(10,10) и b=(6,12).
- Определители U,V равны 1. Прямое произведение UAV=diag(2,10), поэтому допустимы целочисленные замены.
- Для b=(10,10) получаем c=Ub=(10,10), затем y=(5,1) и x=Vy=(1,1).
- Для b=(6,12) имеем c=(12,18). Число 18 не делится на 10, поэтому целого решения нет.
- Рациональное решение второй системы равно(−6/5,9/5), что не противоречит ненулевому определителю A. Для первой прямая подстановка возвращает(10,10).
Ответ. Первое целое решение x=(1,1); вторая система несовместна над целыми.
Проверка. Комбинация −первое уравнение+2·второе даёт 10x₂=−b₁+2b₂. Для второй правой части это 10x₂=18 — независимое точное препятствие целочисленности.
Где легко ошибиться. Не проверяйте делимость исходного b без матрицы U. Диагональ D относится к преобразованным координатам, и забытая замена правой части меняет задачу.
Проверьте понимание
Вопросы к этой главе
Одних инвариантных множителей достаточно?
Они описывают тип фактор-группы, но не положение данного b в ней. Для конкретного теста принадлежности образу нужны соответствующие преобразования либо другой сертификат.
Можно делить диагональную строку на dᵢ?
При решении да, если заранее проверена точная делимость правой части. Но такая операция не объявляется обратимой заменой целочисленного базиса для произвольных правых частей.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- SageMath: Dense matrices over the integer ring, smith_form
Официальная документация: прочитаны договор S=UAV, целочисленные преобразования и отличие возврата базисов от одних elementary_divisors. Собственные 2×2 матрица, преобразования и две правые части рассчитаны отдельно.
Канонические представители смежных классов целочисленной решётки
Треугольный целочисленный базис позволяет не только сосчитать классы, но и привести любой вектор к единственному представителю. Остатки нужно брать с учётом переноса между координатами, иначе полученный вектор попадёт в другой класс.
Перед началом: Столбцы решётки; Деление с остатком.
Приводите координаты снизу вверх
Пусть решётка L порождена столбцами верхнетреугольной невырожденной целочисленной H с положительной диагональю hᵢᵢ. В нижней координате влияет только последний столбец. Разделим её на hₙₙ, оставим остаток от 0 до hₙₙ−1, а соответствующее кратное последнего столбца вычтем из всего вектора.
Затем обработаем предпоследнюю координату. Вычитание этого столбца не меняет уже нормализованные нижние координаты, поскольку ниже диагонали стоят нули. Продолжаем вверх. Полученный r лежит в прямоугольнике 0≤rᵢ<hᵢᵢ, а исходный вектор отличается от него целочисленной комбинацией столбцов, поэтому класс по L сохранён.
Уникальность следует из последней ненулевой координаты
Пусть два представителя r,s из этого прямоугольника принадлежат одному классу: r−s=Hz. Нижняя координата даёт rₙ−sₙ=hₙₙzₙ. Её модуль меньше hₙₙ, значит zₙ=0 и rₙ=sₙ. Повторяя рассуждение выше, получаем все zᵢ=0 и r=s. Условия диапазона нужны для этого строгого неравенства.
Итак, остаточный прямоугольник содержит ровно по одному представителю каждого класса. Его число целых точек равно произведению диагональных элементов. Но задача приведения даёт больше, чем размер фактора: она позволяет сравнивать конкретные классы и строить свидетельство принадлежности разности решётке.
Независимые остатки не учитывают наклон столбца
Если вне диагонали есть ненулевые элементы, вычитание нижнего столбца меняет и верхние координаты. Поэтому покоординатное взятие исходного вектора по диагональным модулям обычно неверно. Нужно сначала применить перенос от уже найденного нижнего частного, а потом брать верхний остаток.
Для отрицательных координат используйте евклидово деление с неотрицательным остатком и положительным делителем. Усечение частного к нулю может оставить отрицательный остаток и нарушить каноничность. В общем базисе сначала нужна подходящая целочисленная треугольная форма; обычное рациональное исключение способно изменить решётку и для этой цели непригодно.
Две точки одного косого класса
Условие. L порождена столбцами(3,0) и(1,4). Найдите канонические представители в 0≤r₁<3,0≤r₂<4 для b=(14,11) и c=(−1,−1).
- Для b нижнее деление 11=2·4+3. Вычитаем два вторых столбца и получаем(12,3).
- Верхнее деление 12=4·3+0. Вычитаем четыре первых столбца; представитель равен(0,3).
- Для c имеем−1=(−1)·4+3. После вычитания минус одного второго столбца сразу получаем(0,3), верхнее частное нулевое.
- Представители совпали. Разность b−c=(15,12)=4(3,0)+3(1,4) действительно принадлежит L.
Ответ. Обе точки имеют канонический представитель(0,3).
Проверка. Для b разность b−(0,3)=4(3,0)+2(1,4). Ошибочный независимый остаток(2,3) не эквивалентен b: второе уравнение требует коэффициент 2, а первое тогда даёт 10/3 вместо целого.
Где легко ошибиться. Нельзя брать обе координаты исходного вектора независимо по диагонали. Вне диагонали столбец создаёт перенос, который сначала нужно вычесть из верхних координат.
Проверьте понимание
Вопросы к этой главе
Сам прямоугольник является параллелограммом базиса?
Необязательно. Здесь это набор канонических целых представителей классов, а не утверждение о совпадении геометрических фундаментальных областей выбранной формы.
Что делать при нулевом диагональном элементе?
Описанная конечная прямоугольная нормализация предполагает полный ранг. При вырожденном базисе остаются свободные направления, и конечного набора представителей для всего Zⁿ обычно нет.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- SageMath: Integer matrices, hermite_form
Официальная документация: прочитаны hermite_form и договор строкового преобразования U*A=H. Глава явно задаёт собственный верхнетреугольный СТОЛБЦОВЫЙ базис; правило остатков и доказательство единственности выведены отдельно, не приписывая Sage иную конвенцию.
Порядок элемента в факторе целочисленной решётки
Структура фактор-группы решётки не определяет порядок каждого её элемента без преобразования конкретного вектора. Диагональная форма Смита превращает этот запрос в несколько условий делимости. Наименьшее положительное число повторений получается через НОК, а ненулевая свободная координата делает порядок бесконечным.
Перед началом: Целочисленные унимодулярные преобразования; НОД, НОК и делимость.
Преобразовывать нужно и подгруппу, и выбранный элемент
Пусть столбцы целочисленной матрицы A порождают L=AZⁿ в Zᵐ. Порядок класса [v] в Zᵐ/L — наименьшее k>0, для которого kv∈L; при отсутствии такого числа порядок бесконечен. Нулевой класс имеет порядок один, поскольку уже один экземпляр принадлежит подгруппе.
Пусть даны унимодулярные U,V и D=UAV=diag(d₁,…,d_r,0,…), где положительные d_i делят следующие. Поскольку VZⁿ=Zⁿ, умножение на U переводит L в DZⁿ. Поэтому w=Uv — координаты нужного класса в диагональном факторе. Одни инварианты d_i без U не указывают, куда попал конкретный исходный v.
Каждая конечная координата даёт собственный период
В координате с модулем d_i условие возврата равно d_i|kw_i. Если g_i=НОД(d_i,w_i), оно равносильно d_i/g_i|k. Это следует после сокращения на g_i: оставшиеся целые числа взаимно просты, и оставшийся делитель должен делить k. При w_i=0 получаем период один.
Чтобы все конечные координаты вернулись одновременно, минимальный положительный k равен НОК чисел d_i/g_i. Произведение обычно завышает результат, потому что периоды могут иметь общие простые множители. Размер всей конечной группы равен произведению d_i, но отдельный элемент часто имеет существенно меньший порядок.
Свободные направления меняют качественный ответ
Для строк после ранга r диагональный образ содержит только нули. Поэтому условие kw_i=0 при положительном целом k выполнимо ровно при w_i=0. Любая ненулевая свободная координата даёт бесконечный порядок класса независимо от конечных остатков.
После вычисления конечного k полезно восстановить свидетельство: решить Dy=kw, затем положить z=Vy и проверить Az=kv. Такая подстановка подтверждает возврат. Минимальность доказывают условия делимости или отдельный ограниченный перебор для малого примера; одна найденная комбинация столбцов показывает лишь верхнюю границу порядка.
Возврат класса раньше размера всей группы
Условие. Даны A=[[16,−12],[−12,12]], U=[[1,1],[0,1]], V=[[1,0],[1,1]] и v=(1,2). Проверьте форму Смита и найдите порядок [v] по решётке AZ².
- Определители U и V равны единице. Прямое умножение UAV даёт D=diag(4,12), поэтому фактор имеет 48 элементов.
- Преобразованный вектор w=Uv равен (3,2). Для первой координаты нужен период 4/НОД(4,3)=4, для второй — 12/НОД(12,2)=6.
- Совместный минимальный период равен НОК(4,6)=12. Число 48 является размером группы, а не порядком данного элемента.
- Для k=12 решаем Dy=12w=(36,24), получая y=(9,2). Возвращаем исходные координаты z=Vy=(9,11). Действительно, Az=(12,24)=12v.
- Проверка k=6 даёт A⁻¹(6v)=(9/2,11/2), поэтому более короткий предложенный возврат невозможен. Вообще оба периода должны делить k, что исключает все положительные k<12.
Ответ. Порядок класса равен 12. Свидетельство возврата: A(9,11)=12(1,2). Размер всего фактора равен 48.
Проверка. Прямое рациональное решение A⁻¹(kv)=(3k/4,11k/12) целочисленно впервые при k=12; оно независимо проверяет диагональные условия.
Где легко ошибиться. Не подменяйте порядок конкретного класса определителем A. Определитель задаёт число классов для квадратной невырожденной матрицы, а период зависит ещё от положения v.
Проверьте понимание
Вопросы к этой главе
Что будет для diag(4,0) и v=(1,1)?
Вторая координата свободная и ненулевая. Ни одно положительное k не занулит её, поэтому класс имеет бесконечный порядок, хотя первая координата возвращается через четыре шага.
Обязательно ли использовать НОК всех инвариантов Смита?
Нет. Сначала каждый модуль сокращается на НОД с соответствующей координатой Uv. НОК самих модулей даёт общий показатель конечной группы, но может завысить порядок выбранного элемента.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- P. Brosnan, UMD: Cyclic Groups and Orders of Elements
Прочитана теорема 2.57 о порядке элемента циклической группы n/НОД(n,i) и её доказательство делимостью. Перенос через U, объединение периодов НОК и решёточный пример выведены отдельно; источник не выдаётся за алгоритм построения формы Смита.
Форма Эрмита различает решётки с одинаковыми инвариантами Смита
Одинаковые инвариантные множители Смита означают одинаковый абстрактный тип фактор-группы, но не положение подрешётки внутри выбранных целых координат. Форма Эрмита сохраняет само вложенное множество. Поэтому она отвечает на более конкретный вопрос: порождают ли два набора столбцов в точности одни и те же целочисленные точки?
Перед началом: Целочисленная решётка как образ столбцов; Унимодулярная матрица и инварианты Смита.
Правое преобразование меняет базис внутри той же решётки
Подрешётки полного ранга в фиксированной Z², заданные двумя столбцами; координаты окружающего пространства при сравнении не меняются.
Для невырожденной целочисленной A обозначим L(A)=A Z². Если U целочисленна и det U=±1, то U Z²=Z², откуда L(AU)=L(A). Такое преобразование заменяет генераторы, сохраняя все точки. Обратная U тоже целочисленна, поэтому включение работает в обе стороны, а не только для новых столбцов через старые.
Умножение слева на унимодулярную V действует иначе: L(VA)=V L(A). Это обратимая замена окружающих координат; она сохраняет абстрактный фактор, но не обязана сохранять конкретное подмножество Z². Приведение Смита разрешает преобразования с двух сторон, поэтому по одному диагональному результату равенство вложений не следует.
Треугольная нормировка хранит наклон вложения
Здесь договоримся о столбцовой форме H=[[a,b],[0,c]], где a,c>0 и 0≤b<a. Её столбцы получаются целочисленными обратимыми заменами исходных столбцов. Это явная конвенция: программы могут вместо неё возвращать строковую форму с другими расположением нулей и границами остатков. Сравнивать матрицы разных конвенций напрямую нельзя.
В размерности два каноничность видна без общего алгоритма. Проекция решётки на вторую координату равна cZ, поэтому c определяется самим множеством. Горизонтальные точки имеют вид (ak,0), что определяет a. Точка с нижней координатой c имеет верхнюю координату, определённую по модулю a; условие 0≤b<a выбирает единственный остаток. Значит одинаковые формы задают равные решётки, а разные формы — разные.
Индекс и тип фактора теряют часть координатной информации
Индекс равен ac и считает только число классов. Инварианты Смита дополнительно описывают их групповое сложение с точностью до изоморфизма. Но в обоих описаниях теряется то, какие именно векторы исходных координат принадлежат нулевому классу. При сравнении периодических ограничений или допустимых целых смещений это существенно.
Равенство также можно удостоверить двумя включениями: выразить каждый набор генераторов целочисленно через другой. Для квадратных базисов удобно вычислить A⁻¹B над рациональными и проверить целочисленность вместе с определителем ±1. Один целочисленный переход с определителем по модулю больше единицы доказывает лишь вложение подрешётки конечного индекса.
Три базиса с одинаковым Смитом, но двумя вложениями
Условие. Сравните решётки столбцов A=[[2,1],[0,3]], B=[[3,7],[3,9]], C=[[1,0],[0,6]]. Найдите их формы Эрмита в принятой конвенции и объясните роль инвариантов Смита.
- Все определители равны 6, а НОД элементов каждой матрицы равен 1. Поэтому во всех случаях инварианты Смита равны 1,6, фактор-группа изоморфна Z/6Z.
- Матрица A уже имеет нужную форму: a=2,b=1,c=3. Матрица C также нормирована, но её параметры a=1,b=0,c=6 отличаются.
- У B вычитаем из второго столбца удвоенный первый и получаем (1,3). Затем из первого вычитаем этот новый столбец и получаем (2,0). В итоге форма B совпадает с A.
- Полный сертификат: B·[[3,−2],[−1,1]]=A, определитель правой матрицы 1. Напротив, вектор (1,0) принадлежит L(C), но не L(A): нулевая нижняя координата заставляет второй коэффициент быть нулём, а верхняя тогда чётная.
Ответ. L(A)=L(B), но L(C) другая. Их формы Эрмита соответственно A,A,C, хотя у всех инварианты Смита 1,6.
Проверка. Обратный переход B=A·[[1,2],[1,3]] также целочисленный с определителем 1. Он независимо подтверждает второе включение, а свидетель (1,0) отделяет третью решётку.
Где легко ошибиться. Изоморфность Z²/L₁ и Z²/L₂ не означает L₁=L₂ в фиксированных координатах. Для равенства сравнивайте вложения, а не только абстрактные инварианты.
Проверьте понимание
Вопросы к этой главе
Почему обычное рациональное исключение не решает сравнение решёток?
Над Q все три матрицы имеют образ Q², и информация о целочисленной делимости исчезает. Деление генератора на число может добавить точки, которых в исходной решётке не было.
Можно вместо формы Эрмита проверить только определитель A⁻¹B?
Нет. Он должен быть ±1 и сам переход должен быть целочисленным. Рациональная матрица с определителем 1 ещё не отображает Z² на себя.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- SageMath — Integer matrices: Hermite form and transformation
Унимодулярное преобразование и необходимость фиксировать строковую или столбцовую конвенцию. Документация использует U·A=H; собственная двумерная столбцовая нормировка и её каноничность в главе доказаны явно.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Сколько корней между границами: проверка знаков без приближённого поиска
Подсчитать различные действительные корни рационального многочлена в открытом интервале по изменениям знаков последовательности Штурма.
Открыть темуРациональная замена начала ряда: когда [1/1] существует и где её полюс
По трём коэффициентам ряда построить нормированный аппроксимант Паде первого порядка и проверить совместность условий и полюс запроса.
Открыть тему